-
Notifications
You must be signed in to change notification settings - Fork 0
/
Alinhamento-Global-Needleman-Wunsch.py
131 lines (111 loc) · 4.77 KB
/
Alinhamento-Global-Needleman-Wunsch.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import pandas as pd
if __name__ == "__main__":
vertical, horizontal = ('CACCCCCCACGCAAAUGCGUGGCCAGGCCGCAACAUAGCGUCUGACCUGUAGGAUCUUAACGUGCUCGAAGGGCUACAAAAUUCGAGGGCAACACCCUGACGACGAUGGGAGCGACCACGCGAGAAUACUCAUGAAUUCCAUAUGCUACGUACUAAUCUAGGCCACAGGUCAGGGCAGACACAAUGCAAUGGCACGCGCC', 'CACCCCCCACGCAAAUGCGUGGCCAGGCCGCAACAUAGCACAGCGUCUGUAGGAUCUUAACGUGCUCGAAGGGCUACAAAAUUCGAGGGCAACACCCUGACGUCACGACGAUGGGAGCGACCACGCGAGAAUA')
#vertical, horizontal = ('AGCT', 'GCTT')
#vertical, horizontal = ('AGCTAAA', 'GCTTTGCA')
match = 3
mismatch = -1
gap = -2
matriz = []
matrizCaminho = []
###Inicializando matriz###############
for i in range(len(vertical)+2):
aux = []
aux2 = []
for j in range(len(horizontal)+2):
aux.append(0)
aux2.append("")
matriz.append(aux)
matrizCaminho.append(aux2)
matriz[0][0] = ""
matriz[0][1] = ""
matriz[1][0] = ""
for i in range(len(matriz[0])-2):#colocando sequencias na horizontal
matriz[0][i+2] = horizontal[i]
matrizCaminho[0][i+2] = horizontal[i]
matriz[1][i+2] = (i+1)*gap
for j in range(len(matriz[2:])):#colocando sequencias na vertical
matriz[j+2][0] = vertical[j]
matrizCaminho[j+2][0] = vertical[j]
matriz[j+2][1] = (j+1)*gap
########################################
######Preenchendo a matriz##############
diagonal = 0
for i in range(len(matriz)-2):
for j in range(len(matriz[0])-2):
L = i+2
C = j+2
vertical = matriz[L-1][C] + gap
horizontal = matriz[L][C-1] + gap
if (matriz[L][0] == matriz[0][C]):#match
diagonal = matriz[L-1][C-1] + match
elif (matriz[L][0] == "-" or matriz[0][C] == "-"):#gap
diagonal = matriz[L-1][C-1] + gap
else:#matriz[L][0] != matriz[0][C]
diagonal = matriz[L-1][C-1] + mismatch
matriz[L][C] = max(vertical,horizontal,diagonal)
########################################
df = pd.DataFrame(matriz)
df.to_excel("matriz.xlsx",index=False,header=False)
##################backtrace#############
L = len(matriz) -1
C = len(matriz[0]) -1
print("Score:",matriz[L][C])
sequenciaFinalHorizontal = ""
sequenciaFinalVertical = ""
while L >= 1:
try:
if L==1:
raise TypeError
if (matriz[L][0] == matriz[0][C]):#match
matrizCaminho[L][C] = "↖"
sequenciaFinalHorizontal+=matriz[0][C]
sequenciaFinalVertical+=matriz[L][0]
L = L-1
C = C-1
else:
valorVertical = matriz[L-1][C]
valorHorizontal = matriz[L][C-1]
valorDiagonal = matriz[L-1][C-1]
maior = max(valorVertical,valorHorizontal,valorDiagonal)
if maior == valorVertical:
matrizCaminho[L][C] = "↑"
sequenciaFinalHorizontal+="_"
sequenciaFinalVertical+=matriz[L][0]
L = L-1
elif maior == valorHorizontal:
matrizCaminho[L][C] = "←"
sequenciaFinalHorizontal+=matriz[0][C]
sequenciaFinalVertical+="_"
C = C-1
else:
matrizCaminho[L][C] = "↖"
sequenciaFinalHorizontal+=matriz[0][C]
sequenciaFinalVertical+=matriz[L][0]
L = L-1
C = C-1
except TypeError:
if L == 1:
matrizCaminho[L][C] = "*"
else:
matrizCaminho[L][C] = "↑"
sequenciaFinalHorizontal+="_"
sequenciaFinalVertical+=matriz[L][0]
L = L-1
sequenciaFinalVertical = sequenciaFinalVertical[::-1]
sequenciaFinalHorizontal = sequenciaFinalHorizontal[::-1]
print(sequenciaFinalVertical)
for i in range(len(sequenciaFinalVertical)):
if sequenciaFinalVertical[i] == sequenciaFinalHorizontal[i]:
print("*",end="")
elif (sequenciaFinalVertical[i]=="A" and sequenciaFinalHorizontal[i]=="T" or
sequenciaFinalHorizontal[i]=="A" and sequenciaFinalVertical[i]=="T" or
sequenciaFinalVertical[i]=="G" and sequenciaFinalHorizontal[i]=="C" or
sequenciaFinalHorizontal[i]=="C" and sequenciaFinalVertical[i]=="G"):
print("|",end="")
else:
print(" ",end="")
print()
print(sequenciaFinalHorizontal)
df2 = pd.DataFrame(matrizCaminho)
df2.to_excel("matrizCaminho.xlsx",index=False,header=False)