macでインフォマティクス

macでインフォマティクス

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

ラージデータにも対応したマルチプルシーケンスアラインメントツール Kalign 3

2019 Bioinformatics multiple sequence alignment (MSA) 高速なツール

 

　マルチプルシーケンスアラインメント（MSA）は、生物学的シーケンス解析の重要なタスクのままである。 MSAプログラムは、Consistency-based のメソッドとprogressive なメソッドに分けることができる。後者は、ペアワイズシーケンス距離を推定し、ガイドツリーを構築し、ガイドツリーの順序に従ってシーケンスをアラインする。Consistency-basedのメソッドは、progressive なメソッドと比較してより正確である傾向があるが、桁違いに遅いため、数千のシーケンスを整列する場合には実用的ではない。 Kalign（Lassmann et al、2008）は、一連の一般的なベンチマークデータセット上の他のアラインメントプログラムと比較して、精度と速度のバランスが優れたプログレッシブアライメント手法である（例：Sievers et al、2011を参照）。十分に熟成したにもかかわらず、Kalignは、今日頻繁に遭遇する何万ものシーケンスを処理するようには設計されていない。特に、元のKalignプログラムは、算術平均（UPGMA）アルゴリズムを使用した非加重ペアグループ法を使用して、ガイドツリーを構築し、2次時間の複雑さをもたらす。より最近のアライメントプログラムは、ガイドツリーを構築するためのヒューリスティックを実装することにより、このハードルを克服している（Blackshields et al、2010; Katoh and Toh、2006）。

　ここでは、SIMD（single instruction, multiple data）加速バージョンのGene Myersのビット並列アルゴリズム（Myers、1999）を導入して、ペアワイズシーケンス距離を推定し、Blackshields et al（2010）によって導入されたシーケンス埋め込み戦略を採用して ガイドツリーの構築を高速化するKalignの新しいバージョンを紹介する。

　Kalign2（Muth and Manber、1996）で使用されている高速文字列照合アルゴリズムを、Gene Myersの近似文字列照合アルゴリズムの新しい実装に置き換えまた。このアルゴリズムは、ビット並列命令を使用して、2つの文字列間の正確な編集距離を計算する。標準実装では、クエリの最大長はコンピューターワード（64ビットアーキテクチャでは64文字）のサイズに相当する。ただし、アルゴリズムは、最新のすべてのコンピューターで使用可能なAVXおよびAVX2命令を含むSIMD命令を使用して、さらに並列化できる。これらの命令を使用すると、長さ256のシーケンスを比較することが可能になる。AVX命令を使用したジーンマイヤーズアルゴリズムの実装はかなり単純だが、AVX命令セットにない操作があり、個別に実装する必要があった。アルゴリズムのスタンドアロン実装はKalignと一緒に配布され、ダウンストリームの採用と開発を促進する。（以下略）

 

 

インストール

macos10.14でテストした。

GIthub

git clone https://github.com/TimoLassmann/kalign.git 
cd kalign
./autogen.sh
./configure
make
make check 
make install 

#homebrew
brew install brewsci/bio/kalign

#2019 11月現在、kalign2はcondaで導入可能
conda install -c bioconda kalign2

> kalign -h

$ kalign -h

 

Kalign (3.1.1)

 

Copyright (C) 2006,2019 Timo Lassmann

 

This program comes with ABSOLUTELY NO WARRANTY; for details type:

`kalign -showw'.

This is free software, and you are welcome to redistribute it

under certain conditions; consult the COPYING file for details.

 

Please cite:

  Lassmann, Timo.

  "Kalign 3: multiple sequence alignment of large data sets."

  Bioinformatics (2019) 

  https://doi.org/10.1093/bioinformatics/btz795

 

 

Usage: kalign  -i <seq file> -o <out aln> 

 

Options:

 

   --format           : Output format. [Fasta]

   --reformat         : Reformat existing alignment. [NA]

   --version (-V/-v)  : Prints version. [NA]

 

 

 

実行方法

配列を指定する。

#fasta formatで出力
kalign -i input.fa -f fasta -o out.fa

#clustal formatで出力
kalign -i input.fa -f clu -o out.clu

 

引用

Kalign 3: multiple sequence alignment of large datasets
Timo Lassmann
Bioinformatics, btz795, Published: 26 October 2019