Come trovare la sovrapposizione tra 2 sequenze e restituirlo

Question

Sono nuovo in Python e ho già trascorso molte ore con questo problema, spero che qualcuno possa aiutarmi. Ho bisogno di trovare la sovrapposizione tra 2 sequenze. La sovrapposizione è nella parte sinistra delle prime sequenze e nella parte destra della seconda. Voglio che la funzione trovi la sovrapposizione e la restituisca.

mie sequenze sono:

s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC" 
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC" 

La mia funzione deve essere denominato

def getOverlap(left, right) 

Con s1 essere la sequenza di sinistra, e il s2 essere quella giusta.

Il risultato dovrebbe essere

‘GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC’ 

Ogni aiuto è apprezzato

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

Il Knuth-Morris-Pratt algoritmo è un bel metodo per trovare una stringa all'interno di un altro (da quando ho visto il DNA, Immagino che ti piacerebbe che questo si riduca a ... miliardi?).

# 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 (ed un integrato, che sarà più veloce per i piccoli problemi a causa della costante runtime).

Per prestazioni eccellenti, utilizzare una tabella di prefissi e finestre di hash della stringa come numeri interi di base 4 (in biologia si chiamerebbero k-mers o oligos). ;)

Buona fortuna!

MODIFICA: C'è anche un trucco piacevole in cui si ordina una lista contenente ogni prefisso (n totale) nella prima stringa e ogni prefisso (n totale) nella seconda stringa. Se condividono la sottosequenza comune più ampia, devono essere adiacenti nell'elenco ordinato, quindi individuare l'elemento dall'altra stringa più vicina nell'elenco ordinato e quindi prendere il prefisso più lungo che corrisponde completamente.:)

Answer 3

Si potrebbe utilizzare 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

Dai un'occhiata alla biblioteca difflib e più precisamente a 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