次世代シークエンシング（NGS）技術の出現はゲノム研究に革命をもたらしたが、シーケンスされた生物の全体像を提供することはできていない。なぜなら、数十億のフラグメント断片の相対位置はゲノムアセンブリなしでは分からず、それらは非常にあいまいな重複のあるパズルだからである（Nagarajan and Pop、2013; Pevzner et al、2001）。デノボ配列アセンブリは異なる種間の進化的多様性の理解などの下流データ解析に向けた最初のステップであり、genome 10K（Koepfli et al、2015 pubmed）を含む多数のデータ収集プロジェクトによって証明される。より多くの生物のゲノムをシーケンシングしてアセンブリする努力が増加するにつれて、アセンブリの問題は、、特に不正確なシーケンシングされたリードとゲノムのリピートにより（Head et al、2014）、より複雑で計算集中的になる。
次世代のアセンブリアルゴリズムは、効率的にタスクを完了するために、De Bruijnとstring graphsの2つの基本フレームワークが使用されている。 De Bruijn graphでは、リードから抽出された異なるk-mersのセット（長さkの部分文字列）であるnodeと、 それらの中で (k−1) 重複するedgeからなる。String graphは、古典的なoverlap graphの単純化されたバージョンである。overlap graphでは、nodeはシーケンシングリードであり、non-transitiveなedgeはそれらのsuffixからprefixへの重なりをエンコードする（El-Metwally et al、2013,2014; Myers、2005; Nagarajan and Pop、2013）。
リソース効率の良いゲノムアセンブラの作成により、アセンブリグラフをコンピュータメモリに適合させるために多くの努力がなされてきた。Resource efficiencyという用語は、メモリ空間と速度の両方に触れている（Chikhi et al、2015）。シーケンシングリードのFM索引とBurrows-Wheeler変換を使用して（Simpson and Durbin、2010）、string graph の圧縮表現がSGAに導入された（Simpson and Durbin、2012）。最近、確率的なデータ構造（ブルームフィルタ）とインクリメンタルハッシュ技術の組み合わせがstring graphの表現を再訪した（Ben-Bassat and Chor、2014）。
（一部略）
リソース効率の良いシーケンスアセンブラは、精度と連続性の両方の点でアセンブリ結果が異なる。各ツールには、効率を達成するための妥協案に基づき、一連の長所と短所がある。（一部略）すべてのシナリオに最適なツールは1つもなく、現在のアセンブリパイプラインにはまだ改善の余地があるという共通の結論がある。
本稿では、De Bruijnグラフ表現を再考し、cache obliviousな（参考）Bloomフィルタをシーケンスアセンブリに導入する。著者rの方法は、ブルームフィルタのペアと簡単な統計テストを使って、シーケンスエラーを修正するLighterのアイデア（Song et al、2014 pubmed）に触発されている。LighterはBloomフィルタのkのランダムサンプルを収納して、これらをシードとしてシンプルな統計テストで使用して、読み込み位置を信頼できるものと信頼できないものに分類する。Lighterの究極的な目標は、これらのk-mersをエラーコレクションなしでアセンブリすることであり、それらはすでに信頼できるノードとして分類されているからである。
LightAssemblerは、k-mer間のg塩基をスキップしてk-merの一様なサンプルを取得する。ここで、gはギャップの長さで、Bloomフィルタに格納される。リード中の誤った塩基は、まれなk-merを生成し、正確な塩基によって生成された豊富なk-merと比較して、サンプル中でサバイバルしそうにない。リードポジションの信頼性は、ポジションをカバーし、サンプル中に現れるk-mer数を統計的に計算された閾値と比較することによって決定される。（以下略）
LightAssemblerに関するツイート
インストール
ubuntu16.04でテストした。
ビルド依存
#全部ないなら
apt install gcc zlib1g-dev libpthread-stubs0-dev
本体 Github
git clone https://github.com/SaraEl-Metwally/LightAssembler.git
cd LightAssembler/
make
#defaultではk≤31まで。カスタムするなら(makefile参照)(bcが必要)
make k=151
> ./LightAssembler
$ ./LightAssembler
--- no read files specified as inputs
--- invalid value for genome size: 0
********************************** <<< LightAssembler >>> ***************************************
Light Version of an assembly algorithm for short reads in FASTA/FASTQ/FASTA.gz/FASTQ.gz formats.
Usage: ./LightAssembler [Options] ...FASTA/FASTQ/FASTA.gz/FASTQ.gz files
[-k] kmer size [default: 31]
[-g] gap size [default: 25X:3 35X:4 75X:8 140X:15 280X:25]
[-e] expected error rate [default: 0.01 ]
[-G] genome size [default: 0]
[-t] number of threads [default: 1]
[-o] output file name [default: LightAssembler]
Typical LightAssembler Command Line :
./LightAssembler -k 31 -g 13 -e 0.01 -G 1000000 -t 1 -o LightAssembler read_file1 read_file2 --verbose
****************************************************************************************************
ラン
k=31、g=15で実行。
LightAssembler -k 31 -g 15 -e 0.01 -G 4686137 -o ecoli_contigs -t 3 ecoli_reads_1.fq ecoli_reads_2.fq --verbose
-gフラグで指定するgapサイズは無しでもラン可能。
note (Githubより)
- If the gap size parameter is missing, LightAssembler invokes its parameters extrapolation module to compute the starting gap based on the sequencing coverage and the error rate of the dataset.
引用
LightAssembler: fast and memory-efficient assembly algorithm for high-throughput sequencing reads
El-Metwally S, Zakaria M, Hamza T
Bioinformatics. 2016 Nov 1;32(21):3215-3223.
