2 अनुक्रमों के बीच ओवरलैप कैसे ढूंढें, और इसे

Question

पर वापस लौटें, मैं पाइथन में नया हूं, और इस समस्या के साथ पहले से ही कई घंटों तक खर्च कर चुका हूं, उम्मीद है कि कोई मेरी मदद कर सकता है। मुझे 2 अनुक्रमों के बीच ओवरलैप ढूंढना होगा। ओवरलैप पहले अनुक्रमों के बाएं सिरे और दूसरे के दाहिने सिरे पर है। मैं चाहता हूं कि फ़ंक्शन ओवरलैप ढूंढें, और इसे वापस कर दें।

मेरे दृश्यों हैं:

s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC" 
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC" 

मेरे समारोह छोड़ दिया अनुक्रम किया जा रहा है नाम दिया जाना चाहिए

def getOverlap(left, right) 

s1 के साथ, और s2 सही जा रहा है।

परिणाम होना चाहिए

‘GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC’ 

किसी भी मदद की सराहना की

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

Knuth-Morris-Pratt एल्गोरिथ्म एक के अंदर एक स्ट्रिंग को खोजने के लिए एक अच्छा तरीका है (के बाद से मैं डीएनए देखा था, मुझे लगता है कि आप इसे स्केल करना चाहते हैं ... अरबों?)।

# 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 (और अंतर्निहित है, जो क्रम निरंतर की वजह से छोटे समस्याओं के लिए तेजी से हो जाएगा)।

रक्तस्राव-किनारे के प्रदर्शन के लिए, बेस 4 पूर्णांक के रूप में अपनी स्ट्रिंग की एक उपसर्ग तालिका और हैश विंडो का उपयोग करें (जीवविज्ञान में आप उन्हें के-मेर्स या ओलिगोस कहते हैं)। ;)

शुभकामनाएं!

संपादित करें: एक अच्छी चाल भी है जहां आप पहली स्ट्रिंग में प्रत्येक उपसर्ग (एन कुल) और दूसरी स्ट्रिंग में प्रत्येक उपसर्ग (एन कुल) वाली सूची को सॉर्ट करते हैं। यदि वे सबसे बड़ा आम अनुक्रम साझा करते हैं, तो वे क्रमबद्ध सूची में आसन्न होना चाहिए, इसलिए क्रमबद्ध सूची में सबसे नज़दीक की दूसरी स्ट्रिंग से तत्व ढूंढें, और उसके बाद सबसे लंबा उपसर्ग जो पूरी तरह मेल खाता है।:)

Answer 3

आप 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

difflib पुस्तकालय पर एक नज़र और अधिक सटीक 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