1

最初の 5 文字と最後の 5 文字に基づいて、一致するシーケンスを整列させようとしています。たとえば、次のようになります。

AAATGCEGAIRPVOGJKKK
KKKTGKAFKEJWKLJFFFF
FFFKEJFWKFJWEKFJIGK

作成するために整列および連結します：

AAATGCEGAIRPVOGJKKKTGKAFKEJWKLJFFFFKEJFWKFJWEKFJIGK

マッピング領域を繰り返さないことに注意してください。実際には 3 行以上あり、順序付けられていないため、ループを作成してすべてを整列させようとしています。これにアプローチする最善の方法がわかりません。

4

1 に答える 1

1

接頭辞の辞書を作ることでこれを解決できると思います。取得したら、任意のシーケンスから始めて、そのサフィックスがプレフィックス リストにあることを確認します。次に、そのプレフィックスを持つシーケンスに移動して、チェーンを構築します。

ここにいくつかのコードがあります：

def make_circular_overlapping_sequence(sequences, min_overlap=1, max_overlap=5):
    # start by mapping prefixes to full sequences
    prefixes = {}
    for seq in sequences:
        for length in range(min_overlap, max_overlap+1):
            prefixes[seq[:length]] = seq

    # pick arbitrary a start sequence
    start = current = sequences[0]

    # build a chain of sequences with overlapping suffixes and prefixes
    chain = [start]
    while True:
        # try longest suffixes first
        for length in range(max_overlap, min_overlap-1, -1):
            suffix = current[-1-length:]
            if suffix in prefixes:
                current = prefixes[suffix]
                if current == start: # looped around, so we're done
                    return "".join(chain)
                chain.append(current[length+1:]) # don't duplicate the prefix
                break
        else: # for loop ended without breaking
            raise ValueError("No match found for sequence {!r}"
                             .format(current))

テスト出力:

>>> sequences = '''AAATGCEGAIRPVOGJKKK
KKKTGKAFKEJWKLJFFFF
FFFKEJFWKFJWEKFJIGK
GKXYZ1234AAAT'''.split()
>>> make_circular_overlapping_sequence(sequences)
'AAATGCEGAIRPVOGJKKKTGKAFKEJWKLJFFFFKEJFWKFJWEKFJIGKXYZ1234AAAT'

ノート：

  1. このコードは、あいまいでない循環シーケンスに対して機能しますが、あいまいな一致がある場合 (たとえば、 または"...ABC"のいずれかが続く可能性がある"ABC..."場合"BC...") は、期待どおりに機能しない可能性があります。現在、常に最長のオーバーラップが選択されます。
  2. チェーンがループせずに終了した場合、コードは例外を発生させますが、開始要素 (例: ) を含まない短いループがある場合、永久に実行される可能性があります["A...B", "B..C", "C..B"]。
  3. アルゴリズムは、すべての入力シーケンスが出力に含まれることを保証しません。ループを見つけて停止するだけです。
  4. 最初と最後の値の一致する部分は削除されません。それを望まない場合は、戻り値から最後の接尾辞を切り取ることをお勧めします。return "".join(chain)[:-length]
于 2013-09-09T15:53:10.200 に答える