(94) 遺伝的アルゴリズムを用いたアライメントシステム


	マ シ ン：PIM/UNIXマシン
	環　　境：PIMOS/UNIX, KLIC
	言　　語：KL1
	ソース量：0.3 MB
	文　　書：マニュアル (日本語 / 英語)

概要

マルチプルアライメントの問題を組合せ最適化問題と捉え、遺伝的アルゴリズ ムの手法を適用した並列システムである。

特徴

本システムは、遺伝的アルゴリズムをマルチ個体群の方式で並列計算機上に実 装したものであり、実用規模のアライメント問題でも、準最適な解を比較的高 速に求めることができる。本システムは、単純なマルチ山登り並列より、早期 に収束に至り、かつ、最良優先探索並列のような局所最適解に陥ることが少な い。また、ときどき良いスコアの解の部分アライメントを繋ぎ合わせる操作 (クロスオーバー) で、改善の効率を向上させている。

機能

PIM／m 256台構成において、80文字の蛋白質配列22本のアライメントが、2時 間程で求まる。1台の PE をマスターとし、残りの PE は、それぞれ1つのアラ イメントの改善を請負い、並列で動く。世代はシステムタイマーで80秒ごとに 管理され、データはマスターに集められ、個体群の管理、移民や淘汰の処理が 行われる。各個体群間では淘汰率が異なり、比較的悪いスコアの解は、淘汰率 の低い個体群で広く探索し、比較的良いスコアの解は、淘汰率の高い個体群で 集中的に近傍を探索するように、実装されている。なお、Ｘウインドウ上で、 パフォーマンスをオンラインでグラフ表示できるツールが附属している。

本システムはKLIC処理系により、UNIXオペレーティング・システムの基本部分 が動作する計算機システム上で動作可能である。

ＦＴＰ

www-admin@icot.or.jp