クラスタル

Clustalはバイオインフォマティクスにおける多重配列アライメントに使用されるコンピュータプログラムです。^[2]このソフトウェアとそのアルゴリズムはいくつかの反復を経ており、2011年時点での最新バージョンはClustalΩ（オメガ）です。これはスタンドアロンソフトウェアとして、Webインターフェイス経由で、および欧州バイオインフォマティクス研究所がホストするサーバー経由で利用できます。 ^{[アップデート]}

Clustalは重要なバイオインフォマティクスソフトウェアであり、 2014年のNature誌によると、その学術論文のうち2つは史上最も引用された論文のトップ100にランクインしている。^[3]

• Clustal ：1988年にDes Higginsによって作成された多重配列アライメントのための最初のソフトウェアは、アミノ酸またはヌクレオチドのペアワイズ配列からガイドツリーを導出することに基づいていました。^[4]
• ClustalV : 1992年にリリースされたClustalの第二世代。系統樹再構築と呼ばれるプロセスで、既存のアラインメントから新しいアラインメントを作成する機能が導入されました。ClustalVでは、近隣結合法を使用してツリーを作成するオプションも追加されました。^[5]
• ClustalW : 1994年にリリースされた第3世代。類似性と相違性に基づく配列重み付けオプションを含むプログレッシブアラインメントアルゴリズムを改良しました。さらに、コマンドラインからバッチモードでClustalを実行するオプションが追加されました。^[6]
• ClustalX : 1997年にリリースされ、グラフィカルユーザーインターフェイスを備えた最初のバージョンでした。^[7]
• Clustal2 : これは2007年にClustalWとClustalXの両方をより高い精度と効率で更新しました。^[8]
• ClustalΩ (オメガ) : 2011年にリリースされた現在のバージョン。^{[9] [10]}

Clustalの初期バージョンのガイドツリーは、ペアワイズアラインメントのUPGMAクラスター分析によって構築されたため、CLUSTALという名前が付けられました。 ^{[11] cf. [12]} Clustalの最初の4つのバージョンはアラビア数字（1から4）を使用して番号が付けられていましたが、5番目のバージョンではローマ数字のVが使用されています。 ^{[11] cf. [13] [5]}次の2つのバージョンはラテンアルファベットを使用してアルファベット順に進み、Wは加重、Xは導入された変更を表すXウィンドウを表します。^{[11] cf. [14] [7]} Omegaという名前は、以前の反復からの変更を示すために選択されました。^[11]

Clustalは、一連のペアワイズアラインメントから多重配列アラインメントを段階的に構築するヒューリスティックを使用して配列をアラインメントします。この方法は、配列全体を分析してUPGMA/近隣結合法を使用して距離マトリックスを生成することによって機能します。マトリックス内の配列のスコアからガイドツリーが計算され、その後、類似性の順に配列を段階的にアラインメントすることで多重配列アラインメントを構築するために使用されます。^[15]

Clustal は、主に次の 3 つのステップを通じて複数の配列アライメントを作成します。

1. プログレッシブ アライメント メソッドを使用してペアワイズ アライメントを完了します。
2. ガイド ツリーを作成します(またはユーザー定義のツリーを使用します)。
3. ガイドツリーを使用して多重アライメントを実行します。

これらの手順は、「完全なアライメントを実行する」機能によって自動的に実行されます。その他のオプションは、「ガイド ツリーと系統発生からアライメントを実行する」と「ガイド ツリーのみを生成する」です。

このプログラムは、NBRF/ PIR、FASTA、EMBL/ Swiss-Prot、Clustal、GCC/MSF、GCG9 RSF、GDE など、幅広い入力形式を受け入れます。

出力形式は、Clustal、NBRF/ PIR、GCG /MSF、PHYLIP、GDE、NEXUS のいずれか 1 つまたは複数になります。

DNA / RNAアライメントとタンパク質アライメントの両方に同じシンボルが表示されるため、* (アスタリスク) シンボルはどちらにも役立ちますが、DNA/RNA アライメントでは他のコンセンサス シンボルは無視する必要があります。

ギャップ開始ペナルティとギャップ拡張ペナルティのパラメータはユーザーが調整できます。

オリジナルの Clustal ソフトウェアは、パーソナル コンピューター上で複数の配列アラインメントを生成する計算方法として 1988 年に開発されました。4 年後にリリースされた ClustalV では、いくつかの重要な機能が追加および変更され、オリジナルのソフトウェアが大幅に改良されました。これは完全に書き直されたもので、FortranではなくCで記述されています。

