ベルベットアセンブラー

Velvetは、 de novo ゲノムアセンブリとショートリードシーケンシングアライメントを処理するために設計されたアルゴリズムパッケージです。これは、エラーの除去と繰り返し領域の簡素化によるゲノム配列アセンブリのde Bruijnグラフの操作によって実現されます。 ^{[2] Velvetは、} Sequencher、Geneious、MacVector、BioNumericsなどの商用パッケージにも実装されています。

次世代シーケンサー（NGS）の開発により、非常に短いリードシーケンスのコスト効率が向上しました。アライメントの方法としてのde Bruijnグラフの操作はより現実的になりましたが、エラーや繰り返しの問題に対処するためにさらなる開発が必要でした。^[3]これにより、英国の欧州バイオインフォマティクス研究所のDaniel ZerbinoとEwan BirneyによるVelvetの開発が進みました。 ^[4]

Velvet は、交差しないパスを単一のノードに収束させることで、グラフ情報を失うことなく、簡略化と圧縮によって de Bruijn グラフを効率的に操作します。最初にシーケンスを結合するエラー修正アルゴリズムを使用して、エラーを排除し、繰り返しを解決します。次に、ローカル重複を共有するパスを分離する繰り返しソルバーによって、シーケンスから繰り返しが削除されます。

短い読み取りと読み取りペアの組み合わせにより、Velvet は小さな繰り返しを解決し、適切な長さのコンティグを生成できます。この Velvet アプリケーションでは、ペアエンド原核生物データではN50長が 50 kb、哺乳類データの領域では 3 kb の長さのコンティグを生成できます。

すでに述べたように、Velvet は de Bruijn グラフを使用して短いリードを組み立てます。より具体的には、Velvet は、リードから取得した異なる各k-mer をグラフ上の一意のノードで表します。2 つのノードは、その k-mer に k-1 の重複がある場合に接続されます。言い換えると、A で表される k-mer の最後の k-1 文字が B で表される k-mer の最初の k-1 文字である場合、ノード A からノード B へのアークが存在します。次の図は、Velvet で生成された de Bruijn グラフの例を示しています。

反対の鎖の読み取り間の重複を考慮するために、すべての k-mer の逆補完に対して同じプロセスが同時に実行されます。グラフに対して、簡素化やエラー除去など、さまざまな最適化を行うことができます。

メモリ コストを節約する簡単な方法は、グラフで生成されるパスに影響を与えないノードをマージすることです。つまり、ノード A にノード B を指す出力アークが 1 つだけあり、入力アークが 1 つだけの場合は、ノードをマージできます。両方のノードを 1 つとして表し、それらとすべての情報を一緒にマージすることができます。次の図は、最初の例を簡略化してこのプロセスを示しています。

グラフ内のエラーは、シーケンス処理によって発生する場合もあれば、単に生物学的サンプルに何らかのエラー (多型など) が含まれている場合もあります。Velvet は、ヒント、バブル、誤った接続の 3 種類のエラーを認識します。

ノードは先端とみなされ、片方の端が切断されている場合、ノードに格納されている情報の長さが 2k 未満の場合、およびこのノードにつながるアークの多重度 (グラフの構築中にアークが見つかった回数) が低いために他の代替パスと比較できない場合は、削除する必要があります。これらのエラーが削除されると、グラフは再び簡略化されます。

バブルは、2 つの異なるパスが同じノードで開始および終了するときに生成されます。通常、バブルはエラーまたは生物学的変異によって発生します。これらのエラーは、ダイクストラ アルゴリズムに似た幅優先探索で最適なパスを検出し、削除するパスを決定するツアー バス アルゴリズムを使用して削除されます。簡単な例を図 4 に示します。

このプロセスは、図 1 および 2 に示した例に続いて、図 5 にも示されています。

これらは、正しいパスを生成しない、またはグラフ内に認識可能な構造を作成しない接続です。Velvet は、Tour Bus アルゴリズムの完了後にこれらのエラーを消去し、ユーザーが定義する必要がある単純なカバレッジ カットオフを適用します。

Velvet は次の機能を提供します。

ベルベット

このコマンドは、velvetg のデータ セット (読み取りをハッシュ) の構築に役立ち、各シーケンス ファイルの意味に関する情報が含まれます。

ベルベット

このコマンドは、velveth によって取得された k-mer から de Bruijn グラフを構築し、グラフに対して簡略化とエラー修正を実行します。その後、コンティグを抽出します。

velvetg を実行すると、いくつかのファイルが生成されます。最も重要なのは、コンティグのファイルには 2k を超えるコンティグのシーケンスが含まれていることです。ここで、k は velveth で使用されるワード長です。

詳しい内容と例についてはベルベットマニュアル^{[5]を参照のこと。}

NGSを含む現在のDNAシーケンシング技術は、ゲノムが読み取り長よりもはるかに大きいという理由で限界があります。通常、NGSは400bp未満の小さな読み取りで動作し、以前の第1世代のマシンよりも読み取りあたりのコストが大幅に低くなります。また、操作が簡単で、並列処理が高く、収量も高くなります。^[3]

ただし、短い読み取りには長い読み取りよりも情報が少ないため、検出可能な重複を可能にするために、アセンブリ読み取りカバレッジを高くする必要があります。これにより、シーケンスの複雑さが増し、計算要件が大幅に増加します。読み取りの数が増えると、重複グラフのサイズも大きくなり、計算が難しくなり、時間がかかります。重複セクションが減少するため、読み取り間の接続が不明瞭になり、エラーの可能性が高くなります。

これらの問題を克服するために、効率的でコスト効率が高く、エラーや繰り返しを解決できる動的シーケンシングプログラムが開発されました。Velvetアルゴリズムはこのために設計されており、他のアセンブラと比較して比較的短い計算時間で、メモリ使用量を抑えながら、短い読み取りのde novoシーケンシングアライメントを実行できます。^[6]

Velvet を使用する際の主な欠点の 1 つは、コマンドライン インターフェイスの使用と、特に初心者がデータの実装で直面する困難です。Velvet アセンブラのグラフィカル ユーザー インターフェイスは 2012 年に開発され、この問題を克服し、Velvet の実行を簡素化するように設計されています。^[7]

• デノボ配列アセンブラ
• SPAdes (ソフトウェア)