the backtrack step in smith_waterman
| 94 | |
| 95 | //the backtrack step in smith_waterman |
| 96 | unsigned Backtrack(const int i_max, const int j_max, int** I_i, int** I_j, |
| 97 | const string& seq_a, const string& seq_b, SMAlignment& align, unsigned* align_pos) |
| 98 | { |
| 99 | // Backtracking from H_max |
| 100 | int current_i=i_max,current_j=j_max; |
| 101 | int next_i=I_i[current_i][current_j]; |
| 102 | int next_j=I_j[current_i][current_j]; |
| 103 | string consensus_a(""), consensus_b(""), match(""); |
| 104 | unsigned num_of_match = 0; |
| 105 | while(((current_i!=next_i) || (current_j!=next_j)) && (next_j!=0) && (next_i!=0)){ |
| 106 | if(next_i==current_i) { |
| 107 | consensus_a += '-'; //deletion in A |
| 108 | match += tolower(seq_b[current_j-1]); |
| 109 | consensus_b += seq_b[current_j-1]; //b must be some actual char, cannot be '-' aligns with '-'! |
| 110 | } |
| 111 | else { |
| 112 | consensus_a += seq_a[current_i-1]; // match/mismatch in A |
| 113 | if(next_j==current_j) { |
| 114 | consensus_b += '-'; // deletion in B |
| 115 | match += tolower(seq_a[current_i-1]); |
| 116 | } |
| 117 | else { |
| 118 | consensus_b += seq_b[current_j-1]; // match/mismatch in B |
| 119 | char consensus_char; |
| 120 | if (isMatch(seq_a[current_i-1], seq_b[current_j-1], |
| 121 | consensus_char)) { |
| 122 | match += consensus_char; |
| 123 | num_of_match++; |
| 124 | } |
| 125 | else { |
| 126 | match += ambiguityOr( |
| 127 | seq_a[current_i-1], seq_b[current_j-1]); |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | current_i = next_i; |
| 133 | current_j = next_j; |
| 134 | next_i=I_i[current_i][current_j]; |
| 135 | next_j=I_j[current_i][current_j]; |
| 136 | } |
| 137 | |
| 138 | //check whether the alignment is what we want (pinned at the ends), modified version of SW (i_max is already fixed) |
| 139 | if (current_j > 1) |
| 140 | return 0; |
| 141 | |
| 142 | //record the last one |
| 143 | consensus_a += seq_a[current_i-1]; |
| 144 | consensus_b += seq_b[current_j-1]; |
| 145 | char consensus_char; |
| 146 | if (isMatch(seq_a[current_i-1], seq_b[current_j-1], |
| 147 | consensus_char)) { |
| 148 | match += consensus_char; |
| 149 | num_of_match++; |
| 150 | } |
| 151 | else { |
| 152 | match += ambiguityOr(seq_a[current_i-1], seq_b[current_j-1]); |
| 153 | } |
no test coverage detected