どちらのバージョンも、同じ高速近似アルゴリズムを使用してシーケンス間の類似性スコアを計算し、ペアワイズアラインメントを生成します。このアルゴリズムは、ギャップに対するペナルティを考慮して、2 つのシーケンス間のk タプルマッチの数として類似性スコアを計算します。シーケンスが類似しているほど、スコアが高くなります。シーケンスがスコアリングされると、 UPGMA によって樹形図が生成され、複数のシーケンスアラインメントの順序が生成されます。シーケンスは、設定された順序で降順でアラインメントされます。このアルゴリズムは、非常に大きなデータセットに対応し、高速です。ただし、速度は、特定のシーケンスタイプに対して選択された k タプルマッチの範囲に依存します。^[16]

ClustalV の最も注目すべき追加機能のいくつかは、プロファイルアラインメントと完全なコマンドラインインターフェースオプションです。プロファイルアラインメントを使用すると、ユーザーは 2 つ以上の以前のアラインメントまたはシーケンスを新しいアラインメントにアラインメントし、アラインメントがずれているシーケンス (スコアが低いシーケンス) をアラインメント順序のさらに下に移動できます。これにより、ユーザーは、基本オプションよりも制御しながら、段階的かつ系統的に複数のシーケンスアラインメントを作成することができます。^[15]コマンドラインから実行するオプションにより、複数のシーケンスアラインメントプロセスが迅速化されます。シーケンスは、簡単なコマンドで実行できます。

 clustalv nameoffile . seq 

または

 clustalv / infile = nameoffile.seq​​ 

プログラムは解析する配列の種類を決定します。プログラムが完了すると、多重配列アライメントとデンドログラムの出力は、それぞれ .aln と .dnd 拡張子のファイルに出力されます。コマンドラインインターフェイスはデフォルトのパラメータを使用し、他のオプションは許可しません。^[16]

ClustalW は、他の Clustal バージョンと同様に、複数のヌクレオチドまたはタンパク質配列を効率的にアラインメントするために使用されます。これは、グローバル アラインメントが返されるまで、類似性に基づいてアラインメントの配列に優先順位を付けるプログレッシブ アラインメント メソッドを使用します。ClustalW はマトリックス ベースのアルゴリズムですが、T-CoffeeやDialignなどのツールは一貫性に基づいています。ClustalW は効率的で、同様のソフトウェアと比較して競争力があります。^[要出典]このプログラムでは、グローバル アラインメントを計算するために 3 つ以上の配列が必要です。バイナリ シーケンス アラインメントの場合は、EMBOSSや LALIGN などの他のツールを使用する必要があります。

ClustalW はプログレッシブ アライメント アルゴリズムを使用します。このアルゴリズムでは、シーケンスはアライメント スコアの高い順から低い順にアライメントされます。このヒューリスティックは、グローバルに最適なソリューションを見つけるために必要な時間とメモリの複雑さを制限するために必要です。

まず、アルゴリズムはすべての配列ペア間のペアワイズ距離行列を計算します（ペアワイズ配列アライメント）。次に、近隣結合法は中点ルーティングを使用して全体的なガイドツリーを作成します。^[17]この方法の図を右に示します。最後に、ガイドツリーはグローバルアライメントを生成するための近似テンプレートとして使用されます。

ClustalW は、近隣結合法を使用しているため、 時間の計算量が になります。${\displaystyle O(N^{2})}$

ClustalW2 では、大きな入力サイズに対してより高速な UPGMA を使用するオプションが追加されました。ネイバー結合の代わりにこれを使用するためのコマンドライン フラグは次のとおりです。

-クラスタリング= UPGMA

おおよその例として、10,000 個のシーケンスを入力すると近隣結合に 1 時間以上かかりますが、UPGMA では 1 分以内に完了します。

ClustalW2 では、反復的なアライメント精度も追加されました。このオプションでは効率は上がりませんが、アライメント精度を上げることができます。これは、小規模なデータセットの場合に特に役立ちます。

次のフラグは反復的なアライメントを有効にします。

-反復=アライメント
-反復=ツリー
-数値

最初のオプションは最終的なアライメントを改良します。2番目のオプションは、プログレッシブアライメントステップにスキームを組み込みます。3番目のオプションは反復サイクルの数を指定します。デフォルト値は3に設定されています。^[18]

ClustalW が使用するアルゴリズムはほぼ最適です。これは、分散度合いが大きいデータセットに最も効果的です。このようなデータセットでは、ガイド ツリーを生成するプロセスはノイズの影響を受けにくくなります。ClustalW は、ペアワイズ アライメントとグローバル アライメントを組み合わせて速度を向上させた最初の多重配列アライメント アルゴリズムの 1 つでしたが、この決定により結果の精度が低下します。

2014年に複数の配列アライメントアルゴリズムを比較したところ、ClustalWは、望ましいレベルの精度で結果を生成できる最も高速なアルゴリズムの1つでした。しかし、一貫性に基づく競合製品であるT-Coffeeほど正確ではありませんでした。^[19] MAFFT、T-Coffee、Clustal Omegaのうち、ClustalWは全長配列の精度が最も低いですが、それでも許容範囲内の精度であると考えられています。さらに、ClustalWは調査対象の中で最もメモリ効率の高いアルゴリズムでした。^[19]ソフトウェアの継続的な更新により、ClustalW2はこの速度を維持しながら精度が向上しました。^[18]

