6

私の長いシーケンスが次のようになっているとします。

5’-AGGGTTTCCC**TGACCT**TCACTGC**AGGTCA**TGCA-3

この長いシーケンスの 2 つのイタリック体のサブシーケンス (ここでは 2 つの星の内側) は、まとめて逆反復パターンと呼ばれます。これら 2 つのサブシーケンスの A、T、G、C などの 4 文字の長さと組み合わせはさまざまです。しかし、これら 2 つのサブシーケンスの間には関係があります。最初のサブシーケンスを考慮すると、その相補サブシーケンスは ACTGGA であり (A は T と結合し、G は C と結合します)、この相補サブシーケンスを反転すると (つまり、最後の文字が最初に来る)、2 番目のサブシーケンスと一致することに注意してください。

このようなパターンは FASTA シーケンス (1000 万の ATGC 文字を含む) に多数存在し、そのようなパターンとその開始位置と終了位置を見つけたいと考えています。

4

4 に答える 4

5

私は Python とバイオインフォマティクスの両方に慣れていませんが、rosalind.info Web サイトを調べて、両方のいくつかを学んでいます。これはサフィックス ツリーで行います。サフィックス ツリー ( http://en.wikipedia.org/wiki/Suffix_treeを参照) は、バイオインフォマティクスであらゆることを可能にする魔法のデータ構造です。複数の長いシーケンスで共通の部分文字列をすばやく見つけます。サフィックス ツリーは線形時間のみを必要とするため、長さ 10,000,000 が実現可能です。

したがって、最初にシーケンスの逆補数を見つけます。次に、両方を接尾辞ツリーに入れ、それらの間の共通部分文字列を見つけます (最小限の長さ)。

以下のコードは、このサフィックス ツリーの実装を使用しています: http://www.daimi.au.dk/~mailund/suffix_tree.html . Python バインディングを使用して C で記述されています。多数のシーケンスを処理することはできませんが、2 つであれば問題ありません。ただし、これが長さ 10,000,000 を処理できるかどうかはわかりません。

from suffix_tree import GeneralisedSuffixTree

baseComplement = { 'A' : 'T', 'C' : 'G', 'G' : 'C', 'T' : 'A' }

def revc(seq):
    return "".join([baseComplement[base] for base in seq[::-1]])

data = "AGGGTTTCCCTGACCTTCACTGCAGGTCATGCA"
# revc  TGCATGACCTGCAGTGAAGGTCAGGGAAACCCT
#       012345678901234567890123456789012
#                 1         2         3
minlength = 6

n = len(data)
tree = GeneralisedSuffixTree([data, revc(data)])
for shared in tree.sharedSubstrings(minlength):
    #print shared
    _, start, stop = shared[0]
    seq = data[start:stop]
    _, rstart, rstop = shared[1]
    rseq = data[n-rstop:n-rstart]
    print "Match: {0} at [{1}:{2}] and {3} at [{4}:{5}]".format(seq, start, stop, rseq, n-rstop, n-rstart)

これにより出力が生成されます

Match: AGGTCA at [23:29] and TGACCT at [10:16]
Match: TGACCT at [10:16] and AGGTCA at [23:29]
Match: CTGCAG at [19:25] and CTGCAG at [19:25]

各マッチは、両端から 1 回ずつ、合計 2 回検出されます。逆回文もあります！

于 2013-01-12T22:04:00.083 に答える
1

これはブルート フォースの実装ですが、非常に長いシーケンスではおそらくあまり役​​に立ちません。

def substrings(s, lmin, lmax):
    for i in range(len(s)):
        for l in range(lmin, lmax+1):
            subst = s[i:i+l]
            if len(subst) == l:
                yield i, l, subst

def ivp(s, lmin, lmax):
    mapping = {'A': 'T', 'G': 'C', 'T': 'A', 'C': 'G'}
    for i, l, sub in substrings(s, lmin, lmax):
        try:
            from string import maketrans
        except ImportError: # we're on Python 3
            condition = sub.translate(
                       {ord(k): v for k, v in mapping.items()})[::-1] in s
        else: # Python 2
            condition = sub.translate(maketrans('ATGC', 'TACG'))[::-1] in s
        if condition:
            yield i, l, sub

長さ 6 (およびその開始位置と長さ) の「反転した繰り返しパターン」を見つけてみましょう。

>>> list(ivp('AGGGTTTCCCTGACCTTCACTGCAGGTCATGCA', 6, 6))
[(10, 6, 'TGACCT'), (19, 6, 'CTGCAG'), (23, 6, 'AGGTCA')]

ただし、これは 2 つのパターンが重複しているかどうかをチェックしません。たとえば、'CTGCAG'それ自体に一致します。

于 2013-01-12T22:22:00.673 に答える
0

長いシーケンスの逆パリンドロームシーケンスを見つけるためのアイデアがあります。シーケンス全体のDNAシーケンスのセクションを検討し、その補数を生成します。次に、この補数シーケンスのセクションを逆にします。次に、これら2つのセクション間で動的アラインメントを実行し、そのコストを計算します（1つは実際のシーケンスから、もう1つは逆相補シーケンスから）。コストは、どの配置が最適かを判断するためのものです。ここで、最適な配置のコスト> =しきい値のコストである場合は、そのセクションを選択して、共通の領域を見つけます。この特定のセクションの2つの一般的な領域は、1つの逆方向反復単位になります。ユニットを見つけたら、次のセクションでそれを繰り返します。それ以外の場合は、セクションの長さを連続的に増やします。誰でもこのアルゴリズムを実装できますか？それは有用な解決策になるかもしれません。

于 2013-01-14T02:22:05.527 に答える