Perform the Smith-Waterman local sequence alignment algorithm. Returns a 2D list representing the score matrix. Each value in the matrix corresponds to the score of the best local alignment ending at that point. >>> smith_waterman('ACAC', 'CA') [[0, 0, 0], [0, 0, 1], [0, 1, 0],
(
query: str,
subject: str,
match: int = 1,
mismatch: int = -1,
gap: int = -2,
)
| 37 | |
| 38 | |
| 39 | def smith_waterman( |
| 40 | query: str, |
| 41 | subject: str, |
| 42 | match: int = 1, |
| 43 | mismatch: int = -1, |
| 44 | gap: int = -2, |
| 45 | ) -> list[list[int]]: |
| 46 | """ |
| 47 | Perform the Smith-Waterman local sequence alignment algorithm. |
| 48 | Returns a 2D list representing the score matrix. Each value in the matrix |
| 49 | corresponds to the score of the best local alignment ending at that point. |
| 50 | >>> smith_waterman('ACAC', 'CA') |
| 51 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 52 | >>> smith_waterman('acac', 'ca') |
| 53 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 54 | >>> smith_waterman('ACAC', 'ca') |
| 55 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 56 | >>> smith_waterman('acac', 'CA') |
| 57 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 58 | >>> smith_waterman('ACAC', '') |
| 59 | [[0], [0], [0], [0], [0]] |
| 60 | >>> smith_waterman('', 'CA') |
| 61 | [[0, 0, 0]] |
| 62 | >>> smith_waterman('ACAC', 'CA') |
| 63 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 64 | |
| 65 | >>> smith_waterman('acac', 'ca') |
| 66 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 67 | |
| 68 | >>> smith_waterman('ACAC', 'ca') |
| 69 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 70 | |
| 71 | >>> smith_waterman('acac', 'CA') |
| 72 | [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 2], [0, 1, 0]] |
| 73 | |
| 74 | >>> smith_waterman('ACAC', '') |
| 75 | [[0], [0], [0], [0], [0]] |
| 76 | |
| 77 | >>> smith_waterman('', 'CA') |
| 78 | [[0, 0, 0]] |
| 79 | |
| 80 | >>> smith_waterman('AGT', 'AGT') |
| 81 | [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 2, 0], [0, 0, 0, 3]] |
| 82 | |
| 83 | >>> smith_waterman('AGT', 'GTA') |
| 84 | [[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 2, 0]] |
| 85 | |
| 86 | >>> smith_waterman('AGT', 'GTC') |
| 87 | [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 2, 0]] |
| 88 | |
| 89 | >>> smith_waterman('AGT', 'G') |
| 90 | [[0, 0], [0, 0], [0, 1], [0, 0]] |
| 91 | |
| 92 | >>> smith_waterman('G', 'AGT') |
| 93 | [[0, 0, 0, 0], [0, 0, 1, 0]] |
| 94 | |
| 95 | >>> smith_waterman('AGT', 'AGTCT') |
| 96 | [[0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0], [0, 0, 0, 3, 1, 1]] |
no test coverage detected