source: branches/stable/NALIGNER/ali_aligner.hxx

Last change on this file was 7623, checked in by westram, 8 years ago
  • merge from dev [7450] [7452] [7456] [7457] [7458] [7459] [7460] [7461] [7464] [7465] [7466] [7467] [7468] [7469] [7482]
    • tweaked compiler options
      • activated -Weffc++
        • postfilter warnings where Scott Meyers' advices are too general.
          • base classes should not always have virtual destructors, since that renders tiny classes useless and
          • members should not always be initialized via initialization list, since that often violates the DRY principle
        • fix gcc's inability to detect that Noncopyable implements a private copy-ctor and op=
        • this slows down complete ARB recompilation by ~5%
    • added -Wold-style-cast (inactive)
    • removed -Wno-non-template-friend added in [7447]
  • postcompile.pl
    • added option —original to show unmodified compiler output
  • declared op= for classes which had a copy-ctor
  • moved op= macros to arbtools.h
  • derived classes containing pointers from Noncopyable (use Noncopyable virtually) or
  • made them copyable if needed (awt_mask_item, KnownDB, Code, AWT_registered_itemtype, GEN_gene, PosGene, PartialSequence, PlugIn, Range, Convaln_exception)
  • other related changes
    • user mask destruction working now
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.8 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : ali_aligner.hxx                                   //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#ifndef ALI_ALIGNER_HXX
12#define ALI_ALIGNER_HXX
13
14#ifndef ALI_SOLUTION_HXX
15#include "ali_solution.hxx"
16#endif
17#ifndef ALI_TSTACK_HXX
18#include "ali_tstack.hxx"
19#endif
20#ifndef ALI_PATHMAP_HXX
21#include "ali_pathmap.hxx"
22#endif
23
24#define ALI_ALIGNER_INS        1
25#define ALI_ALIGNER_SUB        2
26#define ALI_ALIGNER_DEL        3
27#define ALI_ALIGNER_MULTI_FLAG 4
28
29struct ALI_ALIGNER_CONTEXT {
30    long max_number_of_maps;
31};
32
33// Structure of a cell of the distance matrix
34struct ali_aligner_cell {
35    float d1, d2, d3;
36    ALI_TARRAY<ali_pathmap_up_pointer> *starts;
37
38    ali_aligner_cell() {
39        d1 = d2 = d3 = 0.0;
40        starts = 0;
41    }
42
43    void print() {
44        printf("%4.2f %4.2f %4.2f %8p", d1, d2, d3, starts);
45    }
46};
47
48// Structure of a column of the distance matrix
49struct ali_aligner_column : virtual Noncopyable {
50    unsigned long column_length;
51    ali_aligner_cell **cells;
52
53    ali_aligner_column(unsigned long length) {
54        column_length = length;
55        cells = (ali_aligner_cell**) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
56        if (cells == 0)
57            ali_fatal_error("Out of memory");
58    }
59    ~ali_aligner_column() {
60        if (cells)
61            free((char  *) cells);
62    }
63
64    void print() {
65        unsigned int i;
66        for (i = 0; i < column_length; i++) {
67            printf("%2d: ", i);
68            (*cells)[i].print();
69            printf("\n");
70        }
71    }
72};
73
74// Structure of a LONG deletion (multi gap) in the distance matrix
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() {
88        printf("(%3ld %4.2f %2d)", start, costs, operation);
89    }
90};
91
92// Structure of the list of LONG deletions in the distance matrix
93struct ali_aligner_dellist : virtual Noncopyable {
94    ALI_PROFILE *profile;
95    ALI_TLIST<ali_aligner_dellist_elem *> list_of_dels;
96
97    ali_aligner_dellist(ALI_PROFILE *p) {
98        profile = p;
99    }
100    ~ali_aligner_dellist() {
101        ali_aligner_dellist_elem * elem;
102        if (!list_of_dels.is_empty()) {
103            elem = list_of_dels.first();
104            while (list_of_dels.is_next()) {
105                delete elem;
106                elem = list_of_dels.next();
107            }
108            delete elem;
109        }
110    }
111
112    void print() {
113        printf("DEL_LIST: ");
114        if (!list_of_dels.is_empty()) {
115            list_of_dels.first()->print();
116            while (list_of_dels.is_next()) {
117                printf(", ");
118                list_of_dels.next()->print();
119            }
120        }
121        printf("\n");
122    }
123    void print_cont(unsigned long position) {
124        ali_aligner_dellist_elem *elem;
125        if (!list_of_dels.is_empty()) {
126            elem = list_of_dels.first();
127            while (list_of_dels.is_next()) {
128                elem->print();
129                printf("\t %f\n", profile->gap_percent(elem->start, position));
130                elem = list_of_dels.next();
131            }
132            elem->print();
133            printf("\t %f\n", profile->gap_percent(elem->start, position));
134        }
135    }
136    unsigned long length() {
137        return list_of_dels.cardinality();
138    }
139    void make_empty() {
140        ali_aligner_dellist_elem *elem;
141        if (!list_of_dels.is_empty()) {
142            elem = list_of_dels.first();
143            while (list_of_dels.is_next()) {
144                delete elem;
145                elem = list_of_dels.next();
146            }
147            delete elem;
148        }
149        list_of_dels.make_empty();
150    }
151    void insert(unsigned long start, float costs, unsigned char operation) {
152        ali_aligner_dellist_elem *new_elem;
153
154        new_elem = new ali_aligner_dellist_elem(start, costs, operation);
155        list_of_dels.append_end(new_elem);
156    }
157    float update(unsigned long position);
158    ALI_TARRAY<ali_pathmap_up_pointer> *starts(float costs,
159                                               unsigned long y_offset);
160    void optimize(unsigned long position);
161};
162
163
164// Structure of the virtual cell at the left buttom
165struct ali_aligner_last_cell : virtual Noncopyable {
166    ALI_PROFILE *profile;
167    float d1, d2, d3;
168    ALI_TLIST<ali_pathmap_up_pointer> left_starts;
169    ALI_TLIST<ali_pathmap_up_pointer> up_starts;
170
171    ali_aligner_last_cell(ALI_PROFILE *prof) {
172        profile = prof;
173        d1 = d2 = d3 = -1.0;
174    }
175
176    void insert_left(unsigned long start, unsigned char operation, float costs) {
177        ali_pathmap_up_pointer left;
178        if (costs < d3 || d3 == -1.0) {
179            left_starts.make_empty();
180            d3 = costs;
181        }
182        if (costs == d3) {
183            left.start = start;
184            left.operation = operation;
185            left_starts.append_end(left);
186        }
187    }
188    void insert_up(unsigned long start, unsigned char operation, float costs) {
189        ali_pathmap_up_pointer up;
190        if (costs < d1 || d1 == -1.0) {
191            up_starts.make_empty();
192            d1 = costs;
193        }
194        if (costs == d1) {
195            up.start = start;
196            up.operation = operation;
197            up_starts.append_end(up);
198        }
199    }
200    void update_border(unsigned long start_x, unsigned long end_x,
201                       unsigned long start_y, unsigned long end_y)
202    {
203        float cost;
204
205        cost = profile->w_del_multi(start_y, end_y) +
206            profile->w_ins_multi(start_x, end_x);
207
208        insert_left(0, ALI_UP, cost);
209        insert_up(0, ALI_LEFT, cost);
210    }
211    void update_left(ali_aligner_cell *akt_cell, unsigned long akt_pos,
212                     unsigned long start_x, unsigned long end_x) {
213        float min;
214        unsigned char operation = 0;
215
216        min = (akt_cell->d1 < akt_cell->d2) ? akt_cell->d1 : akt_cell->d2;
217        if (akt_cell->d1 == min)
218            operation |= ALI_UP;
219        if (akt_cell->d2 == min)
220            operation |= ALI_DIAG;
221
222        insert_left(akt_pos, operation,
223                    min + profile->w_ins_multi_cheap(start_x + akt_pos, end_x));
224    }
225    void update_up(ali_aligner_cell *akt_cell, unsigned long akt_pos,
226                   unsigned long start_y, unsigned long end_y) {
227        float min;
228        unsigned char operation = 0;
229
230        min = (akt_cell->d3 < akt_cell->d2) ? akt_cell->d3 : akt_cell->d2;
231        if (akt_cell->d3 == min)
232            operation |= ALI_LEFT;
233        if (akt_cell->d2 == min)
234            operation |= ALI_DIAG;
235
236        insert_up(akt_pos, operation,
237                  min + profile->w_del_multi_cheap(start_y + akt_pos, end_y));
238    }
239    void update_up(ali_aligner_column *akt_col,
240                   unsigned long start_y, unsigned long end_y) {
241        unsigned long cell;
242
243        // Value for start := start + 1 (because of -1)
244
245        for (cell = 0; cell < akt_col->column_length - 1; cell++)
246            update_up(&(*akt_col->cells)[cell], cell + 1, start_y, end_y);
247
248        d2 = (*akt_col->cells)[akt_col->column_length - 1].d2;
249    }
250
251    void print() {
252        ali_pathmap_up_pointer elem;
253        printf("d1 = %f, d2 = %f, d3 = %f\n", d1, d2, d3);
254        printf("left starts = ");
255        if (!left_starts.is_empty()) {
256            elem = left_starts.first();
257            printf("<(%ld %d)", (long)elem.start, elem.operation);
258            while (left_starts.is_next()) {
259                elem = left_starts.next();
260                printf(", (%ld %d)", (long)elem.start, elem.operation);
261            }
262            printf(">\n");
263        }
264        else {
265            printf("empty\n");
266        }
267        printf("up starts = ");
268        if (!up_starts.is_empty()) {
269            elem = up_starts.first();
270            printf("<(%ld %d)", elem.start, elem.operation);
271            while (up_starts.is_next()) {
272                elem = up_starts.next();
273                printf(", (%ld %d)", (long)elem.start, elem.operation);
274            }
275            printf(">\n");
276        }
277        else {
278            printf("empty\n");
279        }
280    }
281};
282
283
284// Structure for collecting all possible solution
285struct ali_aligner_result : virtual Noncopyable {
286    ALI_TLIST<ALI_MAP *> *map_list;
287
288    ali_aligner_result() {
289        map_list = new ALI_TLIST<ALI_MAP *>;
290    }
291    ~ali_aligner_result() {
292        if (map_list) {
293            clear();
294            delete map_list;
295        }
296    }
297
298    void insert(ALI_MAP *in_map) {
299        map_list->append_end(in_map);
300    }
301    void clear() {
302        if (!map_list->is_empty()) {
303            delete map_list->first();
304            while (map_list->is_next())
305                delete map_list->next();
306        }
307    }
308};
309
310
311// Class of the extended aligner
312class ALI_ALIGNER : virtual Noncopyable {
313    ALI_PROFILE *profile;
314    ALI_PATHMAP *path_map[3];
315    ali_aligner_last_cell *last_cell;
316
317    ali_aligner_result result;
318    unsigned long result_counter;
319    unsigned long start_x, end_x, start_y, end_y;
320
321    float minimum2(float a, float b);
322    float minimum3(float a, float b, float c);
323
324    void calculate_first_column_first_cell(
325                                           ali_aligner_cell *akt_cell, ali_aligner_dellist *del_list);
326    void calculate_first_column_second_cell(
327                                            ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
328                                            ali_aligner_dellist *del_list);
329    void calculate_first_column_cell(
330                                     ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
331                                     unsigned long pos_y, ali_aligner_dellist *del_list);
332    void calculate_first_column(ali_aligner_column *akt_col,
333                                ali_aligner_dellist *del_list);
334
335    void calculate_second_column_first_cell(
336                                            ali_aligner_cell *left_cell, ali_aligner_cell *akt_cell,
337                                            ali_aligner_dellist *del_list);
338    void calculate_second_column_second_cell(
339                                             ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
340                                             ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
341                                             ali_aligner_dellist *del_list);
342    void calculate_second_column_cell(
343                                      ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
344                                      ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
345                                      unsigned long pos_y, ali_aligner_dellist *del_list);
346    void calculate_second_column(ali_aligner_column *prev_col,
347                                 ali_aligner_column *akt_col,
348                                 ali_aligner_dellist *del_list);
349
350    void calculate_first_cell(
351                              ali_aligner_cell *left_cell, ali_aligner_cell *akt_cell,
352                              unsigned long pos_x, ali_aligner_dellist *del_list);
353    void calculate_second_cell(
354                               ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
355                               ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
356                               unsigned long pos_x, ali_aligner_dellist *del_list);
357    void calculate_cell(ali_aligner_cell *diag_cell, ali_aligner_cell *left_cell,
358                        ali_aligner_cell *up_cell, ali_aligner_cell *akt_cell,
359                        unsigned long pos_x, unsigned long pos_y,
360                        ali_aligner_dellist *del_list);
361    void calculate_column(ali_aligner_column *prev_col,
362                          ali_aligner_column *akt_col,
363                          unsigned long pos_x,
364                          ali_aligner_dellist *del_list);
365
366    void calculate_matrix();
367
368    void generate_result(ALI_TSTACK<unsigned char> *stack);
369    void mapper_pre(ALI_TSTACK<unsigned char> *stack,
370                    unsigned long pos_x, unsigned long pos_y,
371                    unsigned char operation,
372                    int random_mapping_flag = 0);
373    void mapper_post(ALI_TSTACK<unsigned char> *stack,
374                     unsigned long pos_x, unsigned long pos_y);
375    void mapper_pre_random_up(
376                              ALI_TSTACK<unsigned char> *stack,
377                              ALI_TLIST<ali_pathmap_up_pointer> *list);
378    void mapper_pre_random_left(
379                                ALI_TSTACK<unsigned char> *stack,
380                                ALI_TLIST<ali_pathmap_up_pointer> *list);
381    void mapper_random(ALI_TSTACK<unsigned char> *stack, int plane,
382                       unsigned long pos_x, unsigned long pos_y);
383    void mapper(ALI_TSTACK<unsigned char> *stack, int plane,
384                unsigned long pos_x, unsigned long pos_y);
385    void make_map_random(ALI_TSTACK<unsigned char> *stack);
386    void make_map_systematic(ALI_TSTACK<unsigned char> *stack);
387    void make_map();
388
389    unsigned long number_of_solutions();
390
391public:
392    ALI_ALIGNER(ALI_ALIGNER_CONTEXT *context, ALI_PROFILE *profile,
393                unsigned long start_x, unsigned long end_x,
394                unsigned long start_y, unsigned long end_y);
395    ALI_TLIST<ALI_MAP *> *solutions() {
396        ALI_TLIST<ALI_MAP *> *ret = result.map_list;
397        result.map_list = 0;
398        return ret;
399    }
400};
401
402
403#else
404#error ali_aligner.hxx included twice
405#endif // ALI_ALIGNER_HXX
Note: See TracBrowser for help on using the repository browser.