r""" Perform traceback to find the optimal local alignment. Starts from the highest scoring cell in the matrix and traces back recursively until a 0 score is found. Returns the alignment strings. >>> traceback([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]], 'ACAC', 'CA')
(score: list[list[int]], query: str, subject: str)
| 127 | |
| 128 | |
| 129 | def traceback(score: list[list[int]], query: str, subject: str) -> str: |
| 130 | r""" |
| 131 | Perform traceback to find the optimal local alignment. |
| 132 | Starts from the highest scoring cell in the matrix and traces back recursively |
| 133 | until a 0 score is found. Returns the alignment strings. |
| 134 | >>> traceback([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]], 'ACAC', 'CA') |
| 135 | 'CA\nCA' |
| 136 | >>> traceback([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]], 'acac', 'ca') |
| 137 | 'CA\nCA' |
| 138 | >>> traceback([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]], 'ACAC', 'ca') |
| 139 | 'CA\nCA' |
| 140 | >>> traceback([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]], 'acac', 'CA') |
| 141 | 'CA\nCA' |
| 142 | >>> traceback([[0, 0, 0]], 'ACAC', '') |
| 143 | '' |
| 144 | """ |
| 145 | # make both query and subject uppercase |
| 146 | query = query.upper() |
| 147 | subject = subject.upper() |
| 148 | # find the indices of the maximum value in the score matrix |
| 149 | max_value = float("-inf") |
| 150 | i_max = j_max = 0 |
| 151 | for i, row in enumerate(score): |
| 152 | for j, value in enumerate(row): |
| 153 | if value > max_value: |
| 154 | max_value = value |
| 155 | i_max, j_max = i, j |
| 156 | # Traceback logic to find optimal alignment |
| 157 | i = i_max |
| 158 | j = j_max |
| 159 | align1 = "" |
| 160 | align2 = "" |
| 161 | gap = score_function("-", "-") |
| 162 | # guard against empty query or subject |
| 163 | if i == 0 or j == 0: |
| 164 | return "" |
| 165 | while i > 0 and j > 0: |
| 166 | if score[i][j] == score[i - 1][j - 1] + score_function( |
| 167 | query[i - 1], subject[j - 1] |
| 168 | ): |
| 169 | # optimal path is a diagonal take both letters |
| 170 | align1 = query[i - 1] + align1 |
| 171 | align2 = subject[j - 1] + align2 |
| 172 | i -= 1 |
| 173 | j -= 1 |
| 174 | elif score[i][j] == score[i - 1][j] + gap: |
| 175 | # optimal path is a vertical |
| 176 | align1 = query[i - 1] + align1 |
| 177 | align2 = f"-{align2}" |
| 178 | i -= 1 |
| 179 | else: |
| 180 | # optimal path is a horizontal |
| 181 | align1 = f"-{align1}" |
| 182 | align2 = subject[j - 1] + align2 |
| 183 | j -= 1 |
| 184 | |
| 185 | return f"{align1}\n{align2}" |
| 186 |
no test coverage detected