オーバーラップグラフに基づいたde novoゲノムアセンブラ ALGA

2021 1/22 誤字修正

　オーバーラップグラフ法に基づいたde novoゲノムアセンブリの手法は非常に少ない。いわゆるde Bruijnグラフアプローチよりも正確な結果が得られると考えられているが、より多くの時間とより多くのメモリを必要とする。オーバーラップグラフモデルを用いたアセンブリ手法では、主にコンピュータのメモリ制限のために、より大きなデータセットをうまく計算できないことが珍しくない。このため、ここ数十年の間に、主にde Bruijnに基づく高速でかなり正確なアセンブリ手法が開発されてきた。しかし、後者のde Bruijnに基づく方法は、より長いゲノムやリピートの多いゲノムでは、リードを短い断片に分解して情報の一部を失うため、失敗する可能性がある。ビッグデータセットを処理し、オーバーラップグラフモデルを利用した効率的なアセンブラの開発が検討されている。
　本研究では、ショートリードシーケンシングデータのために設計されたオーバーラップグラフ法に基づく新しいゲノムスケールのデノボアセンブラを提案する。この手法は、いくつかの新しいアイデアを取り入れており、短時間でより正確なコンティグが得られるようになっている。これらのアイデアの中には、疎ではあるが非常に情報量の多いグラフの作成、局所的な部分グラフの最小スパニングツリーの問題を含むグラフの縮小、これまでに保存されたコンティグの同時解析に関連したグラフ走査などがある。ゲノムアセンブリでは珍しく、アルゴリズムはほとんどパラメータがなく、ユーザが設定するオプションのパラメータは1つだけである。ALGAは、サイズ、カバレッジ、GC含有量、繰り返し回数の異なる6つの生物の実際の実験から得られたゲノムスケールのシーケンシングデータを用いて、9つの最先端のアセンブラと比較した。その結果、ALGAは、ゲノム再構成の全体的な品質、すなわち、ゲノムの網羅性、精度、結果として得られる配列の長さのバランスが良いという意味で、最も良い結果をもたらした。このアルゴリズムは、現在実現されているポーランドの国家プロジェクトであるGenomic Map of Polandのデータ処理に関わるツールの一つである。

http://alga.put.poznan.pl

インストール

ubuntu18.04LTSでビルドした。

ビルド依存

CMake VERSION 2.8.7 or higher
C++ 17 or higher

Github

git clone https://github.com/swacisko/ALGA.git
cd ALGA/
mkdir build 
cd build 
cmake .. 
make -j 4

> ./ALGA -h

$ ./ALGA -h

./ALGA: invalid option -- 'h'

inStreamFilePath1 =

fileName =

fileExtension =

fileNameNoExt =

TEST_NAME = ALGA_NO_NAME_TESTING_scale55_noN

ERROR - PLEASE PROVIDE THE INPUT FILE using --file1 option!

実行方法

ハイクオリティなfastqを指定する(raw file, .fastq or .fasta extension)。

#paired-end
ALGA --file1=pair_1.fastq --file2=pair_2.fastq --threads=8 --output=outprefix

#single-end
ALGA --file1=pair_1.fastq --threads=8 --output=outprefix

出力

f:id:kazumaxneo:20210122114357p:plain

ランタイムは非常に短い。バクテリアゲノムのfastqで試した所、数十秒で計算は終了した。

OLCアセンブラはハイクオリティなショートリードシーケンスデータを必要とするため、GithubではMusketでエラーコレクションすることが推奨されています。また、論文では末端の低品質な領域が問題という記載があります。末端領域の 1塩基または数塩基を前処理の時点で強制トリミングすることも必要かもしれませんね。

引用

Genome-scale de novo assembly using ALGA
Sylwester Swat, Artur Laskowski, Jan Badura, Wojciech Frohmberg, Pawel Wojciechowski, Aleksandra Swiercz, Marta Kasprzak, Jacek Blazewicz
Bioinformatics, Published: 20 January 2021

Genomic Map of Poland

https://ecbig.pl/page/genomic-map-of-poland/