利用方法説明
タンパク質配列マルチプルアライメント

メソッド :

TBIAT (Tree-base Best-first Iterative Algorithm with Tree-dependent partitioning)
(ツリー依存限定分割を用いたツリーベース・最良優先探索・反復改善法)

従来、ほとんどのマルチプルアライメントシステムは、ツリーベース法を採用してきた。 ツリーベース法は、配列間の類似距離に従ったツリー状の階層関係に基づいて、配列グループ間のペアワイズアライメントを用いて、マルチプルアライメントを形成する。 しかし、配列間の類似性が低い場合などは、アライメントの精度は不十分である。 一度アライメントに誤りが起こると、その誤りが修正されることはなく、後々まで波及して、最終的なマルチプルアライメントの精度を落す危険性がある。

本アルゴリズムは、ツリーベース法でアライメントが形成される度に、配列グループ間のペアワイズアライメントを反復的に適用して、アライメントの誤りを修正して精度を改善させる。 このような反復改善法では、実用規模のアライメント問題を解くには、発見的手法の導入により効率的に解空間を探索する必要がある。 我々は、ツリー依存限定分割と最良優先探索を採用し、最良優先探索における近傍 探索を並列実装して計算時間を大幅に削減した。

文献 :

十時 泰, 秋山 泰, 鬼塚健太郎, 野口 保, 斎藤 稔, 安藤 誠:
"アミノ酸配列のマルチプルアライメント計算におけるA*アルゴリズムの適用の効果",
情報処理学会研究報告 97-MPS-16-4, pp.19-24 (1997).

M. Hirosawa, Y. Totoki, M. Hoshida, and M. Ishikawa :
"Comprehensive Study on Iterative Algorithms of Multiple Sequence Alignment",
Comput. Applic. Biosci., Vol.11, No.1, pp.13-18 (1995).

制限事項 :

  1. 配列の長さ
    受け付ける配列の長さを 1000 以下に制限しています。
    より長い配列のアライメントを望まれる方は、下記へ御連絡の上、データを お送り下さい。
    papia@m.aist.go.jp.

  2. データの大きさ
    受け付けるデータの大きさ（最も長い配列の長さ × 配列数）を制限しています。
    「探索方法」(配列グループ間のペアワイズアライメントの解法)の指定によって以下のようになります。
    (1) ダイナミックプログラミングの場合は 10000 以下、
    (2) A*アルゴリズムの場合は 5000 以下
    より大きなデータのアライメントを望まれる方は、下記へ御連絡の上、データを お送り下さい。
    papia@m.aist.go.jp.

使用方法 :

  1. 「サービス稼働状況」 をクリックして「マルチプルアライメント」のサービスが ONになっていることを確認して下さい。
  2. 「類似度評価行列」を選択して下さい。
    'BLOSUM45','BLOSUM62','BLOSUM80','PAM120','PAM250' が使用できます。
  3. 「ギャップコスト」を指定して下さい。
    「デフォルト値」と「ユーザ定義」が選べます。
    「ユーザ定義」を選んだ場合は、 各 「ギャップ」 のフィールドにギャップのペナルティコストを 入力して下さい。
    • ギャップ開始 : ギャップ開始のペナルティコスト
    • ギャップ延長 : ギャップ延長のペナルティコスト
    • ギャップ外側 : ギャップ外側のペナルティコスト
    「ギャップ」のペナルティコストは全て 0 以上 100 以下の範囲の整数 でなければなりません。
  4. 「探索方法」(配列グループ間のペアワイズアライメントの解法)を指定して下さい。
    「ダイナミックプログラミング」と「A*アルゴリズム」が選べます。
    「ダイナミックプログラミング」を選んだ場合は、「DPカットオフ率」を設定して下さい。
    「DPカットオフ率」 とはダイナミックプログラミングの探索空間の削除率です。 ダイナミックプログラミングは配列群間のペアワイズアライメントを 行なう時に用いられます。
    「ツリーベース部」 と 「反復改善部」 にそれぞれカットオフ率を入力 します。
    5. 「DPカットオフ率」 の入力値は 0 以上 100 以下の範囲の整数 でなければなりません。
  5. 「ラベル=」 フィールドにはデータのタイトルを 入力して下さい。
  6. 「アライメントする配列」 のテキストエリアに配列データを カットアンドペーストして下さい。
    以下の３つのデータ形式 が使用できます。
    5.1.
    Fasta 形式
    例 : 
    >CSRC_HUMAN
