ヌクレオチド配列をクラスタリングすることは、生物学的データを分析するための必須ステップである。冗長性を減らし、次世代のシークエンシングデータ（論文より ref.1-6）およびゲノムをde-novoアセンブリするための先駆的な配列クラスタリングツール（ref.7 pubmed）が提案されている。 barcode error correction （ref.8 link）および taxonomic profiling （ref.9 pubmed）のために、シーケンスクラスタリングツールも提案された。さらに、d2_cluster（ref.10）、wcdest（ref.11）、CD-HIT（ref.3,12）（紹介）、UCLUST（ref.13）（紹介）、DNACLUST（ref.9）、mBKM（ref.14）およびd2-vlmc（ref.15）は、汎用シーケンスクラスタリングツールである。これらのツールは、遺伝子配列、EST、RNAのクラスタリング、非冗長な配列グループへ一連の配列を減少させるために適用される。
しかしながら、(i)これらのツールはgreedy algorithmに基づいており、最適のクラスターを形成しない可能性があり、（ii）これらのツールは、クラスタを定義する配列類似性閾値に非常に敏感であり、かつ（iii）最適化されたクラスタを生成することができない欲張りアルゴリズムに基づいており、クラスタの中心を表すシーケンスの選択は最適ではない。
シーケンスクラスタリング（CD-HIT、UCLUST、およびDNACLUST）のために広く使用されているツールは、最適な解決策を見つけることが保証されていないgreedy algorithmに依存している。計算生物学の分野での配列クラスタリングの重要性を考え、著者らははるかに高度なアプローチを提案する。The mean shift algorithmは、画像処理およびコンピュータビジョン（ref.17-19）に広く適用されている汎用最適化技術（ref.16）である（参考）。Greedy algorithmとは異なり、 mean shift アルゴリズムは局所的最適点、クラスターの中心に収束するように「保証」される。このアルゴリズムは他の分野でも何千回も成功しているが、バイオインフォマティクス（ref.20-22）の分野では数回しか適用されていない。ここでは、ヌクレオチドシークエンスをクラスタリングする際の mean shiftアルゴリズムを利用した新しいソフトウェアツールMeShClustを提案する。さらに、本発明者らのアルゴリズムの適応は、4つのアラインメントフリー配列類似性測定を使用して同一性スコアを予測するために新規の分類子を利用する。
現在のクラスタリングアプリケーションの問題は、クラスタを分離する根本的な類似性がしばしば不明であることである。したがって、生物学者は、クラスタリングツールに提供するアイデンティティスコアを推測しなければならない場合がある。間違っている場合、この推測されたスコアは予測クラスタの品質を著しく制限する。たとえば、提供されたアイデンティティスコアが真のアイデンティティスコアよりも高い場合、ツールはより小さいクラスタを生成する。それがはるかに低い場合、ツールはより大きなクラスタを生成するであろう。どちらの状況でも、予測クラスタは実際のクラスタと一致しない。人気のツールは、この不一致を説明していない。
利用可能なツールの別の制限は、クラスタの中心を表すシーケンスの選択が必ずしも最適ではないということである。これらのアルゴリズムでは、どのクラスターにも属していないシーケンスは、新しいクラスターの中心とみなされる。いったんセンターが選択されると、変更されない。例示すると、中心シーケンスが実際のクラスタの周辺にある場合、予測されるクラスタは部分クラスタである可能性が非常に高い。
MeShClustのコアはmean shiftアルゴリズムなので、これらの制限を克服している。具体的には、mean shiftアルゴリズムは実際には最適なシーケンスクラスタを生成する可能性が非常に高い。 MeShClustは柔軟性があり、提供されたアイデンティティスコアを大幅に修正することができる。クラスタを表すシーケンスは変化し、クラスタの真の中心に向かって移動する。 MeShClustは配列類似性パラメータにそれほど敏感ではなく、類似ツールより高い精度を提供する。
インストール
ubuntu18.04でテストした。
ビルド依存
git clone https://github.com/TulsaBioinformaticsToolsmith/MeShClust.git
cd MeShClust/
make
cd bin/
> ./meshclust
# ./meshclust
Usage: ./meshclust *.fasta [--id 0.90] [--kmer 3] [--delta 5] [--output output.clstr] [--iterations 20] [--align] [--sample 1500] [--pivot 40] [--threads TMAX]
実行方法
./meshclust input.fa
The most important parameter, --id, controls the identity of the sequences.
If the identity is below 60%, alignment is automatically used instead of k-mer measures.
However, alignment can be forced with the --align parameter.
引用
MeShClust: an intelligent tool for clustering DNA sequences
James BT, Luczak BB, Girgis HZ
Nucleic Acids Res. 2018 Aug 21;46(14):e83
