ゲノム解析において、リファレンスゲノムの大規模なコレクションからコンパクトなde Bruijnグラフを構築することは、ますます関心が高まっている課題である。例えば、compacted colored reference de Bruijn graphsは、ショートリードとロングリードのアラインメントのための配列指標として使用されることが多くなってきている。また、個々のゲノムの配列がより多様になるにつれ、compacted colored de Bruijn graphは、これらのゲノムの比較ゲノム解析を行うための基礎として利用されるようになってきている。これまでにリファレンス配列からcompacted colored de Bruijn graphを構築するアルゴリズムは開発されているが、特にde Bruijnグラフを構築するゲノムの数や規模が大きくなるにつれて、メモリや実行時の性能に改善の余地があると考えられる。本研究では、Cuttlefishに実装されている新しいアルゴリズムを紹介する。Cuttlefishは、de Bruijn graphの頂点を有限状態オートマトンとしてモデル化し、オートマトンの状態空間を制約することで、非常に少ないメモリ使用量で遷移状態を追跡できるようにした。また、Cuttlefishは高速で、高度な並列化が可能である。実験結果は、既存のアプローチよりも、特に入力参照の数や規模が大きくなるにつれて、アルゴリズムのスケーリングが優れていることを示している。例えば、典型的な共有メモリ型計算機では、Cuttlefishは7時間以内に100のヒトゲノムの圧縮グラフを構築し、29GBのメモリを使用した。また、11種類の針葉樹植物ゲノムを対象にCuttlefishを適用したところ、~84GBのメモリを使用して11時間以内に圧縮グラフを構築することができたが、他のツールでは16時間以上かかり、~289GBのメモリを使用していた。
CuttlefishはC++14で書かれており、https://github.com/COMBINE-lab/cuttlefish でオープンソースライセンスで利用可能である。
インストール
ubuntu18.04LTSでテストした。kmc3はcondaで導入した。cmakeは3.12以上を要求されたため、Cmake HP（リンク）から最新版のバイナリをダウンロードして使った。
依存
- Cuttlefish uses the KMC3 tool,（kmc3紹介）
git clone https://github.com/COMBINE-lab/cuttlefish.git
cd cuttlefish/
mkdir build
cd build
cmake ..
make install
cd src/
> ./cuttlefish build
$ ./cuttlefish build
No value
Usage :
Efficiently construct the compacted de Bruijn graph from references
Usage:
cuttlefish build [OPTION...]
-r, --refs arg reference files (default: "")
-l, --lists arg reference file lists (default: "")
-d, --dirs arg reference file directories (default: "")
-k, --kmer_len arg k-mer length
-s, --kmc_db arg set of k-mers (KMC database) prefix
-t, --threads arg number of threads to use (default: 1)
-o, --output arg output file
-f, --format arg output format (0: txt, 1: GFAv1, 2: GFAv2) (default: 0)
-w, --work_dir arg working directory (default: .)
--mph arg minimal perfect hash (BBHash) file (optional) (default:
"")
--buckets arg hash table buckets (cuttlefish) file (optional)
(default: "")
-h, --help print usage
実行方法
mkdir temp
kmc -k21 -m100 -fm -ci0 -t20 input.fq kmcoutput temp/
cuttlefish build -k 21 -o kmcoutput -s cuttlefishoutput -f 0
引用
Cuttlefish: Fast, parallel, and low-memory compaction of de Bruijn graphs from large-scale genome collections
Jamshed Khan, Rob Patro
bioRxiv, Posted October 22, 2020
