macでインフォマティクス

macでインフォマティクス

HTS (NGS) 関連のインフォマティクス情報についてまとめています。

機械学習の手法でエミュレートされたBWA-MEM: BWA-MEME

2021 Preprint mapping 高速なツール 2022 Bioinformatics

 

　 次世代シーケンサーの普及やシーケンサーのスループットの向上に伴い、効率的なショートリードのアライメントが求められているが、その中でもシーディングは主要な性能ボトルネックの一つとなっている。Seeding phaseのキーとなるチャレンジは、リファレンスDNA配列中からショートリードの部分配列の正確な一致を検索することである。しかし、既存のアルゴリズムでは、頻繁にメモリにアクセスするため、性能に限界があった。

　本論文では、seedingを効率的に行うための完全一致検索問題を解決するために、学習したインデックスを活用した初の本格的なショートリードアライメントソフトウェアであるBWA-MEMEを紹介する。BWA-MEMEは、seeding phaseで多用されるSMEM探索に学習済みインデックスを活用するという課題を解決する、接尾辞配列探索アルゴリズムをベースとした実用的かつ効率的なseedingアルゴリズムである。評価の結果、BWA-MEMEは、BWA-MEM2と同一のSAM出力を確保しつつ、命令数を4.60倍、メモリアクセスを8.77倍、LLCミスを2.21倍に削減することで、BWA-MEM2と比較してシーディングのスループットを最大で3.45倍に高速化した。

（中略）

BWA-MEMEは、新しい学習済みインデックス構造とアルゴリズムを導入することで、これらの課題に対処する。まず、部分的に3層の再帰的モデルインデックス（P-RMI）を提示し、接尾辞の不均衡な分布にうまく適応し、正確な予測を行う。この過程で、入力された部分文字列や接尾辞を数値キーにエンコードするアルゴリズムを設計する。この数値キーはP-RMIへの入力として与えられ、P-RMIは接尾辞配列内の予測位置と予測の誤差範囲を提供する。P-RMIは、接尾辞配列内の予測位置とその誤差範囲を提供し、誤差範囲内でバイナリ検索を行い、部分文字列が一致する参照位置を見つける。（以下略）

 

 

インストール

  • 3990x CPUを積んだUbuntuマシンでビルドした（make -j arch=avx2）。

Github

#from source
git clone https://github.com/kaist-ina/BWA-MEME.git BWA-MEME
cd BWA-MEME

# If AVX512BW (512-bit SIMD) is supported
make clean
make -j<num_threads> arch=avx512

# If AVX2 (256-bit SIMD) is supported
make clean
make -j arch=avx2

# If SSE4.1 (128-bit SIMD) is supported (default)
make -j<num_threads>

> ./bwa-mem2.avx2 

Usage: bwa-mem2 <command> <arguments>

Commands:

  index         create index

  mem           alignment

  version       print version number

 

 

 

実行方法

レポジトリではヒトゲノムのアセンブリ配列をダウンロードして、indexを付け、訓練してマッピングするまでの流れが書かれています。ここでもその通り進めます。

 

１、ダウンロード

wget ftp://ftp-trace.ncbi.nih.gov/1000genomes/ftp/technical/reference/human_g1k_v37.fasta.gz
gunzip human_g1k_v37.fasta.gz

 

２、indexing

bwa-mem2.avx2 index -a meme -t32 human_g1k_v37.fasta

 

3、P-RMIのトレーニング

./build_rmis_dna.sh human_g1k_v37.fasta

 

４、マッピング

bwa-mem2 mem -Y -K 100000000 -t32 -7 human_g1k_v37.fasta input_1.fastq -o out.sam
  • -Y    use soft clipping for supplementary alignments
  • -K    process INT input bases in each batch regardless of nThreads (for reproducibility)
  • -7    Use Learned index for seeding
  • -t    number of threads [1]
  • -o   Output SAM file name

 

この後、レポジトリでは、オリジナルのbwa-mem2も走らせ、diffコマンドを使ってsam形式ファイルに違いがないか確認する流れについて書かれています。

引用

BWA-MEME: BWA-MEM emulated with a machine learning approach

Youngmok Jung,  Dongsu Han

bioRxiv, Posted September 01, 2021

 

2022/03/08

BWA-MEME: BWA-MEM emulated with a machine learning approach Get access Arrow
Youngmok Jung, Dongsu Han
Bioinformatics, Published: 07 March 2022

 

関連