Clustal

Clustalは広く用いられている多重整列プログラムである。現在はコマンドライン版のClustal Wとグラフィカルインターフェース（GUI）版のClustal Xとがある。欧州バイオインフォマティクス研究所のFTPサーバから入手できる。

アルゴリズム 
以下の3つの段階を踏む。
1対1の整列（ペアワイズアラインメント）を行う
1対1の整列を総当たりで行い、配列一致度の行列を作成する。
配列一致度に基づいて樹形図（Guide Tree）を得る
配列一致度を距離尺度に用いて階層型クラスタリングを行う。この際のアルゴリズムは近隣結合法（または非加重結合法）が用いられている。
樹形図に沿って配列を追加しながら整列を行う
最も一致度の高い配列ペアからはじめて、樹形図に沿って1つずつ配列を追加しながら整列させていくことで効率的に多重整列を得る。

これらは自動的に行われるが、ガイドツリーのみを計算させたり、ガイドツリーを指定して多重整列のみを行わせることもできる。

入出力 
入力ファイルとしてはNBRF/PIR, FASTA, EMBL/Swissprot, Clustal, GCC/MSF, GCG9 RSF , GDEの形式を受け付け、Clustal, NBRF/PIR, GCG/MSF, PHYLIP, GDE, NEXUSの形式で出力することができる。

系統解析 
多重整列を行う目的の1つに分子系統解析があるが、Clustalで系統解析を行うことも可能である。ただし近隣結合法を用いたきわめてシンプルな解析に限られる。多重整列の際に作成される樹形図 (.dnd) は系統樹ではないことに注意が必要である。

履歴 
1988年、Higginsにより最初のバージョンが公表される。これは上記アルゴリズムの3段階に対応する3つのプログラム (Clustal1, Clustal2, Clustal3) からなるパッケージであり、すべてIBM AT機用のMicrosoft Fortranで書かれていた。ペアワイズアラインメントと多重整列はWilbur and Lipmanのアルゴリズム、クラスタリングは非加重結合法を使用していた。
1989年、HigginsによりClustal3の改良版Clustal4が公表される。これは多重整列のアルゴリズムにMyers and Millerの変法を採用することで、少ないメモリでも類縁性の低い配列を整列できるようにしたものである。
1992年、HigginsによりClustal Vが公表される。これはC言語 (C89) で書き直された単一のプログラムであり、VAX/VMS・Unix・Macintosh・MS-DOSで利用可能だった。入出力のファイル形式が多様になり、整列済みファイルの再整列や近隣結合法による系統樹の作成ができるようになった。
1994年、ThompsonによってClustal Wが公表される。クラスタリングが近隣結合法に変更され、多重整列にも配列ごとに重み付けを行うなど様々な改良が施されている。以後継続的にチューニングが施され続けている。
1997年、ThompsonによってGUI版のClustal Xが公表される。GUIツールキットとしてNCBIのvibrant toolboxを使用しており、X Window System・Macintosh・Microsoft Windowsで利用できる。多重整列された配列をウィンドウシステムによってスクロールしながら調べることができ、低クオリティ領域をマークしてそこだけ整列し直すようなことが可能になった。
2007年、LarkinによってClustal WおよびClustal Xのバージョン2.0が公表される。これはC++によって書き直されており、これによりClustal XはツールキットとしてQtを利用するように変更された。機能面での進歩は大きくなく、クラスタリングのアルゴリズムとして非加重結合法を選べるようになったことと、配列を一旦取り除いてから再度整列し直すことで結果を改善する機能が追加されたのみである。

その他 
SGIによるものをはじめとして、いくつかの並列化バージョンが開発されている。Clustal Wを高速に実行するためのFPGAによる専用ハードウェアがProgeniq社によって開発されている。

参考文献 

バイオインフォマティクス