質問:
「古典的な」deBruijnグラフとNGSの論文で説明されているグラフをどのように区別するのですか?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

コンピュータサイエンスでは、 De Bruijnグラフには(1) m ^ n の頂点があり、上の長さ n のすべての可能なシーケンスを表します。 m シンボル、および(2) n-1 要素のシフトによって異なるノードを接続する有向エッジ(右側に新しい要素を持つ後続)。

しかし、条件(2)が保持されているバイオインフォマティクスでは、いわゆるDe Bruijnグラフは条件を尊重していないようです(1)。場合によっては、グラフがde Bruijnグラフのようにまったく見えないことがあります(例: http://genome.cshlp.org/content/18/5/821.full)。

それで、私の質問は、私がde Bruijnグラフのバイオインフォマティクスの解釈を使用していることを明示したい場合、それに対する用語はありますか? 「簡略化されたdeBruijnグラフ」、「de Bruijnグラフの投影」、または「隣接するk-merのグラフ」のようなものですか?この区別をしている論文はありますか、それとも私はそれをすべて間違っていましたか?

基本的に、条件1は、エッジのない頂点でさえグラフに存在する必要があることを意味します。
つまり、De Bruijnグラフの非バイオインフォマティクスの実装には、有用な情報が含まれていないため、実際にそれらが格納されているのではないかと思います。
ゲノムアセンブリに使用されるDeBruijnグラフには、もう1つ違いがあります。エッジは重み付けされています。
こんにちは@Slimre。 Q1、de Bruijnグラフはつながっていると思います(1つのコンポーネント)。 `m`と` n`を提供するだけでそれらを構築できます(http://mathworld.wolfram.com/deBruijnGraph.html)。 Q2:はい、実装はすべてのノードを必要としません。 de Bruijnグラフは、「完全グラフ」のような抽象的なエンティティ、組み合わせ構造です。しかし、私の非常に重要なグラフがいくつかのエッジを見逃している場合(b / cは役に立たない)、それを「完全」とは言えません。ところで、それはそれほど重要ではありません! Q3:そうです!質問を編集していただきありがとうございます。
三 答え:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

いくつかの論文がこの区別をしており、実際にそれらを区別するために異なる用語を使用している論文もあります。たとえば、 Kazaux etal。 (2016)は次のことを認めます:

これらの制約は、ゲノムアセンブリ専用のde Bruijn Graph(dBG)のバージョンの使用を支持します-発明された組み合わせ構造とは異なるバージョンNGによるdeBruijn。

Kingsford etal。 (2010)もこの違いを認識しています。

de Bruijnグラフのこの定義は、1940年代の数学文献に記載されているグラフに含まれる必要がある従来の定義とは異なることに注意してください。 (ゲノムに存在する文字列だけでなく)アルファベットから形成できるすべての長さkの文字列。

アセンブリ関連の構造を参照する特定の用語について私が見つけた最も古い参照は、 Skiena and Sundaram(1995)であり、 deBruijn有向グラフのサブグラフ。その後、2002年に、Błażewiczetal。はそれを deBruijn誘導部分グラフと呼びます。 deBruijnサブグラフという用語は、 Quitzauの論文(2009)でも正式に定​​義されています。そこで、また記事( Quitzau and Stoye、2008)で、著者はシーケンスグラフをスパースde Bruijnサブグラフ(アセンブリの問題で一般的に使用される)の修正として説明しています。 、非分岐パスが単一の頂点に置き換えられます。 スパースdeBruijnグラフという用語は、 Chauve etal。でも使用されています。 (2013)

私が見つけたもう1つの用語は、 Malde etal。によって記述された単語グラフでした。 (2005)および Heath and Pati(2007)によってサブグラフまたはdeBruijnグラフの一般化として。 Rødland(2013)は、このデータ構造に使用されるいくつかの用語を要約しています。

データ構造は、S [k]のdeBruijnサブグラフ表現の観点から最もよく理解されます。 (...)一部の作成者は、これをワードグラフ、または単にdeBruijnグラフと呼ぶ場合があります。

この区別はあまり関連性がないことは認識できますが、問題はそのような区別をしたい状況を具体的に尋ねます。

多くの論文と私が言ったように、Assembly deBruijnグラフは完全なdeBruijnグラフのサブグラフにすぎません。別の言い方をすると、この単純な関係を認めることができません。 「シーケンスグラフ」は一般的すぎて、他のコンテキストで使用されます(シーケンスアセンブリグラフなど)。 「スパースdeBruijnグラフ」は、読み取りで一部のk-merをスキップして作成されたグラフ(スパースアセンブラーなど)に適しています。有向非巡回単語グラフ(DAWG)は既存の概念であり、少なくとも80年代にさかのぼります。これにより、「単語グラフ」もあいまいになります。人々はサブグラフの新しい名前を発明するのをやめるべきです。
Pevznerは、アセンブリ(http://www.pnas.org/content/98/17/9748.full)および選択的スプライシング(https://www.ncbi.nlm.nih.gov/)でdeBruijnグラフを使用するという独創的な作業を行いました。 pubmed / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

ウィキペディアに示されている通常のDeBruijnグラフに加えて、バイオインフォマティクスの一部の実装は追加の処理を備えています。リンクした論文(Velvetゲノムアセンブラーに関して)の図1がわずかに異なる主な理由は、ノードが一連の重複するk-mer を表すためだと思います。これをより古典的なDeBruinグラフとして視覚化するには、ノードの上に描かれているk-merを接続する必要があります。 図1の横のキャプションは、処理を非常に明確に説明しています。

最後の質問によると、「DeBruijnグラフのバイオインフォマティック解釈」はないと思います。さまざまな実装があり、すべてに詳細があります。したがって、実際の実装を参照するのが最善です。

例として:これは、複数のゲノムの汎ゲノムDeBruijnグラフを同時に作成する方法に関する優れた論文です。 。

しかし、すべてのk-merを含まないde Bruijnグラフの「実装」は、もはやde Bruijnグラフではありません(本来の意味で)。実装が上記の条件(1)を満たさない場合、別の名前(または修飾子)が使用されているのではないかと思います。
すべてのオリジナルのk-merが何らかの形で存在していると確信しています。
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

最初に、DNAには1本の鎖しかないと仮定しましょう。 Assembly de Bruijnグラフは、完全なdeBruijnグラフのサブグラフです。 uが読み取りでk-merの場合、頂点uが含まれます。 uとvが読み取りで隣接するk-merである場合、エッジu-> vが含まれます。あるいは、エッジu-> vが(k + 1)-merで表されることに注意してください。アセンブリdeBruijnグラフは、読み取りですべての(k + 1)-merから誘導されたサブグラフエッジと見なすことができます。実際、一部のアセンブラは、(k + 1)-merのリストをdeBruijnグラフの簡潔な表現と見なします。

DNAには2本の鎖があります。すべての(k + 1)-merとそれらの逆補集合からアセンブリdeBruijnグラフを誘導する必要があります。それはまだ完全なdeBruijnグラフのサブグラフです。

アセンブリdeBruijnグラフは単なるサブグラフであるためです。新しい名前を付ける必要はありません。

PS:コメントに基づいて求めているものではなかったため、古い回答を削除しました。私はあなたがベルベットについて言及していることに混乱しました。 Velvetは、de Bruijnグラフの同等ではあるが一般的ではない表現を使用しているため、質問が複雑になります。



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