source: tags/arb_5.2/NALIGNER/ali_aligner.hxx

Last change on this file was 4912, checked in by westram, 17 years ago
  • untabified + indented
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.4 KB
Line 
1
2
3#ifndef _ALI_ALIGNER_INC_
4#define _ALI_ALIGNER_INC_
5
6// #include <malloc.h>
7
8#include "ali_solution.hxx"
9#include "ali_tstack.hxx"
10#include "ali_tlist.hxx"
11#include "ali_tarray.hxx"
12#include "ali_profile.hxx"
13#include "ali_pathmap.hxx"
14
15#define ALI_ALIGNER_INS        1
16#define ALI_ALIGNER_SUB        2
17#define ALI_ALIGNER_DEL        3
18#define ALI_ALIGNER_MULTI_FLAG 4
19
20struct ALI_ALIGNER_CONTEXT {
21    long max_number_of_maps;
22};
23
24/*
25 * Structure of a cell of the distance matrix
26 */
27struct ali_aligner_cell {
28    float d1, d2, d3;
29    ALI_TARRAY<ali_pathmap_up_pointer> *starts;
30
31    ali_aligner_cell(void) {
32        d1 = d2 = d3 = 0.0;
33        starts = 0;
34    }
35
36    void print(void) {
37        printf("%4.2f %4.2f %4.2f %8p",d1,d2,d3,starts);
38    }
39};
40
41/*
42 * Structure of a column of the distance matrix
43 */
44struct ali_aligner_column {
45    unsigned long column_length;
46    //ali_aligner_cell (*cells)[];
47    ali_aligner_cell **cells;
48
49    ali_aligner_column(unsigned long length) {
50        column_length = length;
51        cells = (ali_aligner_cell**) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
52        //cells = (ali_aligner_cell (*) [0]) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
53        //cells = (ali_aligner_cell (*) [1]) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
54        if (cells == 0)
55            ali_fatal_error("Out of memory");
56    }
57    ~ali_aligner_column(void) {
58        if (cells)
59            free((char  *) cells);
60    }
61
62    void print(void) {
63        unsigned int i;
64        for (i = 0; i < column_length; i++) {
65            printf("%2d: ",i);
66            (*cells)[i].print();
67            printf("\n");
68        }
69    }
70};
71
72/*
73 * Structure of a LONG deletion (multi gap) in the distance matrix
74 */
75struct ali_aligner_dellist_elem {
76    unsigned long start;
77    float costs;
78    unsigned char operation;
79
80    ali_aligner_dellist_elem(unsigned long s = 0, float c = 0.0,
81                             unsigned char op = 0) {
82        start = s;
83        costs = c;
84        operation = op;
85    }
86
87    void print(void) {
88        printf("(%3ld %4.2f %2d)",start,costs,operation);
89    }
90};
91
92/*
93 * Structure of the list of LONG deletions in the distance matrix
94 */
95struct ali_aligner_dellist {
96    ALI_PROFILE *profile;
97    ALI_TLIST<ali_aligner_dellist_elem *> list_of_dels;
98
99    ali_aligner_dellist(ALI_PROFILE *p) {
100        profile = p;
101    }
102    ~ali_aligner_dellist(void) {
103        ali_aligner_dellist_elem * elem;
104        if (!list_of_dels.is_empty()) {
105            elem = list_of_dels.first();
106            while (list_of_dels.is_next()) {
107                delete elem;
108                elem = list_of_dels.next();
109            }
110            delete elem;
111        }
112    }
113
114    void print(void) {
115        printf("DEL_LIST: ");
116        if (!list_of_dels.is_empty()) {
117            list_of_dels.first()->print();
118            while (list_of_dels.is_next()) {
119                printf(", ");
120                list_of_dels.next()->print();
121            }
122        }
123        printf("\n");
124    }
125    void print_cont(unsigned long position) {
126        ali_aligner_dellist_elem *elem;
127        if (!list_of_dels.is_empty()) {
128            elem = list_of_dels.first();
129            while (list_of_dels.is_next()) {
130                elem->print();
131                printf("\t %f\n",profile->gap_percent(elem->start,position));
132                elem = list_of_dels.next();
133            }
134            elem->print();
135            printf("\t %f\n",profile->gap_percent(elem->start,position));
136        }
137    }
138    unsigned long length(void) {
139        return list_of_dels.cardinality();
140    }
141    void make_empty(void) {
142        ali_aligner_dellist_elem *elem;
143        if (!list_of_dels.is_empty()) {
144            elem = list_of_dels.first();
145            while (list_of_dels.is_next()) {
146                delete elem;
147                elem = list_of_dels.next();
148            }
149            delete elem;
150        }
151        list_of_dels.make_empty();
152    }
153    void insert(unsigned long start, float costs, unsigned char operation) {
154        ali_aligner_dellist_elem *new_elem;
155
156        new_elem = new ali_aligner_dellist_elem(start,costs,operation);
157        list_of_dels.append_end(new_elem);
158    }
159    float update(unsigned long position);
160    ALI_TARRAY<ali_pathmap_up_pointer> *starts(float costs,
161                                               unsigned long y_offset);
162    void optimize(unsigned long position);
163};
164
165
166/*
167 * Structure of the virtual cell at the left buttom
168 */
169struct ali_aligner_last_cell {
170    ALI_PROFILE *profile;
171    float d1, d2, d3;
172    ALI_TLIST<ali_pathmap_up_pointer> left_starts;
173    ALI_TLIST<ali_pathmap_up_pointer> up_starts;
174
175    ali_aligner_last_cell(ALI_PROFILE *prof) {
176        profile = prof;
177        d1 = d2 = d3 = -1.0;
178    }
179
180    void insert_left(unsigned long start, unsigned char operation, float costs) {
181        ali_pathmap_up_pointer left;
182        if (costs < d3 || d3 == -1.0) {
183            left_starts.make_empty();
184            d3 = costs;
185        }
186        if (costs == d3) {
187            left.start = start;
188            left.operation = operation;
189            left_starts.append_end(left);
190        }
191    }
192    void insert_up(unsigned long start, unsigned char operation, float costs) {
193        ali_pathmap_up_pointer up;
194        if (costs < d1 || d1 == -1.0) {
195            up_starts.make_empty();
196            d1 = costs;
197        }
198        if (costs == d1) {
199            up.start = start;
200            up.operation = operation;
201            up_starts.append_end(up);
202        }
203    }
204    void update_border(unsigned long start_x, unsigned long end_x,
205                       unsigned long start_y, unsigned long end_y)
206    {
207        float cost;
208
209        cost = profile->w_del_multi(start_y, end_y) +
210            profile->w_ins_multi(start_x, end_x);
211
212        insert_left(0, ALI_UP, cost);
213        insert_up(0, ALI_LEFT, cost);
214    }
215    void update_left(ali_aligner_cell *akt_cell, unsigned long akt_pos,
216                     unsigned long start_x, unsigned long end_x) {
217        float min;
218        unsigned char operation = 0;
219
220        min = (akt_cell->d1 < akt_cell->d2) ? akt_cell->d1 : akt_cell->d2;
221        if (akt_cell->d1 == min)
222            operation |= ALI_UP;
223        if (akt_cell->d2 == min)
224            operation |= ALI_DIAG;
225
226        insert_left(akt_pos, operation,
227                    min + profile->w_ins_multi_cheap(start_x + akt_pos, end_x));
228    }
229    void update_up(ali_aligner_cell *akt_cell, unsigned long akt_pos,
230                   unsigned long start_y, unsigned long end_y) {
231        float min;
232        unsigned char operation = 0;
233
234        min = (akt_cell->d3 < akt_cell->d2) ? akt_cell->d3 : akt_cell->d2;
235        if (akt_cell->d3 == min)
236            operation |= ALI_LEFT;
237        if (akt_cell->d2 == min)
238            operation |= ALI_DIAG;
239
240        insert_up(akt_pos,operation,
241                  min + profile->w_del_multi_cheap(start_y + akt_pos, end_y));
242    }
243    void update_up(ali_aligner_column *akt_col,
244                   unsigned long start_y, unsigned long end_y) {
245        unsigned long cell;
246
247        /*
248         * Value for start := start + 1 (because of -1)
249         */
250
251        for (cell = 0; cell < akt_col->column_length - 1; cell++)
252            update_up(&(*akt_col->cells)[cell], cell + 1, start_y, end_y);
253
254        d2 = (*akt_col->cells)[akt_col->column_length - 1].d2;
255    }
256
257    void print(void) {
258        ali_pathmap_up_pointer elem;
259        printf("d1 = %f, d2 = %f, d3 = %f\n",d1,d2,d3);
260        printf("left starts = ");
261        if (!left_starts.is_empty()) {
262            elem = left_starts.first();
263            printf("<(%ld %d)",(long)elem.start,elem.operation);
264            while (left_starts.is_next()) {
265                elem = left_starts.next();
266                printf(", (%ld %d)",(long)elem.start,elem.operation);
267            }
268            printf(">\n");
269        }
270        else {
271            printf("empty\n");
272        }
273        printf("up starts = ");
274        if (!up_starts.is_empty()) {
275            elem = up_starts.first();
276            printf("<(%ld %d)",elem.start,elem.operation);
277            while (up_starts.is_next()) {
278                elem = up_starts.next();
279                printf(", (%ld %d)",(long)elem.start,elem.operation);
280            }
281            printf(">\n");
282        }
283        else {
284            printf("empty\n");
285        }
286    }
287};
288
289
290/*
291 * Structure for collecting all possible solution
292 */
293struct ali_aligner_result {
294    ALI_TLIST<ALI_MAP *> *map_list;
295
296    ali_aligner_result(void) {
297        map_list = new ALI_TLIST<ALI_MAP *>;
298    }
299    ~ali_aligner_result(void) {
300        if (map_list) {
301            clear();
302            delete map_list;
303        }
304    }
305
306    void insert(ALI_MAP *in_map) {
307        map_list->append_end(in_map);
308    }
309    void clear(void) {
310        if (!map_list->is_empty()) {
311            delete map_list->first();
312            while (map_list->is_next())
313                delete map_list->next();
314        }
315    }
316};
317
318
319/*
320 * Class of the extended aligner
321 */
322class ALI_ALIGNER {
323    ALI_PROFILE *profile;
324    ALI_PATHMAP *path_map[3];
325    ali_aligner_last_cell *last_cell;
326
327    ali_aligner_result result;
328    unsigned long result_counter;
329    unsigned long start_x, end_x, start_y, end_y;
330
331    float minimum2(float a, float b);
332    float minimum3(float a, float b, float c);
333
334    void calculate_first_column_first_cell(
335                                           ali_aligner_cell *akt_cell, ali_aligner_dellist *del_list);
336    void calculate_first_column_second_cell(
337                                            ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
338                                            ali_aligner_dellist *del_list);
339    void calculate_first_column_cell(
340                                     ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
341                                     unsigned long pos_y, ali_aligner_dellist *del_list);
342    void calculate_first_column(ali_aligner_column *akt_col,
343                                ali_aligner_dellist *del_list);
344
345    void calculate_second_column_first_cell(
346                                            ali_aligner_cell *left_cell, ali_aligner_cell *akt_cell,
347                                            ali_aligner_dellist *del_list);
348    void calculate_second_column_second_cell(
349                                             ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
350                                             ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
351                                             ali_aligner_dellist *del_list);
352    void calculate_second_column_cell(
353                                      ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
354                                      ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
355                                      unsigned long pos_y, ali_aligner_dellist *del_list);
356    void calculate_second_column(ali_aligner_column *prev_col,
357                                 ali_aligner_column *akt_col,
358                                 ali_aligner_dellist *del_list);
359
360    void calculate_first_cell(
361                              ali_aligner_cell *left_cell, ali_aligner_cell *akt_cell,
362                              unsigned long pos_x, ali_aligner_dellist *del_list);
363    void calculate_second_cell(
364                               ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
365                               ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
366                               unsigned long pos_x, ali_aligner_dellist *del_list);
367    void calculate_cell(ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
368                        ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
369                        unsigned long pos_x, unsigned long pos_y,
370                        ali_aligner_dellist *del_list);
371    void calculate_column(ali_aligner_column *prev_col,
372                          ali_aligner_column *akt_col,
373                          unsigned long pos_x,
374                          ali_aligner_dellist *del_list);
375
376    void calculate_matrix(void);
377
378    void generate_result(ALI_TSTACK<unsigned char> *stack);
379    void mapper_pre(ALI_TSTACK<unsigned char> *stack,
380                    unsigned long pos_x, unsigned long pos_y,
381                    unsigned char operation,
382                    int random_mapping_flag = 0);
383    void mapper_post(ALI_TSTACK<unsigned char> *stack,
384                     unsigned long pos_x, unsigned long pos_y);
385    void mapper_pre_random_up(
386                              ALI_TSTACK<unsigned char> *stack,
387                              ALI_TLIST<ali_pathmap_up_pointer> *list);
388    void mapper_pre_random_left(
389                                ALI_TSTACK<unsigned char> *stack,
390                                ALI_TLIST<ali_pathmap_up_pointer> *list);
391    void mapper_random(ALI_TSTACK<unsigned char> *stack, int plane,
392                       unsigned long pos_x, unsigned long pos_y);
393    void mapper(ALI_TSTACK<unsigned char> *stack, int plane,
394                unsigned long pos_x, unsigned long pos_y);
395    void make_map_random(ALI_TSTACK<unsigned char> *stack);
396    void make_map_systematic(ALI_TSTACK<unsigned char> *stack);
397    void make_map(void);
398
399    unsigned long number_of_solutions();
400
401public:
402    ALI_ALIGNER(ALI_ALIGNER_CONTEXT *context, ALI_PROFILE *profile,
403                unsigned long start_x, unsigned long end_x,
404                unsigned long start_y, unsigned long end_y);
405    ALI_TLIST<ALI_MAP *> *solutions(void) {
406        ALI_TLIST<ALI_MAP *> *ret = result.map_list;
407        result.map_list = 0;
408        return ret;
409    }
410};
411
412
413
414#endif
415
Note: See TracBrowser for help on using the repository browser.