-
Notifications
You must be signed in to change notification settings - Fork 121
/
024_LGIS.py
70 lines (50 loc) · 1.76 KB
/
024_LGIS.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
#!/usr/bin/env python
'''
A solution to a ROSALIND bioinformatics problem.
Problem Title: Longest Increasing Subsequence
Rosalind ID: LGIS
Rosalind #: 024
URL: http://rosalind.info/problems/lgis/
'''
from math import ceil
def BinarySearchLEQ(S, data, value):
'''Use a binary search to return the index of the smallest item in 'S' greater than or equal to 'value'.'''
original_S = S
while len(S)>1:
# index is the exact middle if odd, and the lower value if even.
index = int(ceil(len(S)/2.0 - 1))
if data[S[index]] < value:
S = S[index+1:]
else:
S = S[:index+1]
return original_S.index(S[0])
def LongestIncSubstring(data):
'''Returns an ordered list of the longest increasing substring.'''
S = [0]
parent = [None]*len(data)
for index in range(1,len(data)):
if data[index] > data[S[len(S)-1]]:
parent[index] = S[len(S)-1]
S.append(index)
else:
update_index = BinarySearchLEQ(S, data, data[index])
S[update_index] = index
parent[index] = S[update_index-1]
# Get the indicies of each element in the longest increasing subsequence in reverse order.
LIS = [S[len(S)-1]]
for i in range(0,len(S)-1):
LIS.append(parent[LIS[len(LIS)-1]])
# Convert indicies to values and reverse.
LIS = [data[i] for i in LIS]
LIS.reverse()
return LIS
if __name__ == '__main__':
with open('data/rosalind_lgis.txt') as input_data:
perm = map(int, input_data.readlines()[1].split())
LIS = map(str, LongestIncSubstring(perm))
# The longest decreasing subsequence is just the longest increasing subsequence of -1*permutation.
negperm = [-1*i for i in perm]
LDS = map(str, [-1*i for i in LongestIncSubstring(negperm)])
with open('output/024_LGIS.txt', 'w') as output_data:
output_data.write(' '.join(LIS) + '\n')
output_data.write(' '.join(LDS))