ClustalΩ（別名Clustal O、Clustal Omega）は、CおよびC++で書かれた、多重配列アライメントに使用される高速でスケーラブルなプログラムです。シードされたガイドツリーと、2つのプロファイルに焦点を当てた新しいHMMエンジンを使用して、これらのアライメントを生成します。^{[20] [21]このプログラムでは、}多重配列アライメントを計算するために3つ以上の配列が必要です。Clustal Omegaは一貫性ベースであり、すべての多重配列アライメントツールの中で最も高速なオンライン実装の1つとして広く認識されており^{（誰によって？）}、一貫性ベースおよびマトリックスベースのアルゴリズムの両方の中で、精度の点でも依然として高い評価を得ています。

Clustal Omega には、多重配列アライメントを生成するための 5 つの主なステップがあります。

1. ペアワイズアライメントは、k タプル法を使用して生成されます。これは、最適なソリューションが見つかる保証はないが、動的プログラミングを使用するよりも効率的であるヒューリスティックな方法です。
2. シーケンスは修正されたmBed法を使用してクラスタリングされます。^[22] mBed法はシーケンス埋め込みを使用してペアワイズ距離を計算します。
3. k -meansクラスタリング法が適用されます。
4. ガイド ツリーはUPGMA 法を使用して構築されます。右の図では、UPGMA の凝集性により、複数のガイド ツリー ステップを経て 1 つの最終ガイド ツリー構築に至る様子が示されています。各ステップ (フローチャートのダイヤモンド) で、最も近い 2 つのクラスターが結合されます。最終的なグローバル ツリーを評価できるようになるまで、この処理が繰り返されます。
5. 最終的な多重配列アライメントは、HH-SuiteのHHAlignパッケージを使用して、2つのプロファイルHMMを使用して生成されます。プロファイルHMMは、一連のノードで構成される線形状態マシンであり、各ノードは、それが構築されたアライメント内の位置（列）にほぼ対応しています。^[23]

長さ の配列の最適なアラインメントを正確に計算するための時間計算量はであり 、配列の数が少ない場合でも計算が困難です。これを管理するために、Clustal Omega は の計算量を持つ mBed の修正バージョンを使用し、^{[22] [24]}従来の方法と同程度の精度のガイドツリーを生成します。Clustal Omega のガイドツリーの速度と精度は、修正された mBed アルゴリズムの実装によるものです。また、大規模なデータセットのアラインメントを完了するための計算時間とメモリ要件も削減されます。 ${\displaystyle N}$${\displaystyle L}$${\displaystyle O(L^{N})}$${\displaystyle O(N\log N)}$

Clustal Omega の少数のシーケンスに対する精度は、平均して、高品質シーケンスアライナーと見なされるものと非常に似ています。^{[例が必要]}数十万の入力シーケンスを含む非常に大規模なデータセットでは、Clustal Omega は時間、メモリ、結果の精度において他のすべてのアルゴリズムを上回ります。^[25] 100,000 以上のシーケンスを 1 つのプロセッサで数時間で実行できます。

Clustal Omegaは、プロファイル間の比較ではなく、2つのプロファイルの隠れマルコフモデルをアラインメントするHH-SuiteのHHAlignパッケージを使用します。これにより、感度とアラインメントの品質が大幅に向上します。^[25]これをmBed法と組み合わせることで、Clustal Omegaは他の配列アライナーよりも優位になります。

保存されていない末端塩基を持つデータセットでは、Clustal OmegaはProbconsやT-Coffeeよりも正確である可能性がありますが、どちらも一貫性ベースのアルゴリズムであるという事実にもかかわらずです。高い精度スコアを生成するプログラムを使用した効率テストでは、MAFFTが最も速く、Clustal Omegaがそれに続きました。どちらもT-Coffeeよりも高速でしたが、MAFFTとClustal Omegaは実行に多くのメモリを必要としました。^[19]

Clustal2 は、コマンドラインの ClustalW とグラフィカル Clustal X の両方をパッケージ化したリリースです。どちらも新しいツールではありませんが、上記の以前の実装を更新して改良したバージョンです。両方のダウンロードは、Linux、Mac OS X、Windows (XP と Vista の両方) などの多くのオペレーティング システム用に事前コンパイルされています。このリリースは、Web サイトをより整理してユーザー フレンドリにし、ソース コードを最新バージョンに更新するように設計されています。Clustal2 は ClustalW と ClustalX の両方のバージョン 2 であり、これが名前の由来です。過去のバージョンは引き続き Web サイトで見つけることができますが、すべての事前コンパイルは最新のものになっています。

• Clustal ホームページ (Unix/Linux、Mac、Windows から無料でダウンロード可能)
• EBI の Clustal Omega ミラー