質問:
一部のアセンブラがdeBruijnグラフの作成に奇数長のkmerを必要とするのはなぜですか?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

SOAPdenovo2 Velvetのような一部のアセンブラが、deBruijnグラフの作成に奇数の長さの k -merサイズを必要とするのはなぜですか。 ABySSのような他のアセンブラは、偶数の長さの k -merで問題ありませんか?

二 答え:
#1
+28
Kamil S Jaron
2017-05-19 23:52:35 UTC
view on stackexchange narkive permalink

ベルベットのマニュアルから:

回文を避けるため、奇数にする必要があります。偶数を入力すると、Velvetはそれをデクリメントして続行します。

生物学におけるパリンドロームは逆相補シーケンスとして定義されます。パリンドロームの問題は、このレビューで説明されています。

パリンドロームは、折りたたまれたパスを誘導します。少なくとも1人のアセンブラーがこれらをエレガントに回避します。ベルベットは、K-merの長さであるKが奇数である必要があります。奇数サイズのK-merは、その逆補数と一致できません。

パリンドロームを使用してグラフを作成することは可能ですが、その場合、解釈が難しくなります。奇数の k -merのグラフのみを許可することは、より複雑なグラフを解釈するためのコードを記述しないようにするためのエレガントな方法です。

将来誰かがこれを誤解しないように、この文脈での[palindrome](https://en.wikipedia.org/wiki/Palindromic_sequence)は、[通常は英語で](https ://en.wiktionary.org/wiki/palindrome)。
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

上記の答えを拡張するために、明確でない場合は、次のことを示します。

  1. パリンドロームシーケンスの長さが均一でなければならない理由
  2. パリンドロームシーケンスが誘導する理由deBruijnグラフの自己ループ
  3. deBruijnグラフの自己ループが問題になる理由
  4. ol>

    1。回文配列⇒配列は偶数の長さです

    アイデア:奇数の長さのk-merでは、その中央のヌクレオチドは逆補数で「反転」しているため、 2つが等しくなることはありません。

    パリンドロームシーケンス $ X $ span>があるとします。その場合、 $ X $ span>はその逆補数と同じであり、 $ \ bar {X} $ span>というラベルを付けます。 。

    $ X $ span>の長さが奇数であるとします。次に、 $ AbC $ span>の形式になります。ここで、 $ len(A)= len(C)= \ frac {len (X)-1} {2} $ span>、および $ len(b)= 1 $ span>。

    次に

    $ X = \ bar {X} \ implies AbC = \ overline {AbC} = \ bar {C} \ bar {b} \ bar {A} $ span>

    したがって:

    $ b = \ bar {b} $ span>

    $ len(A)= len(C)= len(\ bar {C}))$ span>以降。ただし、 $ b $ span>は単一ヌクレオチドであり、その補数と等しくすることはできないため、これは矛盾しています。したがって、奇数の長さのk-merはパリンドロームを形成できません。

    したがって、パリンドロームを形成するk-merの長さは偶数でなければなりません。


    2。パリンドロームk-merが自己ループを誘発する理由

    従来のdeBruijnグラフの各ノードは一意の文字列ですが、ほとんどのバイオインフォマティクスの実装では、逆相補的なk-1-merの各ペアは単一ノード、例: $ k = 6 $ span>:

    A palindromic k-mer( $ k \ geq 2 $ span>の)の形式は次のとおりです。

    $ xAy $ span>

    ここで、 $ len(A)= k-2 $ span>、 $ x = \ bar {y} $ span>および $ A = \ bar {A} $ span> (おそらく空の文字列)。

    したがって、deBruijnグラフの2つのノードに寄与します。

    1. 左側のk-1-mer $ xA $ span>
    2. その正しいk-1-mer $ Ay $ span>
    3. ol>

      そしてエッジは1から2になります。

      しかし、このk-merはパリンドロームであるため、 $ xA = \ overline {Ay} $ span>したがって、これら2つのノードは逆相補的であり、したがって「同じ」ノードであるため、このエッジはこのノードでの自己ループになります。


      3。自己ループに問題があるのはなぜですか?

      自己ループ( $ in \ _degree \ geq 2 $ span>と $ out \ _degree \ geq 1 $ span>)は、de Bruijnグラフ(より具体的には、 contig 、複数の場合があります)、このノードを通過するたびに追加の可能なオイラーパスがあるためです。

      これにより、可能なオイラーごとに、グラフを読み取る際のあいまいさが増します。パスは、完全なシーケンスの追加の可能な再構成です。

      例を考えてみましょう:

      enter image description here

      1つだけです可能なオイラーパス:

  • $ ABCDBE $ span>

ただし、自己ループを含める場合上記で2回訪問された $ B $ span>では、これは2つの可能なオイラーパスに倍増します。

enter image description here

  • $ ABBCDBE $ span>
  • $ ABCDBBE $ span>

依存初めて $ B $ span>に到達したとき、または2回目に到達したときに自己ループをトラバースするかどうか。

https://homolog.us/Tutorials/book4/p2.4.html "ゲノムアセンブリプログラムもkを回避します。これは、kが偶数の場合、多くのk-merが独自のシーケンスの逆補数になるためです。**これにより、グラフの鎖特異性。**したがって、奇数のk値が優先されます。」
いい答え@ukemi。ポイント1の結論を理解するのに少し時間がかかったので、そこに助けになる文章を追加しました。変更を元に戻すことができるのは気に入らないのですが、少し説明しておくとよいでしょう。
@KamilSJaron心配はありません、明確であるほど良いです-ええ、技術的には、彼らが従う必要があるという含意のために存在を示すべきでした(単に奇妙ではないのではなく)が、存在を示すことは例によって取るに足らないものです(例:AT、ATAT等)。


このQ&Aは英語から自動的に翻訳されました。オリジナルのコンテンツはstackexchangeで入手できます。これは、配布されているcc by-sa 3.0ライセンスに感謝します。
Loading...