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))
