Debian Codegraph @

CAligner/CAligner.h

raw
1 /* BaitFisher (version 1.2.7) a program for designing DNA target enrichment baits
2 * Copyright 2013-2016 by Christoph Mayer
3 *
4 * This source file is part of the BaitFisher-package.
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
18 *
19 *
20 * For any enquiries send an Email to Christoph Mayer
21 * [email protected]
22 *
23 * When publishing work that is based on the results please cite:
24 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
25 *
26 */
27
28 #define NODEBUG
29 #ifndef CALIGNER_H
30
31 #define CALIGNER_H
32
33 // Changes:
34 // 8.2.2012: Trailing gaps are never free in the matrix. First I thought this
35 // could be handled without much effort in the traceback routine, but
36 // things seem to be ambiguous then.
37 // One solution would be to look for the maximum along the original
38 // back boundary of the dynamic programming matrix.
39
40 // 18.9.2014: TODO: Import coords_of_s1_in_al_string
41 // al_perfection
42 // from *_experimental.h
43
44 #include <iostream>
45 #include <fstream>
46 #include <vector>
47 #include <string>
48
49 #include "../faststring2.h"
50 #include "../scoring-matrices/CScoreMatrix.h"
51
52 #include <limits.h>
53
54 //const int DEBUG_LEVEL=5;
55
56 #define NDEBUG
57
58 #define DEBUG_i_min 15700
59 #define DEBUG_i_max 15800
60
61
62
63 #ifdef DEBUG
64 #define DEBUGOUT1(x) std::cerr << x << std::endl;
65 #define DEBUGOUT2(x,y) std::cerr << x << y << std::endl;
66 #define DEBUGOUT3(x,y,z) std::cerr << x << y << z << std::endl;
67 #define DEBUGOUT4(x,y,z,w) std::cerr << x << y << z << w << std::endl;
68
69 #define DEBUGOUT4Del_OS(os,x,y,z,w) os << x << "," << y << "," << z << "," << w << std::endl;
70
71 #define DEBUGOUT4Del(x,y,z,w) std::cerr << x << "," << y << "," << z << "," << w << std::endl;
72 #define DEBUGCODE(x) {x}
73
74 #define IF_IN_DEB_RANGE if(i>=DEBUG_i_min && i<=DEBUG_i_max)
75 #else
76 #define DEBUGOUT1(x)
77 #define DEBUGOUT2(x,y)
78 #define DEBUGOUT3(x,y,z)
79 #define DEBUGOUT4(x,y,z,w)
80 #define DEBUGOUT4Del(x,y,z,w)
81
82 #define DEBUGOUT4Del_OS(os,x,y,z,w)
83
84 #define DEBUGCODE(x)
85
86 #define IF_IN_DEB_RANGE
87 #endif
88
89
90 #define RECENTER_AFTER 3
91 #define U_ENTRY INT_MIN + 1000000
92 #define U_ENTRY2 INT_MIN + 3000000
93
94 #define macromax2(a,b) ((a<b)?b:a)
95 #define macromin2(a,b) ((a>b)?b:a)
96 #define macromax3(a,b,c) (macromax2(c, macromax2(a,b)))
97
98 #define next_odd(x) ((x%2==0)?x+1:x)
99
100 // #define MATCHSCORE 1
101 #define N_SCORE 0
102 #define NOCOMPILE_NO_OFFSET 1
103
104 #define DIRECTION -
105
106
107 #define move_forward_in_seq(pos, b, e, s, l) {pos += s; while (pos >= e) pos -=l;}
108 #define move_backward_in_seq(pos, b, e, s, l) {pos += s; while (pos <= b) pos +=l;}
109
110 // #define move_forward_in_seq_pp(pos, b, e, l) ((++pos >= e)?pos: pos -=l)
111 // #define move_backward_in_seq_mm(pos, b, e, l) ((--pos <= b)?pos: pos +=l)
112
113
114
115 inline void move_forward_in_seq_pp(const char *&pos, const char *b, const char *e, int l)
116 {
117 ++pos;
118 if (pos >= e)
119 pos -= l;
120 }
121
122 inline void debug_cyclic_checker(const char *pos, const char *s, int l, const char *error_msg)
123 {
124 if (pos < s)
125 {
126 std::cerr << "CYCLIC Lower bound exceeded: " << error_msg << std::endl;
127 }
128
129 if (pos >= s+l)
130 {
131 std::cerr << "CYCLIC Upper bound exceeded: " << error_msg << std::endl;
132 }
133 }
134
135
136
137
138
139
140
141
142 // typedef int scoretype;
143
144 using namespace std;
145
146 class align_coord
147 {
148 public:
149 int col;
150 int row;
151
152 align_coord(int c=0, int r=0):col(c), row(r)
153 {}
154
155 void print(ostream &os)
156 {
157 os << "(" << col << "," << row << ") ";
158 }
159
160 bool valid(int mcol, int mrow)
161 {
162 return (col >= 0 && col < mcol && row >= 0 && row < mrow);
163 }
164 };
165
166
167 inline int max3(int a, int b, int c)
168 {
169 int tmp = macromax2(a,b);
170 return macromax2(tmp,c);
171 }
172
173 inline void print_index(ostream &os, int x, int y)
174 {
175 os << "(" << x << "," << y << ") ";
176 }
177
178 class CAligner
179 {
180 // Convention:
181 // s1 has to be envisaged above the first row. s1 index corresponds to first index in the matrices.
182 // s2 has to be envisaged before the first column. s2 index corresponds to second index in the matrices.
183
184 // The size of the matrix is l1 x l2.
185 //
186
187 ostream &log_file;
188 int **ar_s; // array of scores, first index will be the column (x), the second index the row (y)
189 char **ar_bto; // array of bytes indicating the backtrace route. 0: Only initialized, bit1: match , bit2: mismatch, bit3: gap in s2 (score2 und p2), bit4: gap in s1 (score3 und p3)
190 // Valid coordinates in these two fields:
191 // 0..l1, 0..l2,
192
193 // int stopscore;
194 // int last_col_computed;
195
196 CScoreMatrix &score_mat;
197
198 const char* s1; // pointer to sequence 1
199 int l1; // length of sequence 1
200
201 const char* s2; // pointer to sequence 2
202 int l2; // length of sequence 2
203
204 // int l_max;
205
206 int gap_open;
207 int gap_ext;
208 // int mis_pen;
209 int alignment_score;
210
211 short alignment_mode; // 0: global_alignment, 1: non-global alignment, 2: cyclic alignment
212
213 // bool global_alignment;
214 bool free_front_gaps;
215 bool free_back_gaps;
216
217 void init_border()
218 {
219 // init the border
220 int i;
221
222 if (free_front_gaps)
223 {
224 for (i=0; i<=l1; ++i)
225 {
226 // Fill first row, corresponding to gaps in s2
227 ar_s[i][0] = 0;
228 ar_bto[i][0] = 4;
229 }
230 for (i=0; i<=l2; ++i)
231 {
232 // Fill first columnn, corresponding to gaps in s1
233 ar_s[0][i] = 0;
234 ar_bto[0][i] = 8;
235 }
236 ar_bto[0][0] = 0; // Has no predesessor
237 }
238 else
239 {
240 for (i=0; i<=l1; ++i)
241 {
242 // Fill first column, corresponding to gaps in s2
243 ar_s[i][0] = -(i*gap_ext + gap_open);
244 ar_bto[i][0] = 4;
245 }
246 for (i=0; i<=l2; ++i)
247 {
248 // Fill first row, corresponding to gaps in s1
249 ar_s[0][i] = -(i*gap_ext + gap_open);
250 ar_bto[0][i] = 8;
251 }
252 ar_bto[0][0] = 0; // Has no predesessor
253 }
254 }
255
256 public:
257 void print_ar_s(ostream &os)
258 {
259 int i, j;
260
261 os << "Score matrix:" << endl;
262 for (j=0; j <= l2; ++j)
263 {
264 for (i=0; i <= l1; ++i)
265 {
266 os.width(3);
267 if (ar_s[i][j] < U_ENTRY2)
268 os << "-";
269 else
270 os << ar_s[i][j];
271 }
272 os << endl;
273 }
274 }
275
276 void print_ar_bto(ostream &os)
277 {
278 int i, j;
279
280 os << "Traceback matrix:" << endl;
281 for (j=0; j <= l2; ++j)
282 {
283 for (i=0; i <= l1; ++i)
284 {
285 os.width(3);
286 if (ar_s[i][j] < U_ENTRY2)
287 os << "-";
288 else
289 os << (int) ar_bto[i][j];
290 }
291 os << endl;
292 }
293 }
294
295
296 CAligner(const char* param_s1, int pl1, const char* param_s2, int pl2,
297 CScoreMatrix &param_score_mat, short param_alignmentmode,
298 ostream &plog_file=cerr, int pstopscore=INT_MIN):
299 log_file(plog_file),
300 score_mat(param_score_mat),
301 s1(param_s1), l1(pl1), s2(param_s2), l2(pl2),
302
303 gap_open( -param_score_mat.get_Gap_open_score() ),
304 gap_ext( -param_score_mat.get_Gap_ext_score() ),
305 alignment_mode(param_alignmentmode)
306 {
307 int i,j;
308 ar_s = new int*[l1+1]; // col pointer vector
309 ar_bto = new char*[l1+1];
310
311 for (i=0; i <= l1; ++i) // for all columns
312 {
313 ar_s[i] = new int [l2+1];
314 ar_bto[i] = new char[l2+1];
315 }
316
317 DEBUGCODE(
318 cerr << "Alignment parameters: " << endl;
319 cerr << "gap opening: " << -gap_open << endl;
320 cerr << "gap extension: " << -gap_ext << endl << endl;
321 )
322
323 // Init alignment array
324 for (i=0; i <= l1; ++i)
325 {
326 for (j=0; j <= l2; ++j)
327 {
328 ar_s[i][j] = U_ENTRY;
329 ar_bto[i][j] = 0;
330 }
331 }
332
333
334 DEBUGCODE(cerr << "Mode: (intern) " << alignment_mode << endl;)
335
336 if (alignment_mode == 0) // global
337 {
338 free_front_gaps = false;
339 free_back_gaps = false;
340 DEBUGCODE(cerr << "Mode: global mode" << endl;)
341 }
342 else if (alignment_mode==1) // local
343 {
344 free_front_gaps = true;
345 free_back_gaps = true;
346 DEBUGCODE(cerr << "Mode: local mode" << endl;)
347 }
348 else // cyclic
349 {
350 free_front_gaps = false;
351 free_back_gaps = true;
352 DEBUGCODE(cerr << "Mode: cyclic mode" << endl;)
353 }
354 }
355
356
357 ~CAligner()
358 {
359 int i;
360
361 for (i=0; i<= l1; ++i)
362 {
363 delete [] ar_s[i];
364 delete [] ar_bto[i];
365 }
366 delete [] ar_s;
367 delete [] ar_bto;
368 }
369
370 void print_time_stamp_to_log_file(const char * s)
371 {
372 log_file << "Time: " << s << " " << time(NULL) << endl;
373 }
374
375 void align()
376 {
377 int i,j;
378
379 init_border();
380
381 // print_ar_s(std::cerr);
382 // print_ar_bto(std::cerr);
383
384 // std::cerr << "GAP*******" << gap_open << std::endl;
385
386
387 int score1;
388 int score2;
389 int score3;
390 char match_mismatch;
391 int align_score;
392
393 // TODO: Further improve efficienty: Loop over < l2, <l1.
394 // This removes the if that check for the last row and column.
395
396 for (j=1; j <= l2; ++j) // loop over all rows
397 {
398 for (i = 1; i <= l1; ++i ) // loop over all cols
399 {
400 // Caution: Both loops start at 1 since row and column 1 have already been filled.
401 // However, row and col 1 correspond to entry 0 of the sequence. So sequence indices
402 // are shifted by -1:
403
404 DEBUGCODE(
405 cerr << "al: i " << i << " j " << j
406 << " s1[i-1]=" << "s1[" << i-1 << "]=" << s1[i-1] << " s2[j-1]=" << "s2[" << j-1 << "]= " << s2[j-1]
407 << " ar_s[i-1][j] "<< ar_s[i-1][j] << " ar_s[i-1][j-1] "<< ar_s[i-1][j-1] << " ar_s[i][j-1] "<< ar_s[i][j-1]
408 << endl;
409 )
410
411 // Do we have a match - what is the match/mismatch score
412 align_score = score_mat.score_compare_symbols(s1[i-1], s2[j-1]);
413 if (s1[i-1] == s2[j-1])
414 match_mismatch = 1; // set bit 1
415 else
416 match_mismatch = 2; // set bit 2
417
418 {
419 // match gap gap
420 // ar_s[i][j] = macromax3( ar_s[i-1][j-1]+match_score, ar_s[i][j-1]-gap_ext, ar_s[i-1][]-gap_ext);
421
422 // Compute:
423 // score1, score2, score3:
424 // score1: match or mismatch
425 // score2: gap in s2, horizontal move in matrix
426 // score3: gap in s1, vertical move in matrix
427
428 score1 = ar_s[i-1][j-1]+align_score;
429
430 if (!free_back_gaps || (i < l1 && j < l2 ) )
431 {
432 score2 = ar_s[i-1][j] - gap_ext; // gap in s2
433 score3 = ar_s[i][j-1] - gap_ext; // gap in s1
434
435 if ( !(ar_bto[i-1][j]&4) )
436 {
437 score2 -= gap_open;
438 }
439 if ( !(ar_bto[i][j-1]&8) )
440 {
441 score3 -= gap_open;
442 }
443 }
444 else // free_back_gaps and either i or j on the back boundary:
445 {
446 if (i==l1 && j==l2)
447 {
448 score2 = ar_s[i-1][j]; // gap in s2
449 score3 = ar_s[i][j-1]; // gap in s1
450 }
451 else if (i==l1)
452 {
453 score2 = ar_s[i-1][j] - gap_ext; // gap in s2
454 if ( !(ar_bto[i-1][j]&4) )
455 {
456 score2 -= gap_open;
457 }
458 score3 = ar_s[i][j-1] - 0; // gap in s1
459 }
460 else // if (j==l2)
461 {
462 score2 = ar_s[i-1][j] - 0; // gap in s2
463 score3 = ar_s[i][j-1] - gap_ext; // gap in s1
464 if ( !(ar_bto[i][j-1]&8) )
465 {
466 score3 -= gap_open;
467 }
468 }
469 }
470
471 DEBUGOUT4Del("al score1 ", i-1, j-1, score1);
472 DEBUGOUT4Del("al score2 ", i-1, j, score2);
473 DEBUGOUT4Del("al score3 ", i, j-1, score3);
474
475 DEBUGOUT4Del("2: al ar_bto[i-1][j]", i-1, j, (int)ar_bto[i-1][j]);
476 DEBUGOUT4Del("3: al ar_bto[i][j-1]", i, j-1, (int)ar_bto[i][j-1]);
477
478 if (score1 >= score2 && score1 >= score3)
479 {
480 ar_s[i][j] = score1;
481 ar_bto[i][j] = match_mismatch; // set bit 1 or 2
482 if (score1 == score2)
483 ar_bto[i][j] += 4; // set bit 3 in addition to other bit
484 if (score1 == score3)
485 ar_bto[i][j] += 8; // set bit 4 in addition to what has been set before
486 }
487 else if (score2 >= score3) // gap in s2
488 {
489 ar_s[i][j] = score2;
490 ar_bto[i][j] = 4; // set bit 3
491 if (score2 == score3)
492 ar_bto[i][j] = 12; // set bit 4 in addition to bit 3
493 }
494 else // score3 > score2 and score1 // gap in s1
495 {
496 ar_s[i][j] = score3;
497 ar_bto[i][j] = 8; // set bit 4
498 }
499
500 DEBUGCODE(
501 log_file << "al: scores: ";
502 print_index(log_file, i, j);
503 log_file << score1 << " " << score2 << " " << score3
504 << " " << ar_s[i][j] << " bto: " << (int)ar_bto[i][j]
505 << endl;
506 );
507 } // END Block
508 } // END loop over all cols
509 } // END loop over all rows
510
511
512 /* int col_maximum = ar_s[i][find_max_index_of_col(i)]; */
513
514 /* if (col_maximum < stopscore) */
515 /* // break; // This means we leave the for (i=1; i < length; ++i) loop */
516 /* { */
517 /* DEBUGOUT1("Breaking out of for i loop in align_raw():"); */
518 /* // In this case we revert to the previous column to start the traceback */
519 /* last_col_computed = i-1; */
520
521 /* DEBUGOUT2("raw: last_col_computed reverted to :", last_col_computed); */
522
523 /* break; // This means we leave the for (i=1; i < length; ++i) loop */
524 /* } */
525
526
527 // print_ar_s(std::cerr);
528 // print_ar_bto(std::cerr);
529
530 } // End align()
531
532
533
534
535 int traceback(faststring &alignment, align_coord &ac_start, align_coord &ac_end)
536 {
537 int col, row;
538
539 // Let us determine the starting cooridnates for the backtracking procedure. Later this will be stored in ac_end
540 col = l1;
541 row = l2;
542
543 /* if (!free_back_gaps) // global alignment */
544 /* { */
545 /* row = l2; */
546 /* if (row <= 0 || row >= width) */
547 /* { */
548 /* cerr << "Critical out of bounds error: first row index in traceback out of bounds" << endl; */
549 /* exit(1); */
550 /* } */
551 /* } */
552 /* else */
553 /* row = find_max_index_of_col(col); */
554
555 DEBUGOUT2("Starting in col: ", col);
556 DEBUGOUT2("Starting in row: ", row);
557
558 ac_end.col = col;
559 ac_end.row = row;
560
561 alignment_score = ar_s[col][row];
562
563 align_coord curr_ac(col, row);
564
565 // Initialise last_ac. Otherwise it might be used uninitialized.
566 align_coord p1, p2, p3, last_ac = ac_end;
567 bool end_fixed_free_end_gaps = false;
568 bool start_fixed_free_front_gaps = false;
569
570 while (curr_ac.col > 0 || curr_ac.row > 0)
571 {
572 /* if (curr_ac.col == 1) */
573 /* { */
574 /* cout << "COORD: "; */
575 /* curr_ac.print(cout); */
576 /* cout << endl; */
577 /* } */
578
579 DEBUGCODE(bool match;)
580
581
582 DEBUGCODE(
583 cerr << "curr_ac: ";
584 curr_ac.print(cerr);
585 cerr << "Matrix value: " << ar_s[curr_ac.col][curr_ac.row];
586 cerr << endl;
587 )
588
589 p1.col = curr_ac.col - 1;
590 p1.row = curr_ac.row - 1;
591
592 p2.col = curr_ac.col-1;
593 p2.row = curr_ac.row; // horizontal (p2, 3rd bit, gap in s2)
594
595 p3.col = curr_ac.col; // vertical (p3, 4th bit, gap in s1)
596 p3.row = curr_ac.row-1;
597
598 DEBUGCODE(
599 match = (ar_bto[curr_ac.col][curr_ac.row]&1);
600
601 cerr << "Potential preds: ";
602 cerr << "p1 ";
603 p1.print(cerr);
604
605 cerr << "p2 ";
606 p2.print(cerr);
607
608 cerr << " p3 ";
609 p3.print(cerr);
610
611 cerr << endl;
612
613 if (ar_bto[curr_ac.col][curr_ac.row]&1)
614 cerr << "Match" << endl;
615 if (ar_bto[curr_ac.col][curr_ac.row]&2)
616 cerr << "Mismatch" << endl;
617 if (ar_bto[curr_ac.col][curr_ac.row]&4)
618 cerr << "gap s2" << endl;
619 if (ar_bto[curr_ac.col][curr_ac.row]&8)
620 cerr << "gap s1" << endl;
621
622
623 cerr << "Compare:" << endl;
624 cerr << "Answer: " << ar_s[curr_ac.col][curr_ac.row] << endl;
625 if (p1.valid(l1,l2) )
626 {
627 // cerr << " match? " << ar_s[p1.col][p1.row] << "+" << match_score << endl;
628 // cerr << "mismatch? " << ar_s[p1.col][p1.row] << "-" << mis_pen << endl;
629 }
630 else
631 cerr << " p1 is out of bounds. That is OK if we are in the first row or column." << endl;
632
633 if (p2.valid(l1,l2) )
634 cerr << " p2? " << ar_s[p2.col][p2.row] << "-" << gap_ext << endl;
635 else
636 cerr << " p2 is out of bounds. That is OK if we are in the first row or column." << endl;
637 if (p3.valid(l1,l2) )
638 cerr << " p3? " << ar_s[p3.col][p3.row] << "-" << gap_ext << endl;
639 else
640 cerr << " p3 is out of bounds. That is OK if we are in the first row or column." << endl;
641 );
642
643
644 // New version for finding the traceback
645
646 DEBUGCODE(if (ar_bto[curr_ac.col][curr_ac.row]==0)
647 {
648 cerr << "Error. Tracebackvalue == 0"<< endl;
649 exit(1);
650 }
651 );
652
653 DEBUGOUT2("ar_bto[curr_ac.col][curr_ac.row] = ",char(ar_bto[curr_ac.col][curr_ac.row]+'0'));
654
655 if (ar_bto[curr_ac.col][curr_ac.row]&1) // If this is true, this was a match
656 {
657 DEBUGOUT1("Choosing match (p1)");
658 alignment.push_back('M');
659 curr_ac = p1;
660 }
661 else if (ar_bto[curr_ac.col][curr_ac.row]&2)
662 {
663 DEBUGOUT1("Choosing mismatch (p1)");
664 alignment.push_back('m');
665 curr_ac = p1;
666 }
667 else if (ar_bto[curr_ac.col][curr_ac.row]&4)
668 {
669 DEBUGOUT1("Choosing gap s2 (p2)"); // left <- | gap in s2 | 'i' means: relative insertion in s1.
670 alignment.push_back('i');
671 curr_ac = p2;
672 }
673 else if (ar_bto[curr_ac.col][curr_ac.row]&8)
674 {
675 DEBUGOUT1("Choosing gap s1 (p3)"); // up ^ | gap in s1 | 'd' means: relative deletion in s1.
676 alignment.push_back('d');
677 curr_ac = p3;
678 }
679 else
680 {
681 cerr << "Critical error in traceback_raw_alignment: No succ found at: ";
682 curr_ac.print(cerr);
683 cerr << endl;
684 exit(0);
685 }
686 // End: New version for finding the traceback
687
688 // In the case of free end gaps we have to find the end of the
689 // alignment dynamically. We enter as long as !end_fixed_free_end_gaps
690
691 if (free_back_gaps && !end_fixed_free_end_gaps)
692 {
693 if (alignment_score != ar_s[curr_ac.col][curr_ac.row] )
694 {
695 ac_end = last_ac;
696 end_fixed_free_end_gaps = true;
697 }
698 }
699 // else ac_end is l1, l2
700
701 if (free_front_gaps && !start_fixed_free_front_gaps)
702 {
703 if (curr_ac.col == 0 || curr_ac.row == 0)
704 {
705 ac_start = curr_ac;
706 start_fixed_free_front_gaps = true;
707 }
708 }
709 else if (!free_front_gaps)
710 {
711 ac_start = curr_ac; // Always the last enty has to be stored.
712 }
713 last_ac = curr_ac;
714 }
715 return alignment_score;
716 }
717
718
719 // Requires alignment mode 1 (local) for expected results.
720 void get_respective_start_end_coordinates(int &s2_in_s1_start,
721 int &s2_in_s1_end,
722 int &s1_in_s2_start,
723 int &s1_in_s2_end,
724 align_coord a,
725 align_coord e,
726 int l1,
727 int l2,
728 faststring &alignment)
729 {
730 if (a.col > a.row)
731 {
732 s2_in_s1_start = a.col;
733 s1_in_s2_start = -a.col;
734 }
735 else
736 {
737 s2_in_s1_start = -a.row;
738 s1_in_s2_start = a.row;
739 }
740
741 if (*(alignment.begin()) == 'i')
742 {
743 s1_in_s2_end = -(l1 - e.col);
744 s2_in_s1_end = e.col;
745 }
746 else if (*(alignment.begin()) == 'd')
747 {
748 s1_in_s2_end = e.row;
749 s2_in_s1_end = -(l2 - e.row);
750 }
751 else
752 {
753 s1_in_s2_end = l2;
754 s2_in_s1_end = l1;
755 }
756 }
757
758
759
760 void alignment_strings(faststring &line1, faststring &line2, faststring &line3, faststring alignment)
761 {
762 line1.clear();
763 line2.clear();
764 line3.clear();
765
766 const char *i_al, *i_al_end;
767
768 const char *ps1 = s1;
769 const char *ps2 = s2;
770
771 i_al = alignment.rbegin();
772 i_al_end = alignment.rend();
773
774 // Delete:
775 // int num_m_M = 0;
776 // int s1;
777
778 while (i_al != i_al_end)
779 {
780 if (*i_al == 'M') // Match
781 {
782 line1.push_back(*ps1);
783 ++ps1;
784 line3.push_back('|');
785 line2.push_back(*ps2);
786 ++ps2;
787 // ++num_m_M;
788 }
789 else if (*i_al == 'm') // mismatch
790 {
791 line1.push_back(*ps1);
792 ++ps1;
793 line3.push_back(' ');
794 line2.push_back(*ps2);
795 ++ps2;
796 // ++num_m_M;
797 }
798 else if (*i_al == 'i') // gap in s2, or insertion in s1
799 {
800 line1.push_back(*ps1);
801 ++ps1;
802 line3.push_back(' ');
803 line2.push_back('-');
804 }
805 else if (*i_al == 'd') // gap in s1, or insertion in s2
806 {
807 line1.push_back('-');
808 line3.push_back(' ');
809 line2.push_back(*ps2);
810 ++ps2;
811 }
812 --i_al;
813 }
814 }
815
816 int get_alignment_score()
817 {
818 return alignment_score;
819 }
820
821 // NEW
822 // Result only verified for mode==1
823 void coords_of_s1_in_al_string(faststring &alignment,
824 align_coord ac_start,
825 align_coord ac_end,
826 int len1,
827 int len2,
828 unsigned &s,
829 unsigned &e)
830 {
831 int s2_in_s1_start;
832 int s2_in_s1_end;
833 int s1_in_s2_start;
834 int s1_in_s2_end;
835
836 get_respective_start_end_coordinates(s2_in_s1_start,
837 s2_in_s1_end,
838 s1_in_s2_start,
839 s1_in_s2_end,
840 ac_start,ac_end,
841 len1, len2,
842 alignment);
843
844 if (s2_in_s1_start < 0)
845 s = 0;
846 else
847 s = s2_in_s1_start;
848
849 if (s1_in_s2_end < 0) // s1 extends beyond s2 in alignment at its end.
850 e = alignment.length() + s1_in_s2_end;
851 // If s1 does not extend beyond s2 at its end, s2 goes till the end:
852 else // s2_in_s1_end < 0 || s2_in_s1_end > 0 && s1_in_s2_end > 0
853 // s2_in_s1_end < 0: s2 extends beyond s1 in alignment at its end.
854 // s2_in_s1_end > 0 && s1_in_s2_end > 0: end simultanious.
855 e = alignment.length();
856 }
857
858 // NEW
859 // Usually used for mode==1 only!
860 void al_perfection(faststring &alignment,
861 align_coord ac_start,
862 align_coord ac_end,
863 int len1,
864 int len2,
865 unsigned &len, // alignment covering s1
866 unsigned &matches, //
867 unsigned &mismatches, //
868 unsigned &gaps) //
869 {
870 unsigned s,e; // Start and end in alignment string
871
872 unsigned al_len = alignment.length();
873
874 coords_of_s1_in_al_string(alignment,
875 ac_start,
876 ac_end,
877 len1,
878 len2,
879 s,
880 e);
881
882 if (s > e)
883 {
884 cerr << "Internal error: s>e in method al_perfection is not possible." << endl;
885 exit(-33);
886 }
887
888 if (e > al_len)
889 {
890 cerr << "Internal error: e>alignment.length() in method al_perfection is not possible." << endl;
891 exit(-33);
892 }
893
894
895 len = e - s;
896 matches = 0;
897 mismatches = 0;
898 gaps = 0;
899
900 unsigned i, N;
901 char c;
902
903 i = al_len-e;
904 N = al_len-s;
905
906 for (; i<N; ++i)
907 {
908 c = alignment[i];
909 if (c == 'M')
910 ++matches;
911 else if (c == 'm')
912 ++mismatches;
913 else
914 ++gaps;
915 }
916 }
917
918 };
919
920 ///////
921
922
923 inline void pretty_print_alignment(FILE *of, faststring &line1, faststring &line2, faststring &line3, int char_per_line=50)
924 {
925 // 0 . : . : . : . : . :
926 faststring top_str = " . : . : . : . : . :";
927
928 int i=50;
929 while (i<char_per_line)
930 {
931 i += char_per_line;
932 top_str += " . : . : . : . : . :";
933 }
934
935 unsigned len = line1.size();
936 unsigned pos = 0;
937 unsigned back_pos = pos + char_per_line;
938
939 const char* l1 = line1.c_str();
940 const char* l2 = line2.c_str();
941 const char* l3 = line3.c_str();
942
943 unsigned n_print_now;
944 while (pos < len)
945 {
946 back_pos = pos + char_per_line;
947
948 if (back_pos > len)
949 {
950 back_pos = len;
951 }
952 n_print_now = (unsigned)(back_pos - pos);
953
954 // fprintf(of, "debug: %d\n", n_print_now);
955
956 fprintf(of, "%7d %.*s\n", pos+1, n_print_now, top_str.data());
957 fprintf(of, " %.*s\n", n_print_now, l1+pos);
958 fprintf(of, " %.*s\n", n_print_now, l3+pos);
959 fprintf(of, " %.*s\n\n", n_print_now, l2+pos);
960
961 pos += char_per_line;
962
963 }
964 }
965
966 inline void pretty_print_alignment_base0(FILE *of, faststring &line1, faststring &line2, faststring &line3, int char_per_line=50)
967 {
968 // 0 . : . : . : . : . :
969 faststring top_str = " . : . : . : . : . :";
970
971 int i=50;
972 while (i<char_per_line)
973 {
974 i += char_per_line;
975 top_str += " . : . : . : . : . :";
976 }
977
978 unsigned len = line1.size();
979 unsigned pos = 0;
980 unsigned back_pos = pos + char_per_line;
981
982 const char* l1 = line1.c_str();
983 const char* l2 = line2.c_str();
984 const char* l3 = line3.c_str();
985
986 unsigned n_print_now;
987 while (pos < len)
988 {
989 back_pos = pos + char_per_line;
990
991 if (back_pos > len)
992 {
993 back_pos = len;
994 }
995 n_print_now = (unsigned)(back_pos - pos);
996
997 // fprintf(of, "debug: %d\n", n_print_now);
998
999 fprintf(of, "%7d %.*s\n", pos, n_print_now, top_str.data());
1000 fprintf(of, " %.*s\n", n_print_now, l1+pos);
1001 fprintf(of, " %.*s\n", n_print_now, l3+pos);
1002 fprintf(of, " %.*s\n\n", n_print_now, l2+pos);
1003
1004 pos += char_per_line;
1005
1006 }
1007 }
1008
1009 #endif