找到兩個基因組序列中最長的子串

我有兩個序列AAAAAAAAAGAAAAGAAGAAG，AAAGAAG。正確答案是AAGAAG。找到兩個基因組序列中最長的子串

但是我的代碼給了AA。

還有時候兩個字符串按照AAAGAAG，AAAAAAAAAGAAAAGAAGAAG的順序排列。

這裏是我的代碼

`def longestSubstringFinder(string1, string2): 
    string1=string1.strip() 
    string2=string2.strip() 
    answer = "" 
    len1=len(string1) 
    len2=len(string2) 
    if int(len1)>1 and int(len2)>1: 
     for i in range(1,len1,1): 
      match = "" 
      for j in range(len2): 
       if len1>len2: 
        if i+j<len1 and (string1[i+j]==string2[i+j]): 
         match=str(match)+str(string2[i+j]) 
         print(match) 
        else: 
         if len(match)>len(answer): 
          answer=match 
          match="" 
       elif len2>len1: 
        if i+j<len2 and (string1[i+j]==string2[i+j]): 
         match=str(match)+str(string2[i+j]) 
         print(match) 
        else: 
         if len(match)>len(answer): 
          answer=match 
          match="" 
    return(answer)`

來源

2017-08-28 Vignesh

請提供一個工作的例子，人們可以複製到自己的編輯器。 – Joe

您的第二個字符串實際上是第一個字符串的一部分..它從第一個字符串的末尾結束3個字符 – AK47

[在兩個字符串之間查找公共子字符串]可能的重複（https://stackoverflow.com/questions/18715688/find -common-substring-between-two-strings） –

獲取兩個字符串的所有串，發現這兩組子的交集，然後找到在路口最大的字符串

def get_all_substrings(input_string): 
    length = len(input_string) 
    return [input_string[i:j+1] for i in range(length) for j in range(i,length)] 

strA = 'AAAAAAAAAGAAAAGAAGAAG' 
strB = 'AAAGAAG' 

intersection = set(get_all_substrings(strA)).intersection(set(get_all_substrings(strB))) 
print(max(intersection, key=len)) 
>> 'AAAGAAG'

來源

2017-08-28 13:15:02 AK47

這是短而智能的：） –

這是設置方法的一個很好的用法。爲了減少計算複雜度，特別是考慮到其中一個字符串潛在地相當長，可能會把它變成一個字符串比較函數，用'maxlength = max（len（input_string1），len（input_string2））'來限制最大子串？ – Uvar

幾個星期以前我偶然發現了Python中的difflib包，它對於這類工作來說非常完美。

這裏是你的問題的解決方案：

import difflib 
matcher = difflib.SequenceMatcher() 

str1 = 'AGAGGAG' 
str2 = 'AAAAAAAAAGAAAAGAAGAAG' 
matcher.set_seq2(str2) 
matcher.set_seq1(str1) 

m = matcher.find_longest_match(0, len(str1), 0, len(str2)) 
print("Longest sequence of {} found in {}: {}".format(str1, str2, str1[m.a: m.a+m.size])) 
# Longest sequence of AAAGAAG found in AAAAAAAAAGAAAAGAAGAAG: AAAGAAG 
print(str2[:m.b]+'|'+str2[m.b:m.b+m.size]+'|'+str2[m.b+m.size:]) 
# AAAAAAAAAGA|AAAGAAG|AAG 

str1 = 'AGAG' 

matcher.set_seq1(str1) 

m = matcher.find_longest_match(0, len(str1), 0, len(str2)) 
print("Longest sequence of {} found in {}: {}".format(str1, str2, str1[m.a: m.a+m.size])) 
# Longest sequence of AGAG found in AAAAAAAAAGAAAAGAAGAAG: AGA 
print(str2[:m.b]+'|'+str2[m.b:m.b+m.size]+'|'+str2[m.b+m.size:]) 
# AAAAAAAA|AGA|AAAGAAGAAG 

str1 = 'XXX' 

matcher.set_seq1(str1) 

m = matcher.find_longest_match(0, len(str1), 0, len(str2)) 
print("Longest sequence of {} found in {}: {}".format(str1, str2, str1[m.a: m.a+m.size])) 
# Longest sequence of XXX found in AAAAAAAAAGAAAAGAAGAAG: 
print(str2[:m.b]+'|'+str2[m.b:m.b+m.size]+'|'+str2[m.b+m.size:]) 
# ||AAAAAAAAAGAAAAGAAGAAG

的文檔says：

SequenceMatcher計算和緩存有關的第二順序的詳細信息，所以如果你想進行比較的一個序列許多序列，使用set_seq2（）來設置常用序列一次，並且重複地調用set_seq1（），每個其他序列一次。

而且速度也非常快！

我已經超時@AK47大solution並定時10000 loops, best of 3: 85.2 µs per loop

我的解決方案定時10000 loops, best of 3: 31.6 µs per loop

來源

2017-10-10 20:23:06

找到兩個基因組序列中最長的子串

回答

相關問題