バイオインフォマティクスにおいて、マルチプル配列アライメント（MSA）は極めて重要なタスクである。しかし、従来の方法では、ウルトラロングシークエンスのアライメントに苦労することが多い。この問題に対処するため、研究者たちは、並列アラインメントのために配列データを分割する垂直分割戦略に根ざしたMSA手法を設計してきた。このアプローチの代表例がFMAlignであり、FM-indexを利用して共通のseedsを抽出し、それに応じて配列を分割する。
FMAlign2は、接尾辞配列を活用して最大完全一致を特定し、FMAlignのアプローチをグローバルチェーン検索から部分チェーン検索へと再定義した。縦割り戦略を採用することで、大規模な問題を管理可能なタスクに分解し、subMSAの並列実行を可能にした。さらに、部分鎖を連結するために、配列プロファイルアライメントと精密化が組み込まれ、シームレスに最終結果を得ることができる。FMAlignと比較して、FMAlign2は配列のセグメンテーションを著しく向上させ、特にウルトラロングデータセットにおいて、精度を維持しながら大幅に時間を短縮する。重要なことは、FMAlign2は、許容可能な時間枠内で数十億の長さに達する配列を扱う能力を付与することにより、既存のMSA手法を強化することである。ソースコードとデータセットは https://github.com/malabz/FMAlign2 と https://zenodo.org/records/10435770 にある。
インストール
Windows11のWSL環境でテストした。
Github
https://github.com/malabz/FMAlign2
#テストデータが数百MBのサイズあるので注意
git clone https://github.com/metaphysicser/FMAlign2.git
#配列連結長がuint32_t（4294967295）超える場合はM64パラメータを追加して、64ビットの実行ファイルを生成する（無しだと32bit版）
cd FMAlign2 && make [M64=1] -j12
> ./FMAlign2
Error: Missing required argument: -i
Program Exit!
Usage: FMAlign2 [OPTIONS]
Options:
-c (optional) [default: 1]
A floating-point parameter that specifies the minimum coverage across all sequences, with values ranging from 0 to 1. The default setting is that if sequence number less 100, parameter is set to 1 otherwise 0.7.
-d (optional) [default: 0]
Depth of recursion, you could ignore it.
-f (optional) [default: default]
The filter MEMs mode. The default setting is that if sequence number less 100, local mode otherwise global mode.
-h (optional) [default: help]
print help information
-i [default: data/mt1x.fasta]
The path to the input file.
-l (optional) [default: default]
The minimum length of MEM, the default value is square root of mean length.
-o (optional) [default: output.fmaligned2.fasta]
The path to the output file.
-p (optional) [default: mafft]
The MSA method used in parallel align. for example, halign3, halign2 and mafft.
-t (optional) [default: cpu_num]
The maximum number of threads that the program runs, the recommended setting is the number of CPUs.
-v (optional) [default: 1]
Verbose option, 0 or 1. You could ignore it.
テストラン
MEMの最小長 "-l 20"、MEMのシーケンスカバレッジ "-c 1"、並列アライメント "-p mafft"、アライメントモード”-f global”、入力データ./data/mt1x.fastaから
./FMAlign2 -i ./data/mt1x.fasta -l 20 -c 1 -p mafft -f global -o output.fmaligned2.fasta
レポジトリではgloabl となっているがタイポで正しくは上のように”global”。output.fmaligned2.fastaが出力される。
テスト時はsegmentation faultが発生した。
生成されたアライメントを評価する。--match、--mismatch、--gap1、--gap2パラメータでマッチ、ミスマッチ、ギャップペナルティのスコアリングスキームを定義する。
python sp.py --input output.fmalign2.fasta --match 0 --mismatch 1 --gap1 2 --gap2 2
このコマンドを実行すると、アライメントの質を評価するSPスコアが得られる。
引用
FMAlign2: a novel fast multiple nucleotide sequence alignment method for ultralong datasets
Pinglu Zhang, Huan Liu, Yanming Wei, Yixiao Zhai, Qinzhong Tian, Quan Zou
Bioinformatics, Published: 10 January 2024
