16

私はPythonが初めてで、すでにこの問題に何時間も費やしています。誰かが私を助けてくれることを願っています. 2 つのシーケンス間のオーバーラップを見つける必要があります。オーバーラップは、最初のシーケンスの左端と 2 番目のシーケンスの右端にあります。関数がオーバーラップを見つけて返すようにしたい。

私のシーケンスは次のとおりです。

s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC"
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC"

関数に名前を付ける必要があります

def getOverlap(left, right)

s1左のシーケンスであり、右のシーケンスs2です。

結果は

‘GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC’

どんな助けでも大歓迎です

4

4 に答える 4

22

ライブラリを見て、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
于 2013-01-02T20:46:53.867 に答える
13

使用できます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
于 2013-01-02T20:45:30.800 に答える
6

Knuth-Morris-Prattアルゴリズムは、ある文字列を別の文字列の中に見つけるための優れた方法です (私は DNA を見たので、これを数十億にスケーリングしたいと思いますか?)。

# 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

KMP pythonコード（およびランタイム定数のために小さな問題の場合は高速になるビルトイン）を入手したリンク。

最先端のパフォーマンスを得るには、文字列のプレフィックス テーブルとハッシュ ウィンドウを基数 4 の整数として使用します (生物学では、それらを k-mer またはオリゴと呼びます)。; )

幸運を！

編集:最初の文字列にすべてのプレフィックス (合計 n 個) と 2 番目の文字列にすべてのプレフィックス (合計 n 個) を含むリストを並べ替えるという素晴らしいトリックもあります。それらが最大の共通サブシーケンスを共有している場合、それらはソートされたリストで隣接している必要があるため、ソートされたリストで最も近い他の文字列から要素を見つけ、完全に一致する最長のプレフィックスを取得します。: )

于 2013-01-02T20:43:49.637 に答える
4

最長共通部分文字列

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]
于 2013-01-02T20:38:42.447 に答える