KLGQGCFGEVWMGTWNGTTRVAIKTLKPGTMSPEAFLQEAQVMKKLRHEKLVQLYAVVSEEPIYIVTEYMSKGSLLDFLK
>CABL_HUMAN
KLGGGQYGEVYEGVWKKYSLTVAVKTLKEDTMEVEEFLKEAAVMKEIKHPNLVQLLGVCTREPPFYIITEFMTYGNLLDY
>EPH_HUMAN
IGEGEFGEVYRGTLRLPSQDCKTVAIKTLKDTSPGGQWWNFLREATIMGQFSHPHILHLEGVVTKRKPIMIITEFMENGA
>FER_HUMAN
LLGKGNFGEVYKGTLKDKTSVAVKTCKEDLPQELKIKFLQEAKILKQYDHPNIVKLIGVCTQRQPVYIIMELVSGGDFLT
    5.2.
    １行形式 : (ラベル) (アミノ酸配列)
    一つの配列が一行で入力されていなければなりません。
    例 : 
    CSRC_HUMAN  KLGQGCFGEVWMGTWNGTTRVAIKTLKPGTMSPEAFLQEAQVMKKLRHEKLVQLYAVVSEEPIYIVTEYMSKGSLLDFLK
CABL_HUMAN  KLGGGQYGEVYEGVWKKYSLTVAVKTLKEDTMEVEEFLKEAAVMKEIKHPNLVQLLGVCTREPPFYIITEFMTYGNLLDY
EPH_HUMAN   IGEGEFGEVYRGTLRLPSQDCKTVAIKTLKDTSPGGQWWNFLREATIMGQFSHPHILHLEGVVTKRKPIMIITEFMENGA
FER_HUMAN   LLGKGNFGEVYKGTLKDKTSVAVKTCKEDLPQELKIKFLQEAKILKQYDHPNIVKLIGVCTQRQPVYIIMELVSGGDFLT
    5.3.
    ラベルなし形式 : (アミノ酸配列のみ)
    一つの配列が一行で入力されていなければなりません。
    例 : 
    KLGQGCFGEVWMGTWNGTTRVAIKTLKPGTMSPEAFLQEAQVMKKLRHEKLVQLYAVVSEEPIYIVTEYMSKGSLLDFLK
KLGGGQYGEVYEGVWKKYSLTVAVKTLKEDTMEVEEFLKEAAVMKEIKHPNLVQLLGVCTREPPFYIITEFMTYGNLLDY
IGEGEFGEVYRGTLRLPSQDCKTVAIKTLKDTSPGGQWWNFLREATIMGQFSHPHILHLEGVVTKRKPIMIITEFMENGA
LLGKGNFGEVYKGTLKDKTSVAVKTCKEDLPQELKIKFLQEAKILKQYDHPNIVKLIGVCTQRQPVYIIMELVSGGDFLT
  7. 入力フォームを初期状態に戻したいときは 'Reset this form' ボタンをクリックします。
  8. 'Service status' ボタンでサービスが ON になっている ことを確認します。
  9. 'Submit' ボタンをクリックすると処理が開始されます。
  10. 計算結果例
PAPIAシステム, papia@m.aist.go.jp
Copyright (c) 1997-2000, 技術研究組合 新情報処理開発機構 並列応用つくば研究室
Copyright (c) 2001, 独立行政法人 産業技術総合研究所 生命情報科学研究センター