source: branches/stable/NALIGNER/ali_prealigner.hxx

// =============================================================== //
//                                                                 //
//   File      : ali_prealigner.hxx                                //
//   Purpose   :                                                   //
//                                                                 //
//   Institute of Microbiology (Technical University Munich)       //
//   http://www.arb-home.de/                                       //
//                                                                 //
// =============================================================== //

#ifndef ALI_PREALIGNER_HXX
#define ALI_PREALIGNER_HXX

#ifndef ALI_PATHMAP_HXX
#include "ali_pathmap.hxx"
#endif
#ifndef ALI_TSTACK_HXX
#include "ali_tstack.hxx"
#endif
#ifndef ALI_SOLUTION_HXX
#include "ali_solution.hxx"
#endif

#define ALI_PREALIGNER_INS        1
#define ALI_PREALIGNER_SUB        2
#define ALI_PREALIGNER_DEL        3
#define ALI_PREALIGNER_MULTI_FLAG 4



struct ALI_PREALIGNER_CONTEXT {
    long max_number_of_maps;
    long max_number_of_maps_aligner;
    int interval_border;
    int interval_center;
    float max_cost_of_sub_percent;
    float max_cost_of_helix;
    unsigned long error_count;
};

// Structure for a cell in the (simple) distance matrix
struct ali_prealigner_cell {
    float d;

    ali_prealigner_cell() {
        d = 0.0;
    }
};

// Structure for a column in the (simple) distance matrix
struct ali_prealigner_column : virtual Noncopyable {
    unsigned long column_length;
    ali_prealigner_cell **cells;

    ali_prealigner_column(unsigned long length) {
        column_length = length;
        cells = (ali_prealigner_cell **) calloc((unsigned int) column_length, sizeof(ali_prealigner_cell));
        ali_out_of_memory_if(!cells);
    }
    ~ali_prealigner_column() {
        if (cells)
            free((char *) cells);
    }
};

// Structure for the intersection of maps
struct ali_prealigner_mask {
    ALI_MAP *map;
    float cost_of_binding;

    unsigned long calls, joins, last_new, last_joins;

    ali_prealigner_mask() {
        last_new = last_joins = 0;
        map = NULp;
        calls = joins = 0;
    }

    void insert(ALI_MAP *in_map, float costs);
    void delete_expensive(ALI_PREALIGNER_CONTEXT *context, ALI_PROFILE *profile);
    void clear() {
        last_new = last_joins = 0;
        delete map;
        calls = joins = 0;
    }
};

// Structure for a approximation of a map
struct ali_prealigner_approx_element : virtual Noncopyable {
    ALI_MAP *map;
    char *ins_marker;

    ali_prealigner_approx_element(ALI_MAP *m = NULp, char *im = NULp) {
        map = m;
        ins_marker = im;
    }
    ~ali_prealigner_approx_element() {
        /*
          if (map)
          delete map;
          if (ins_marker)
          free((char *) ins_marker);
        */
    }
    void print() {
        printf("map = %p, ins_marker = %p\n", map, ins_marker);
        map->print();
        printf("<%20s>\n", ins_marker);
    }
};

// Structure for a list of approximated maps
struct ali_prealigner_approximation : virtual Noncopyable {
    ALI_TLIST<ali_prealigner_approx_element *> *approx_list;
    float cost_of_binding;

    ali_prealigner_approximation() {
        cost_of_binding = 0.0;
        approx_list = new ALI_TLIST<ali_prealigner_approx_element *>;
    }
    ~ali_prealigner_approximation() {
        if (approx_list) {
            clear();
            delete approx_list;
        }
    }

    // Insert a new approximation (dependence of the costs)
    void insert(ALI_MAP *in_map, char *in_insert_marker, float costs) {
        ali_prealigner_approx_element *approx_elem;

        if (!approx_list)
            approx_list = new ALI_TLIST<ali_prealigner_approx_element *>;

        if (costs < cost_of_binding || approx_list->is_empty()) {
            cost_of_binding = costs;
            clear();
        }

        if (costs == cost_of_binding) {
            if (approx_list->cardinality() < 20) {
                approx_elem = new ali_prealigner_approx_element(in_map,
                                                                in_insert_marker);

                approx_list->append_end(approx_elem);
            }
            else {
                delete in_map;
                delete in_insert_marker;
            }
        }
        else {
            delete in_map;
            delete in_insert_marker;
        }
    }
    ALI_TLIST<ali_prealigner_approx_element *> *list() {
        ALI_TLIST<ali_prealigner_approx_element *> *ret_list;
        ret_list    = approx_list;
        approx_list = NULp;
        return ret_list;
    }
    void clear() {
        if (approx_list) {
            if (!approx_list->is_empty()) {
                delete approx_list->first();
                while (approx_list->has_next())
                    delete approx_list->next();
                approx_list->make_empty();
            }
        }
    }
    void print() {
        ali_prealigner_approx_element *approx_elem;
        printf("\nList of Approximations\n");
        printf("cost_of_binding = %f\n", cost_of_binding);
        if (approx_list) {
            if (!approx_list->is_empty()) {
                approx_elem = approx_list->first();
                approx_elem->print();
                while (approx_list->has_next()) {
                    approx_elem = approx_list->next();
                    approx_elem->print();
                }
            }
            else {
                printf("List is empty\n");
            }
        }
        else {
            printf("List not existent\n");
        }
    }
};



