DNAのステムループの最長の茎を見つける方法

Question

私はDNA配列のステムループで最長の茎を見つけようとしています。ここに私がこれまで持っていたコードがあります。誰かが助けてくれますか？私はPythonには新しく、いくつかの演習を練習しようとしています。

basepairs = {'A':'T', 'C':'G', 'G':'C', 'T':'A'} 

listDNA = 'ATGGGCAT' 
listREV = listDNA[::-1] 

stem = '' 
for i in range(len(listDNA)): 
    for j in range(len(listDNA)): 
     if listDNA[i] == basepairs[listREV[j]]: 
      stem += listDNA[j] 
     else: 
      break 

print stem 

Answer 1

私はexample from wikipediaをとりました。また、その歪みはそれ自身が重なり合うことができないことも考慮に入れましたそれともできますか？

basepairs = {'A':'T', 'C':'G', 'G':'C', 'T':'A'} 

listDNA = 'GACACGGTGCAACTTAGCACCGTGCA' 
listREV = listDNA[::-1] 

longest_stem = '' 
longest_match = '' 
for i in range(len(listDNA)): 
    #print('i = {}'.format(i)) 
    # forward strain order 
    for strain_start in range(len(listDNA)): 
     #print(' start = {}'.format(strain_start)) 
     stem = '' 
     match = '' 
     # stem cannot overlap with itself 
     for n in range((len(listDNA) - i - strain_start)/2): 
      if listDNA[i+n] == basepairs[listREV[i+n]]: 
       #print(' added = {}'.format(listDNA[i+n])) 
       stem += listDNA[i+n] 
       match += listREV[i+n] 
      else: 
       break 
     if len(stem) > len(longest_stem): 
      longest_stem = stem 
      longest_match = match 

print longest_stem 
print longest_match 

出力：

CACGGTGC 
GTGCCACG 

Answer 2

ここはかつてあなたがその長さのないサブ鎖はどこかその逆相補を持っていないプロパティを持つ長さに達する観測を利用した始まり、ややコンパクト版です

basepairs = {'A':'T', 'C':'G', 'G':'C', 'T':'A'} 

def reverseComplement(s): 
    return ''.join(basepairs[b] for b in s[::-1]) 

def longestStem(s): 
    n = len(s) 
    k = int(n/2) #length of longest possible stem 
    candidate = '' 
    i = 1 

    while i <= k and len(candidate) == i - 1: 
     for j in xrange(n-2*i+1): 
      t = s[j:i+j] 
      if reverseComplement(t) in s[i+j:]: 
       candidate = t 
       break 
     i +=1 
    return candidate 

それはあなたのサンプルで動作し、また合理的に迅速にこのようなものを扱うことができます：：他に、より大きな長さを見て無意味です

import random 
s = ''.join(random.choice('ATGC') for i in range(10**4)) 
print longestStem(s) 

しかし、ストランドがかなり長くなると、より洗練されたものに切り替える必要があります。おそらく、O(n)要素をinオペレータに隠しておく辞書ベースのアプローチです。おそらく、幹によって暗黙のうちに形成された樹木を深みに探る深みのある探索。