找到两个基因组序列中最长的子串

Question

我有两个序列aaaaaaaaaagagaag，AAAGAAG。 正确答案是AAGAAG。在

但我的密码是AA。在

也会有两个字符串的顺序是AAAGAAG，aaaaaaaaaagagaag。在

这是我的密码

`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)`

Answer 1

得到两个字符串的所有子字符串，找到这两组子字符串的交集，然后找到交集中最大的字符串

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'

Answer 2

几周前，我偶然发现了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

difflib文档says：

SequenceMatcher computes and caches detailed information about the second sequence, so if you want to compare one sequence against many sequences, use set_seq2() to set the commonly used sequence once and call set_seq1() repeatedly, once for each of the other sequences.

而且速度也很快！在

我已经计时了@AK47很好solution，它计时了{}

我的解决方案计时10000 loops, best of 3: 31.6 µs per loop