INT102-Local-Alignment

 1 import numpy as np
 2 
 3 
 4 def update(a: int, b: int, c: int) -> tuple:
 5     if a > b and a > c and a > 0:
 6         return a, "↖"
 7     if b > a and b > c and b > 0:
 8         return b, "↑"
 9     if c > a and c > b and c > 0:
10         return c, "←"
11     return 0, " "
12 
13 
14 def mapping(c: str) -> int:
15     if c == "A":
16         return 0
17     elif c == "C":
18         return 1
19     elif c == "G":
20         return 2
21     else:
22         return 3
23 
24 
25 def local_alignment(S: list, d: int, X: str, Y: str) -> tuple:
26     n, m = len(X), len(Y)
27     dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
28     flag = [[" " for j in range(m + 1)] for i in range(n + 1)]
29     for j in range(m):
30         dp[0][j + 1] = max(dp[0][j] + d, 0)
31     for i in range(n):
32         dp[i + 1][0] = max(dp[i][0] + d, 0)
33     for i in range(1, n + 1, 1):
34         for j in range(1, m + 1, 1):
35             a = mapping(X[i - 1])
36             b = mapping(Y[j - 1])
37             dp[i][j], flag[i][j] = update(dp[i - 1][j - 1] + S[a][b], dp[i - 1][j] + d, dp[i][j - 1] + d)
38     return dp, flag
39 
40 
41 if __name__ == '__main__':
42     X = "GAGT"
43     Y = "AGACCT"
44     S = [#A   C   G   T
45         [ 1, -3, -2, -3],  # A
46         [-3,  1, -3, -2],  # C
47         [-2, -3,  1, -3],  # G
48         [-3, -2, -3,  1]   # T
49     ]
50     dp, flag = local_alignment(S, -1, X, Y)
51     print(np.array(dp))
52     print(np.array(flag))
~~Jason_liu O(∩_∩)O