// Class of the prealigner
class ALI_PREALIGNER : virtual Noncopyable {
    ALI_PROFILE *profile;
    ALI_PATHMAP *path_map;
    ALI_SUB_SOLUTION *sub_solution;

    ali_prealigner_mask result_mask;
    unsigned long result_mask_counter;
    unsigned long start_x, end_x, start_y, end_y;
    ali_prealigner_approximation result_approx;

    float minimum2(float a, float b);
    float minimum3(float a, float b, float c);

    void calculate_first_column_first_cell(ali_prealigner_cell *akt_cell);
    void calculate_first_column_cell(ali_prealigner_cell *up_cell,
                                     ali_prealigner_cell *akt_cell,
                                     unsigned long pos_y);
    void calculate_first_column(ali_prealigner_column *akt_column);

    void calculate_first_cell(ali_prealigner_cell *left_cell,
                              ali_prealigner_cell *akt_cell,
                              unsigned long pos_x);
    void calculate_cell(
                        ali_prealigner_cell *diag_cell, ali_prealigner_cell *left_cell,
                        ali_prealigner_cell *up_cell, ali_prealigner_cell *akt_cell,
                        unsigned long pos_x, unsigned long pos_y);
    void calculate_column(ali_prealigner_column *prev_col,
                          ali_prealigner_column *akt_col,
                          unsigned long pos_x);

    void calculate_last_column_first_cell(ali_prealigner_cell *left_cell,
                                          ali_prealigner_cell *akt_cell,
                                          unsigned long pos_x);
    void calculate_last_column_cell(
                                    ali_prealigner_cell *diag_cell, ali_prealigner_cell *left_cell,
                                    ali_prealigner_cell *up_cell, ali_prealigner_cell *akt_cell,
                                    unsigned long pos_x, unsigned long pos_y);
    void calculate_last_column(ali_prealigner_column *prev_col,
                               ali_prealigner_column *akt_col,
                               unsigned long pos_x);

    void calculate_matrix();

    void generate_solution(ALI_MAP *map);
    void generate_result_mask(ALI_TSTACK<unsigned char> *stack);
    void mapper_pre(ALI_TSTACK<unsigned char> *stack,
                    unsigned long pos_x, unsigned long pos_y);
    void mapper_post(ALI_TSTACK<unsigned char> *stack,
                     unsigned long pos_x, unsigned long pos_y);
    void mapper_post_multi(ALI_TSTACK<unsigned char> *stack,
                           unsigned long pos_x, unsigned long pos_y);
    void mapper_random(ALI_TSTACK<unsigned char> *stack,
                       unsigned long pos_x, unsigned long pos_y);
    void mapper(ALI_TSTACK<unsigned char> *stack,
                unsigned long pos_x, unsigned long pos_y);
    void make_map();

    void generate_approximation(ALI_SUB_SOLUTION *work_sol);
    void mapper_approximation(unsigned long area_number,
                              ALI_TARRAY<ALI_TLIST<ALI_MAP *> *> *map_lists,
                              ALI_SUB_SOLUTION *work_sol);
    void make_approximation(ALI_PREALIGNER_CONTEXT *context);

    unsigned long number_of_solutions();

public:

    ALI_PREALIGNER(ALI_PREALIGNER_CONTEXT *context, ALI_PROFILE *profile,
                   unsigned long start_x, unsigned long end_x,
                   unsigned long start_y, unsigned long end_y);
    ~ALI_PREALIGNER() {
        if (sub_solution)
            delete sub_solution;
    }

    ALI_SEQUENCE *sequence() {
        return result_mask.map->sequence(profile->sequence());
    }
    ALI_SEQUENCE *sequence_without_inserts() {
        return result_mask.map->sequence_without_inserts(profile->sequence());
    }
    ALI_SUB_SOLUTION *solution() {
        ALI_SUB_SOLUTION *ret_sol = sub_solution;
        sub_solution = NULp;
        return ret_sol;
    }
    ALI_TLIST<ali_prealigner_approx_element *> *approximation() {
        return result_approx.list();
    }
};

#else
#error ali_prealigner.hxx included twice
#endif // ALI_PREALIGNER_HXX