シーケンシング技術の向上により、シーケンシングコストはゲノムあたり100ドルに向かって進み続けている。しかし、シーケンスデータをリファレンスゲノムにマッピングすることは、シーケンスによって導入されるindelやミスマッチを処理するための編集距離に依存しているため、計算量の多い作業であることに変わりない。最近のすべてのアライナーは、編集距離計算のオーバーヘッドを減らすために、シードフィルタリング拡張（SFE）手法を使用し、フィルタリングヒューリスティックに依存している。しかし、フィルタリングはエラーパターンを前提としており、固有の性能と精度のトレードオフがあり、データセットに適合させるためには慎重なハンドチューニングが必要である。
ランダム化された低歪みエンベッディングにおけるアルゴリズムの進歩に触発され、シーケンスマッパーやアライナーを開発するための新しい設計手法であるSEE（seed-embed-extend）を導入した。SFEが最適でない候補を排除することに焦点を当てるのに対し、SEEは最適な候補を特定することに焦点を当てている。そのために、SEEは、ランダム化されたアルゴリズムを用いて埋め込みを行うことで、読み取り文字列と参照文字列を編集距離領域からハミング領域に変換し、埋め込み集合上のハミング距離を用いて最適な候補を特定する。実際にSEEがうまく機能することを示すために、著者らはSEEベースのショートリードシーケンスマッパーとアライナーであるAccel-Alignを紹介する。これは、同等の精度を提供しながら、特別な目的のハードウェアを使用せずに、汎用CPU上の最先端のアライナーよりも3-12倍高速である。
Our latest work with @nimchat12 on randomized low distortion embedding for sequence alignment is out. We introduce seed-embed-extend, a new design method, and show that an SEE aligner can provide 10x reduction in exec. time over bwa and bowtie2 without any special hardware. https://t.co/UATGzjCgxS
— Raja Appuswamy (@raja_appuswamy) 2020年7月21日
インストール
配布されているdocker imageを使ってテストした。
Girthub
現在ソースコードは公開されていない。実行形式ファイルのバイナリとビルド済みのdocker imageだけが提供されている。
git clone https://github.com/raja-appuswamy/accel-align-release.git
cd accel-align-release/
> ./accindex-x86-64
# ./accindex-x86-64
index [options] <ref.fa>
options:
-l INT length of seed. [32]
-m Use low mem
> ./accalign-x86-64
# ./accalign-x86-64
accalign [options] <ref.fa> [read1.fastq] [read2.fastq]
options:
-t INT number of threads to use[1]
-l INT length of seed [32].
-o name of output file to use
-x alignment-free
実行方法
1、indexing
accindex-x86-64 -m ref.fasta
- -m Use low mem
出力。シロイヌナズナゲノムでは2.6GBになった。
2、mapping
accalign-x86-64 -o out.sam -t 30 ref.fasta paired_1.fq paired_2.fq
- -t number of threads to use[1]
- -l length of seed [32].
- -o name of output file to use
引用
Accel-Align: A Fast Sequence Mapper and Aligner based on the Seed–Embed–Extend Method
Yiqing Yan, Nimisha Chaturvedi, Raja Appuswamy
bioRxiv, Posted July 21, 2020
2021 8/30
Accel-Align: a fast sequence mapper and aligner based on the seed–embed–extend method
Yiqing Yan, Nimisha Chaturvedi & Raja Appuswamy
BMC Bioinformatics volume 22, Article number: 257 (2021)
感想
シロイヌナズナゲノムを使い約1400万x２リード（1.6GBx2）のマッピング(sam出力)にかかる時間を調べてみると39秒だった（*）。精度は見ていないが、ランタイムは短い。しかし2020 7/30現在、ソースコードが公開されていない。。。
* オーサー提供のdockerイメージを使用。xeon E5 platinum 2.1 GHz/ 28コア x 1、30スレッド指定。
関連
