HiFiロングリードを効率的にマッピングする mapquik

2023/07/13 タイトル修正、誤字修正

　DNAシーケンスデータは、シーケンスエラー率がますます低くなり、より長いリードへと進歩し続けている。本著者らは、ロングリード（PacBio HiFi）から低発散配列のリファレンスゲノムへのマッピング（アラインメント）という重要な問題に焦点を当てている。自然なアイデアとしては、より長いシードで効率を最適化し、余計なマッチの確率を減らすことであろうが、連続した正確なシードはすぐに感度の限界に達してしまう。本著者らは、連続的にサンプリングされたk個の最小化子（k-min-mer）のマッチによってアラインメントを固定し、リファレンスゲノムに一度だけ出現するk-min-merにのみインデックスを付けることで、高感度を維持しながら超高速マッピングを実現する新しい戦略、mapquikを紹介する。ヒトゲノムとトウモロコシゲノムの両方において、リードマッピングの基本的なボトルネックであるシーディングステップとチェーニングステップをmapquikによって96%以上の感度とほぼ完全な特異性で大幅に高速化できることを実証した。ヒトゲノムでは、mapquikは最先端のツールminimap2に対して30倍のスピードアップを達成し、トウモロコシゲノムではminimap2に対して350倍のスピードアップを達成し、mapquikはこれまでで最速のマッパーとなった。これらの高速化は、minimizer-space seedingだけでなく、新規の発見的アルゴリズムǔ(n) pseudo-chainingアルゴリズムによっても実現されている。ミニマイザースペース計算は、ロングリードシーケンスデータのリアルタイム解析を実現する基盤を構築する。

Our new minimizer-space HiFi-read mapper, mapquik, is now published online (as an advance article) in Genome Research!

https://t.co/fVB0Sibl3h

The recording for the RECOMB 2023 talk is also now up: https://t.co/0WESI9Kj9L
— Barış Ekim (@ekimbarisc) 2023年7月9日

インストール

ubuntu18でビルドした。

依存

Rust environment

Github

rustup update
rustup install nightly #、開発中の機能や実験的な機能を含むnightlyバージョン

git clone https://github.com/ekimb/mapquik.git
cd mapquik/
cargo +nightly build --release #nightlyバージョンでビルド
=> target/release/

> ./mapquik -h

$ ./mapquik -h

mapquik 0.1.0

Original implementation of mapquik, a fast HiFi read mapper

USAGE:

mapquik [FLAGS] [OPTIONS] [reads]

FLAGS:

--debug Activate debug mode

-h, --help Prints help information

--low-memory Enable base-level alignment (WIP)

--nohpc Deactivate HomoPolymer Compression

--nosimd Deactivate SIMD (AVX2,AVX512) functions

(for old processors)

--parallelfastx Use parallelfastx (faster uncompressed reads parsing)

-V, --version Prints version information

OPTIONS:

-b, --b <b> buffer size multiplier

-c, --chain <chain> Minimum chain length

-d, --density <density> Density threshold for density-based

selection scheme

-g, --gap-diff <gap-diff> Maximum nucleotide gap length difference

-k, --k <k> k-min-mer length

-l, --l <l> l-mer (minimizer) length

-p, --prefix <prefix> Output prefix for PAF file

-q, --q <q> queue length

--reference <reference> Reference genome input

-s, --seed <seed> Minimum number of matching seeds

--threads <threads> Number of threads

実行方法

fastq（gzip圧縮も対応）とリファレンスを指定する。

mapquik reads.fq --reference hg38.fasta

出力はPAF形式。CIGARがないので完全なSAM形式には変換できない（参考）。

PBSIM2のP6C4 chemistryのモデルを使ってシミュレートしたhg38アセンブリのリード（x2、ファイルサイズ12.4GB）を使ってhg38にマッピングしたところ、17秒で出力された（xeonE5 v4 2680 dual、20threds指定、PCIe SSD上にて)。minimap2だとindexingから含めて同じハードウェアで3分~5分かかった。

その他

論文で、k-min-merが、k-merと比較して正確なロングリードのアライメントシードとして優れているのか仮説を立てて検証されている。

引用

Efficient mapping of accurate long reads in minimizer space with mapquik

Barış Ekim, Kristoffer Sahlin, Paul Medvedev, Bonnie Berger, Rayan Chikhi

Genome Res. 2023.

https://genome.cshlp.org/content/early/2023/06/29/gr.277679.123

mapquik: Efficient low-divergence mapping of long reads in minimizer space
Barış Ekim, Kristoffer Sahlin, Paul Medvedev, Bonnie Berger, Rayan Chikhi

bioRixv, Posted December 23, 2022