-
Notifications
You must be signed in to change notification settings - Fork 1
/
LCS.py
101 lines (71 loc) · 1.87 KB
/
LCS.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
#!/usr/bin/env python
'''
LCS example
'''
__author__ = 'Sergio García Prado'
__version__= '1.0'
def max(a, b):
return a if (a > b) else b
def lcs(X, Y, m, n):
"""
LCS Algorithm
The Algorithm returns the Longest Common Subsequence of X and Y.
@type X: list
@param X: The First Sequence.
@type Y: list
@param Y: The Second Sequence.
@type m: number
@param m: Len of First Sequence.
@type X: number
@param X: Len of Second Sequence.
@rtype: list
@return: the Longest Common Subsequence of two input Sequences.
"""
L = [[0 for col in range(n+1)] for row in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if (X[i-1] ==Y[j-1]):
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
#return L[m][n]
index = L[m][n]
lcs = list(" " * index)
i = m
j = n
while(i > 0 and j > 0):
if (X[i-1] == Y[j-1]):
lcs[index-1] = X[i-1]
i -= 1
j -= 1
index -= 1
elif (L[i-1][j] > L[i][j-1]):
i -= 1
else:
j -= 1
return "".join(lcs)
def main():
"""
Main method.
It initializes the app. Also acts as IO.
If input is none it uses
ACCGGTGGACAATTCA as X and
GGAAAGAGATATGCAC as Y
Then rerurn LCS of it.
"""
X = "ACCGGTGGACAATTCA";
Y = "GGAAAGAGATATGCAC";
Xinput = raw_input('Introduzca la primera secuencia:')
Yinput = raw_input('Introduzca la segunda secuencia:')
if(Xinput != ""):
X = Xinput
if(Yinput != ""):
Y = Yinput
m = len(X);
n = len(Y);
print "La primera secuencia es: %s" % (X)
print "La segunda secuencia es: %s" % (Y)
l = lcs( X, Y, m, n )
print"LCS es '%s' y su longitud es %s" % (l, len(l) )
if __name__ == "__main__":
main()