2020 12/11 論文引用
マルティプルゲノムアラインメントは、集められたゲノム配列の集まり内の全ての高品質のmultiple local alignmentsを同定する問題である。それはバイオインフォマティクスにおける根本的な問題であり、リアレンジメント分析、系統発生再構築、および進化過程の調査のようなほとんどの比較ゲノム研究の出発点である。残念なことに、高コピーリピートの存在および莫大な入力サイズにより、複数の全ゲノムアラインメントは極めて困難である。現在のアプローチは多くの研究で首尾よく適用されてきたが、それらはアセンブルされたゲノムの数およびサイズの増加に追いつくことができない（Earl et al、2014）。マルティプルゲノムアラインメント問題は、シンテニー再構築問題およびパンゲノムを最も良く表現する方法の問題とも密接に関連している- 補足注1で関連について詳しく述べる。
全ゲノムアラインメント問題に取り組むための２つの一般的な戦略がある（Dewey and Pachter、2006）。第一の方法は、ペアワイズローカルアラインメントを見つけ（Altschul et al、1990、1997； Schwartz et al、2003； Harris、2007； Kent、2002）、次いでそれらをマルティプルローカルアラインメントに拡張することに基づく(Blanchette et al., 2004; Dubchak et al., 2009a; Angiuoli and Salzberg, 2011;Paten et al., 2011)。この戦略はその高い精度で知られているが、複数の全ゲノムアラインメント方法の競合的評価はいくつかの限界を強調している(Alignathon, Earl et al. (2014))。まず、ペアワイズローカルアライメントの数はリピートコピー数に応じて2次的に増加するため、多くのアルゴリズムでは設計による繰り返しの処理ができないか、スケーリングが不十分である。さらに、多くのアルゴリズムはリピートデータベースを使用して高頻度のリピートをマスクする。ただし、これらのデータベースは通常不完全であり、少量のマスクされていないリピートでもアライメントのパフォーマンスが大幅に低下する可能性がある。第二に、ペアワイズアラインメントの数はゲノムの数とquadraticな関係にあり、そして既存のアプローチのほんのわずかのみ10以上のショウジョウバエゲノムを取り扱えた（Earl et al、2014）。それゆえ、これらのアプローチは、最近集められた16系統のマウスのような多数の長く複雑な哺乳動物ゲノムには不適当である（Lilue et al、2018）。
あるいは、アンカーに基づく戦略を適用して、ゲノムを局所的に同一線上のブロックに分解することができる（Darling et al、2004）。これらは、逆位や転座などの非線形の並べ替えが行われていないブロックと定義される。そのようなブロックが特定されると、それらは独立してグローバルにアライメントすることができる（Darling et al、2004； Dewey、2007； Paten et al、2008； Darling et al、2010； Minkin et al、2013）。そのような戦略は、それらが計算的に高価なペアワイズアラインメントに依存しないので、一般的に反復および複数のゲノムを扱うためのスケーリングにおいてより優れている。
シンテニーブロックを見つけるための有望な戦略は、コンパクト化されたde Bruijnグラフに基づいている（Raphael et al、2004; Pham and Pevzner、2010; Minkin et al。、2013b）（我々(著者ら)は、de Bruijnグラフもゲノムアセンブリに使用されることに注意する）。そして、補足注1）でその接続について詳しく述べる。これらのアプローチは大きく異なるゲノムに対してはうまくいかないが、closely relatedなゲノムに対してはかなり正確である。例えば、Sibelia（Minkin et al、2013b）はリピートを処理でき、多くのバクテリアゲノムに対して機能する。残念ながら、それはより大きなゲノムには対応していない。しかし、過去3年間でde Bruijnグラフ構築アルゴリズムの効率が飛躍的に向上した（Marcus et al、2014; Chikhi et al、2016; Baier et al、2016; Minkin et al、2017）。最新の方法では、数週間ではなく数分で数十の哺乳類ゲノムのグラフを作成できる。したがって著者らは、de Bruijnグラフアプローチが、closely relatedなゲノムのスケーラブルな複数全ゲノムアラインメントを可能にするための最も可能性があると考えている。
ここでは、最も近い共通の祖先までの進化距離が9 PAM単位（等価的に、サイトあたり0.085置換）である、closely relatedなゲノムのシンテニーブロックを同定する新規アルゴリズムSibeliaZ-LCBについて説明する。SibeliaZ-LCBは、コンパクト化されたde Bruijnグラフの分析に基づいており、Clearyらによって紹介された「最も頻繁なパス」と同様のシンテニーブロックのグラフモデルを使用する（2017）。これにより、単純で静的なデータ構造を維持することができ、それによって容易に拡張でき、単純な並列化が可能になる。このように、SibeliaZ-LCBは、更新に費用がかかる動的データ構造に頼っていたこれまでの最先端のde Bruijnグラフベースのアプローチのボトルネックを克服している（Pham and Pevzner、2010; Minkin et al、2013a） 。さらに、SibeliaZ-LCBをSibeliaZと呼ばれる複数の全ゲノムアライナーに拡張する。 SibeliaZは、先に発表されたTwoPaCoツール（Minkin et al、2017）を使用して最初に圧縮されたde Bruijnグラフを作成し、次にSibeliaZ-LCBを使用してローカルシンテニーブロックを見つけ、最後に複数シーケンスアライナを実行する。この方法のスケーラビリティと精度を実証するために、マウスの最近アセンブリされた複数の系統コレクションの全ゲノムアラインメントを計算する。また、シミュレーションを使用して、ゲノム間のさまざまなレベルの相違やさまざまなパラメータ設定など、さまざまな条件下でこのメソッドがどのように機能するかをテストする。
Our paper on fast whole-genome aligner for closely-related genomes SibeliaZ is finally out in Nature Communications: https://t.co/5VDzgVLdDn! SibeliaZ can align multiple mammalian-sized genomes on a single server allowing to scale comparative genomics when resources are limited.
— Ilia Minkin (@IliaMinkin) 2020年12月10日
インストール
ビルド依存
- CMake
- A GCC compiler supporting C++11
- Intel TBB library properly installed on your system. In other words, G++ should be able to find TBB libs (future releases will not depend on TBB)
本体 Github
git clone https://github.com/medvedevgroup/SibeliaZ
cd SibeliaZ/
mkdir build
git submodule update --init --recursive
cd build
cmake .. -DCMAKE_INSTALL_PREFIX=<install dir>
make install
> ./sibeliaz -h
# ./sibeliaz -h
Usage: [-k <odd integer>] [-b <integer>] [-m <integer>] [-a <integer>] [-t <integer>] [-f <integer>] [-o <output_directory>] [-n] <input file>
root@4cba361f690d:/data/SibeliaZ/build/SibeliaZ-
> ./sibeliaz-lcb -h
# ./sibeliaz-lcb -h
USAGE:
./sibeliaz-lcb [--noseq] [-o <directory name>] --fasta <file name>
--graph <file name> [-a <integer>] [-t <integer>] [-m
<integer>] [-b <integer>] [-k <oddc>] [--] [--version]
[-h]
Where:
--noseq
Do not output blocks sequences
-o <directory name>, --outdir <directory name>
Output dir for blocks sequences
--fasta <file name>
(required) FASTA file containing the genomes
--graph <file name>
(required) Binary file containing the graph
-a <integer>, --abundance <integer>
Max abundance of a junction
-t <integer>, --threads <integer>
Number of worker threads
-m <integer>, --blocksize <integer>
Minimum block size
-b <integer>, --branchsize <integer>
Maximum branch size
-k <oddc>, --kvalue <oddc>
Value of k
--, --ignore_rest
Ignores the rest of the labeled arguments following this flag.
--version
Displays version information and exits.
-h, --help
Displays usage information and exits.
SibeliaZ-LCB, a program for construction of locally-collinear blocks
from complete genomes
$PATHを通していないなら、twopaco（リンク）のバイナリは以下の場所にある。
> SibeliaZ/build/TwoPaCo/src/graphconstructor/twopaco
テストラン
example/で以下のコマンドを実行する。genomes.faは４つのゲノムを連結したfastaになる。
cd SibeliaZ/examples/
sibeliaz -f 4 genomes.fa
メモリ使用量を前もって指定する必要があるプログラムがあるため、-fで使用メモリ量を指示する。"-f 4"で4GBになる。
結果はデフォルト条件だとsibeliaz_out/に出力される。
> ls -al sibeliaz_out/
# ls -al sibeliaz_out/
total 6344
drwxr-xr-x 5 root root 160 Feb 23 23:33 .
drwxrwxr-x 5 root root 160 Feb 23 23:15 ..
-rw-r--r-- 1 root root 5646300 Feb 23 23:34 alignment.maf
drwxr-xr-x 6 root root 192 Feb 23 23:34 blocks
-rw-r--r-- 1 root root 169117 Feb 23 23:33 blocks_coords.gff
whole-genome alignmentのmafファイルと、シンテニーブロック領域を記載したgffが出力される。
オプションの詳細はGIthubで説明されています。確認してください。
引用
Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ
Ilia Minkin, Paul Medvedev
bioRxiv preprint first posted online Feb. 13, 2019
2020 12/11
Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ
Ilia Minkin & Paul Medvedev
Nature Communications volume 11, Article number: 6327 (2020)
関連
