-
Notifications
You must be signed in to change notification settings - Fork 0
/
REAR.py
109 lines (94 loc) · 3.39 KB
/
REAR.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
"""
Reversal Distance
Solved September 7, 2017
"""
import FileOperations as f
from itertools import permutations
from FrequentOperations import CountBreakagePoints
from FrequentOperations import TransformIndex
# Reversal Distance
def GenerateReversals(q):
""" Generates all possible reversals of a given permutation """
reversals = []
pairs = list(permutations([x for x in range(11)],2))
# remove pairs where j < i
newpairs = []
for tup in pairs:
if tup[0] +1 < tup[1]:
newpairs.append(tup)
pairs = newpairs
for i,j in pairs:
newq = q[:i] + list(reversed(q[i:j])) + q[j:]
if newq != q:
reversals.append(newq)
return reversals
def Generate2Reversals(q):
""" Generates all possible *double* reversals of a given permutation
Used if no breakage points removed from a single reversal"""
reversals2 = []
reversals = GenerateReversals(q)
pairs = list(itertools.permutations([x for x in range(11)],2))
# remove pairs where j < i
newpairs = []
for tup in pairs:
if tup[0] +1 < tup[1]:
newpairs.append(tup)
pairs = newpairs
for pattern in reversals:
for i,j in pairs:
newpattern = pattern[:i] + list(reversed(pattern[i:j])) + pattern[j:]
if newpattern != pattern:
reversals2.append(newpattern)
return reversals2
def ReversalDistance(p,q):
""" Computes reversal distance from p to q """
q = TransformIndex(p,q)
# If p & q are equal, distance = 0
if p == q:
return 0
else:
distance = 0
while CountBreakagePoints(q) != 0:
breakage = CountBreakagePoints(q)
# Generate all the possible reversals
reversals = GenerateReversals(q)
# Go through each one
# Find the one that removes the most breakage points
minbreakage = breakage
for pattern in reversals:
if CountBreakagePoints(pattern) < minbreakage:
q = pattern
minbreakage = CountBreakagePoints(pattern)
"""If no closer pattern can be found...
generate all possible 2 reversals and try again"""
if minbreakage == breakage:
distance += 1
reversals = Generate2Reversals(q)
for pattern in reversals:
if CountBreakagePoints(pattern) < minbreakage:
q = pattern
minbreakage = CountBreakagePoints(pattern)
# Replace q with closer pattern, repeat until q == p
distance += 1
return str(distance)
def FindReversalDistances():
""" Computes multiple reversal distances
between several pairs of strings """
input = f.LoadFile('\\rosalind_rear.txt').splitlines()
k = len(input)
p_str = [input[i].split() for i in range(0,k+1,3)]
q_str = [input[i].split() for i in range(1,k+1,3)]
p_all = []
q_all = []
for line in p_str:
p_all.append([int(x) for x in line])
for line in q_str:
q_all.append([int(x) for x in line])
distances = []
for i in range(len(p_all)):
p = p_all[i]
q = q_all[i]
distances.append(ReversalDistance(p,q))
f.ExportToFile('rosalind_rear_output.txt',' '.join(distances))
return
FindReversalDistances()