Code: Alles auswählen
#!/usr/bin/env python
# coding: utf-8
"""Ported from a piece of Perl code.
"""
from collections import defaultdict
BONDS = dict(GU=1, UG=1, AU=2, UA=2, CG=3, GC=3)
def fold(rna):
c = defaultdict(int)
for length in xrange(5, len(rna) + 1):
for i in xrange(0, len(rna) - length + 1):
j = i + length - 1
c[i, j] = max(c[i + 1, j],
BONDS.get(rna[i] + rna[j], 0) + c[i + 1, j - 1],
max(c[i, k] + c[k + 1, j] for k in xrange(i + 1, j)))
return c
def trace_back(rna):
c = fold(rna)
def _trace_back(i, j):
c_ij = c[i, j]
if c_ij == 0:
result = '.' * (j - i + 1)
elif c_ij == c[i + 1, j]:
result = '.' + _trace_back(i + 1, j)
elif c_ij == BONDS.get(rna[i] + rna[j], 0) + c[i + 1, j - 1]:
result = '(' + _trace_back(i + 1, j -1) + ')'
else:
for k in xrange(i + 1, j):
if c_ij == c[i, k] + c[k + 1, j]:
result = _trace_back(i, k) + _trace_back(k + 1, j)
break
else:
assert False
return result
result = _trace_back(0, len(rna) - 1)
assert len(result) == len(rna)
return result
def main():
rna = ('CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGA'
'UCGGGCGUUCGACUCGCCCCCGGGAGACCA')
expected = ('.((((((...))(((((((((((..(...))))))(((...)..)))(...)))))'
')))))(((((.(..((...)).)))))((...)))')
result = trace_back(rna)
print rna
print result
print result == expected
if __name__ == '__main__':
main()