（５５）３次元ＤＰ法によるマルチプル・アライメント


	マ シ ン：PIM
	環　　境：PIMOS, SIMPOS
	言　　語：KL1, ESP
	ソース量：0.5 MB
	文　　書：なし

概要

タンパク質のアミノ酸配列を解析するソフトウェアである。

        Generator:             ３次元ＤＰを行うプロセスネットワークを構築する。
        Cost Evaluate Process: コストを計算して実際にＤＰを行う。

類似する複数のタンパク質のアミノ酸配列のデータを整列させるソフトウェアである。整列とはアミノ酸配列の共通部分および類似部分を縦に並べることを意味する。アミノ酸間の類似性は、既に生物学的に定義されている。例えば、

    HEKLLHPGIQKTTKLFGETTY
    LHQLTHLSFSKMKALLERSHSPYY
    ELHSFTHCGQTALTLQ

という３つのタンパク質のアミノ酸配列は、

    --HEKLLHPGIZKTTKLF-GET--YY
    -LHQ-LTHLSFSKMKALLERSHSPYY
    ELHS-FTHCG---QTAL--TLQ----
      ^    ^        ^
      |    |        |

のように整列させることができる。ここで挿入されているハイフンは、進化過程で起きた欠失を表す。整列結果の中でよく保存している部分「↑」は、タンパクの機能上重要な部分に対応する。

このプログラムはダイナミックプログラミング法 (ＤＰ)という組み合わせ最適化問題を解く際によく使用される方法を並列化して実装されている。３次元ＤＰを用いており。３本の配列を複数組実行することができる。