Jak znaleźć nakładkę między 2 sekwencjami i zwrócić je

Question

Jestem nowy w Pythonie i już spędziłem wiele godzin z tym problemem, mam nadzieję, że ktoś może mi pomóc. Muszę znaleźć nakładkę między 2 sekwencjami. Nakładanie się znajduje się na lewym końcu pierwszej sekwencji i na prawym końcu drugiej. Chcę, aby funkcja znalazła zakładkę i zwróciła ją.

Moi sekwencje są:

s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC" 
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC" 

Moja funkcja powinna zostać nazwana

def getOverlap(left, right) 

Z s1 będąc lewo sekwencja, a s2 jest słuszna.

wynik powinien być

‘GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC’ 

Każda pomoc jest mile widziana

Answer 1

Longest Common Substring

def LongestCommonSubstring(S1, S2): 
    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))] 
    longest, x_longest = 0, 0 
    for x in xrange(1,1+len(S1)): 
    for y in xrange(1,1+len(S2)): 
     if S1[x-1] == S2[y-1]: 
      M[x][y] = M[x-1][y-1] + 1 
      if M[x][y]>longest: 
       longest = M[x][y] 
       x_longest = x 
     else: 
      M[x][y] = 0 
    return S1[x_longest-longest: x_longest] 

Answer 2

Algorytm Knuth-Morris-Pratt jest miły sposób na znalezienie jeden ciąg wewnątrz drugiego (od Widziałem DNA, Zgaduję, że chciałbyś, żeby to się skalowało do ... miliardów?).

# Knuth-Morris-Pratt string matching 
# David Eppstein, UC Irvine, 1 Mar 2002 

from __future__ import generators 

def KnuthMorrisPratt(text, pattern): 

    '''Yields all starting positions of copies of the pattern in the text. 
Calling conventions are similar to string.find, but its arguments can be 
lists or iterators, not just strings, it returns all matches, not just 
the first one, and it does not need the whole text in memory at once. 
Whenever it yields, it will have read the text exactly up to and including 
the match that caused the yield.''' 

    # allow indexing into pattern and protect against change during yield 
    pattern = list(pattern) 

    # build table of shift amounts 
    shifts = [1] * (len(pattern) + 1) 
    shift = 1 
    for pos in range(len(pattern)): 
     while shift <= pos and pattern[pos] != pattern[pos-shift]: 
      shift += shifts[pos-shift] 
     shifts[pos+1] = shift 

    # do the actual search 
    startPos = 0 
    matchLen = 0 
    for c in text: 
     while matchLen == len(pattern) or \ 
       matchLen >= 0 and pattern[matchLen] != c: 
      startPos += shifts[matchLen] 
      matchLen -= shifts[matchLen] 
     matchLen += 1 
     if matchLen == len(pattern): 
      yield startPos 

The link where I got the KMP python code (a wbudowane, które będą szybciej małe problemy z powodu stałej wykonania).

Aby uzyskać najbardziej wydajną wydajność, użyj tabeli prefiksów i okien mieszania ciągów znaków jako bazowych liczb całkowitych (w biologii nazwałbyś je k-mers lub oligos). ;)

Powodzenia!

EDIT: Istnieje również miły podstęp gdzie posortować listę zawierającą każdy prefiks (N ogółem) w pierwszym ciągiem i każdego prefiksu (n łącznie) w drugim ciągiem. Jeśli dzielą one największy wspólny podciąg, to muszą być przyległe do posortowanej listy, więc znajdź element z drugiego ciągu, który znajduje się najbliżej posortowanej listy, a następnie weź najdłuższy prefiks, który pasuje całkowicie.:)

Answer 3

można użyć difflib.SequenceMatcher:

d = difflib.SequenceMatcher(None,s1,s2) 
>>> match = max(d.get_matching_blocks(),key=lambda x:x[2]) 
>>> match 
Match(a=8, b=0, size=39) 
>>> i,j,k = match 
>>> d.a[i:i+k] 
'GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC' 
>>> d.a[i:i+k] == d.b[j:j+k] 
True 
>>> d.a == s1 
True 
>>> d.b == s2 
True 

Answer 4

Zapraszamy do obejrzenia biblioteki difflib i bardziej dokładnie w find_longest_match():

import difflib 

def get_overlap(s1, s2): 
    s = difflib.SequenceMatcher(None, s1, s2) 
    pos_a, pos_b, size = s.find_longest_match(0, len(s1), 0, len(s2)) 
    return s1[pos_a:pos_a+size] 

s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC" 
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC" 

print(get_overlap(s1, s2)) # GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC