- PDF Free Download

Size: px

Start display at page:

Download "　"

るるみなみこし
9 years ago
Views:

1 早稲田大学大学院理工学研究科博士論文概要論文題目 An algorithm for alignment of multiple biological sequences with generalized gap penalty functions 一般化ギャップペナルティ関数を用いた生物配列のマルチプルアラインメントアルゴリズム申請者山田 Shinsuke 真介 Yamada 情報ネットワーク専攻並列分散アーキテクチャ研究 2008 年 1 月

2 No.1 ヒトゲノムをはじめとする様々な生物種のゲノムが解読され計算機の速度向上率を上回るペースで DNA の塩基配列やタンパク質のアミノ酸配列などの生物配列が蓄積されているゲノムとは全遺伝情報のことであり DNA 塩基配列として保持される従って生物種の違いはゲノムの違いであると言うことができる同様に DNA 塩基配列から転写翻訳というプロセスを経て合成されるタンパク質についてもその構成要素である個々のアミノ酸の相違が立体構造や機能の変化となって表れるそのためタンパク質の立体構造や遺伝子発現などの高次の情報も配列情報に支配されている進化の過程において配列上の塩基ないしアミノ酸 ( まとめて残基と呼ぶ ) が別の残基に変化したり ( 置換 ) 残基が配列の途中に入ったり( 挿入 ) ある残基が配列中から欠落したり( 欠失 ) という現象が起こるそのため進化の過程で配列上に生じた置換挿入欠失といった現象を反映するように配列中の残基同士を対応づけることが様々な配列解析を行う上で重要であるこのように配列中の残基同士を対応づけたものがアラインメントであるアラインメント中で挿入や欠失により対応させることのできない残基には空白文字を対応させ連続した空白文字のことをギャップと呼ぶ 2 配列間でのアラインメントをペアワイズアラインメント 3 配列以上でのアラインメントをマルチプルアラインメントという最適なペアワイズアラインメントは平均配列長の二乗の計算量で計算可能であるマルチプルアラインメントの場合アラインメントの良さを表す目的関数とその最適化を考えなければならないが単純な目的関数を用いたとしても最適なマルチプルアラインメントが現実的な時間内で計算できるのはせいぜい十数配列に限られてしまうそのため現実的な計算時間で実用的なマルチプルアラインメントを得るべく様々なアルゴリズムが開発されてきた主要なマルチプルアラインメントアルゴリズムとして累進法と反復改善法が挙げられる累進法とはペアワイズアラインメントからはじめて徐々にアラインメントを組み上げて最終的なマルチプルアラインメントを得る方法であるアラインメントを行う順番は配列ペア間の距離を基に計算される系統樹に従って決定されることが多い累進法では高速にアラインメントを計算することが可能であるものの途中段階のアラインメントに生じたエラーを取り除くことが出来ないため最終的なアラインメントの精度は反復改善法に比べて低下することが多い累進法の代表的なアルゴリズムとして ClustalW T-Coffee POA などを挙げることができる一方反復改善法は累進法などで得られたアラインメントに対しアラインメントを2つに分割しそれらのアラインメントから再び1つのアラインメントを計算するということを繰り返す方法であるそのためアラインメント中のエラーを取り除くことが可能となる多くのアルゴリズムでは系統樹の枝を切断する形でアラインメントを2つに分割する反復改善法では累進法に比べて計算量が多いものの概ね高精度なアラインメントを得ることができる Prrn MAFFT ProbCons MUSCLE DIALIGN-T などが主要な反復改善アルゴリズムである累進法であれ反復改善法であれ繰り返し用いられるアルゴリズムがグループ間アラインメント

3 No.2 アルゴリズムであるグループ間アラインメントアルゴリズムとは 2つの配列グループ ( アラインメントと同義 ) から1つのアラインメントを計算する方法であるペアワイズアラインメントと異なりグループ内部に様々な長さのギャップが既に存在しているためそれらの扱いに注意を要するアラインメントアルゴリズムは比較の仕方によって2つのタイプに分けられる 1つが配列全体同士を比較するグローバルアラインメントアルゴリズムでありもう1つが部分配列同士の比較を行うローカルアラインメントアルゴリズムであるアラインメントアルゴリズムの比較評価を行った論文において (a) グローバルなアルゴリズムの方がローカルなアルゴリズムよりも多くの場合においてアラインメント精度が良い (b) 進化の過程で長い挿入や欠失が生じた配列を含むアラインメントの場合にはローカルなアルゴリズムの方が概ね高精度であるということが報告されている上記の背景のもと本研究ではグローバルアラインメントを行う反復改善法によるアラインメント精度の向上と計算の高速化を目的とする具体的には主に以下の3 点について提案検証を行っている (1) 区分的線形関数をギャップペナルティとして用いたグループ間アラインメントアルゴリズムの提案 (2) maximal expected accuracy (MEA) に基づいたグループ間アラインメントアルゴリズムの有効性について検証 (3) グループ間アラインメントされる領域を制限するアンカーリングアルゴリズムや反復改善数を削減するグルーピングアルゴリズムの提案 (1) のアルゴリズムは長い挿入や欠失の生じた配列を含むアラインメント精度を向上させることが主要な目的である MAFFT や ProbCons T-Coffee ではグローバルなペアワイズアラインメントとローカルなペアワイズアラインメントから整合性スコアを計算し最終的なマルチプルアラインメントの計算時にその整合性スコアを用いることで精度を向上させているが整合性スコアの計算には配列数の二乗のメモリと計算量が必要になるという問題点があるそれに対し本研究ではグループ間アラインメントアルゴリズムに使用するギャップペナルティ関数として区分的線形ギャップペナルティ ( 複数の線形関数を組み合わせた関数 ) を用いることで精度向上を図る従来のアフィンギャップペナルティ ( 切片が0でない線形関数 ) では長いギャップに対して大きなペナルティを与え過ぎるという問題点があるが区分的線形ギャップペナルティによりこの問題を回避できる (2) に関しては ProbCons でも用いられているが他の配列解析の分野で MEA に基づく手法の有効性が最近いくつかの論文で報告されており本研究においても検証を行い精度向上に有効であることを示す (3) では両アルゴリズムとも最終的なアラインメント精度の低下を最小限に抑えつつ計算量を削減させることを目的とするアンカーリングとは与えられたアラインメントに対しアライン

4 No.3 メント中で保存された領域をアンカーポイントとして抽出することであるアンカーポイントを固定してグループ間アラインメントされる領域を制限することで反復改善時の計算において1 回の計算量を減らすことが可能となるグルーピングとはアラインメントから計算される系統樹に基づき保存された部分アラインメントを抽出することであるその部分アラインメントを変更するような分割をしないことで反復改善の回数そのものを削減し計算時間の大幅な短縮を実現する上記の (1) から (3) のアルゴリズムを PRIME というプログラムとして実装しにてソースコードを GPL2 ライセンスの下で公開している本論文は8 章から成りその内容について以下で述べる 2 章では本論文で用いる記号を導入しマルチプルアラインメント問題について定義する 3 章においてこれまでに開発されてきた代表的なマルチプルアラインメントアルゴリズムを示す 4 章では区分的線形ギャップペナルティを用いたグループ間アラインメントアルゴリズムについて提案するまずは既存のアフィンギャップペナルティに用いたグループ間アラインメントアルゴリズムについて述べる次に区分的線形関数ギャップペナルティを導入し区分的線形ギャップペナルティを用いたグループ間アラインメントアルゴリズムについて提案する 5 章では maximal expected accuracy に基づいたグループ間アラインメントアルゴリズムについて述べる MEA 法は正しくアラインメントされると期待される残基ペアの数を最大化する方法であるその正しさを表す指標としてペア HMM と呼ばれる隠れマルコフモデルから計算される事後確率を使用する本論文で用いたペア HMM の実際のモデルを示し事後確率の計算アルゴリズムを述べるそして事後確率をスコアリング関数として用いたグループ間アラインメントアルゴリズムについて記す 6 章ではアンカーリングアルゴリズムとグルーピングアルゴリズムについて提案する両アルゴリズムとも 2 種類のアルゴリズムについて提案を行っている一方は単体のアラインメント中の保存度に基づく方法でもう一方は反復改善の前と後の2つのアラインメントを比較する方法であるまず保存度に基づくアンカーリングとグルーピングについて示す次に 2つのアラインメントの比較によるアンカーリングとグルーピングについて述べる 7 章では 4 章から6 章で述べたアルゴリズムについて上述の他のマルチプルアラインメントアルゴリズムも含めた評価を行う使用する BAliBASE ベンチマークと PREFAB ベンチマークについて紹介した後両ベンチマークの違いやアラインメント精度を表す評価尺度について説明する最後にベンチマーク結果を述べ PRIME が世界最高精度を誇るプログラムと統計的に見ても同等のアラインメント精度を実現できまたアンカーリングやグルーピングにより精度の低下を抑えつつ高速化できることを示す 8 章において本論文のまとめを行い結論を述べるまた今後の課題と展望について記す

5 早稲田大学博士 ( 工学 ) 学位申請研究業績書 No.1 氏名山田真介印 (2007 年 12 月現在 ) 種類別題名発表発行掲載誌名発表発行年月連名者 ( 申請者含む ) 論文 [1] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: Improvement in speed and accuracy of multiple sequence alignment program PRIME, IPSJ Transactions on Bioinformatics, Nov ( 投稿中 ) [2] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost, BMC Bioinformatics, Vol.7, Article No.524, Dec 講演 [3] 山田真介, 後藤修, 山名早人 : マルチプルアラインメントプログラム PRIME の速度精度両面からの改良, 情処研報 (MPS67/BIO11),Vol.2007, No.128, pp , 2007 年 12 月. [4] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: Improvement in speed and accuracy of multiple sequence alignment program PRIME, The proceedings of the 2007 annual conference of the Japanese Society for Bioinformatics, Dec [5] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: PRIME: multiple sequence alignment program based on group-to-group sequence alignment algorithm with piecewise linear gap cost, 15th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB) / 6th European Conference on Computational Biology (ECCB), Jul [6] 山田真介, 後藤修, 山名早人 :PRIME: 区分的線形ギャップコストを用いたマルチプルアラインメントプログラム,CBRC2006,2006 年 9 月.( ポスター発表 ) [7] 山田真介 ;PRIME: 区分的線形ギャップコストを用いたマルチプルアラインメントプログラム, CBRC2006,2006 年 9 月.( 依頼講演 ) [8] Shinsuke Yamada and Osamu Gotoh: PRIME - an implementation of a doubly nested randomized iterative refinement strategy with the piecewise linear gap cost, CBRC / International Symposium on Computational Biology & Bioinformatics (ISCBB), Sep [9] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: Extension of Prrn: implementation of a doubly nested randomized iterative refinement strategy under the piecewise linear gap cost 15th International Conference on Genome Informatics (GIW), Dec

6 早稲田大学博士 ( 工学 ) 学位申請研究業績書 No.2 種類別題名発表発行掲載誌名発表発行年月連名者 ( 申請者含む ) [10] 山田真介, 後藤修 : 区分的線形ギャップコストを用いたマルチプルアラインメントアルゴリズムの開発, 産総研生命情報科学人材養成コース最終シンポジウム, 2004 年 9 月. [11] Shinsuke Yamada, Osamu Gotoh and Hayato Yamana: The group-to-group sequence alignment algorithm under the piecewise linear gap cost, 12th International Conference on Intelligent Systems for Molecular Biology (ISMB) / 3rd European Conference on Computational Biology (ECCB), Jul 著書その他 [12] Osamu Gotoh, Shinsuke Yamada, Tetsushi Yada: Multiple sequence alignment, In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman & Hall, pp , Dec ( 講演 ) 山田真介, 山名早人, 野口保 : タンパク質立体構造に基づいたアラインメント中の保存領域抽出手法の改良, 第 7 回日本蛋白質科学会年会,2007 年 5 月. ( 講演 )Shinsuke Yamada, Kouratou Yamada, Hayato Yamana, Tamotsu Noguchi: Automatic extraction of conserved region from alignment based on protein structure, 5th East Asian Biophysics Symposium (EABS) / 44th Annual Meeting of the Biophysical Society of Japan (BSJ), Nov ( 講演 ) 山田真介, 山田晃太郎, 山名早人, 野口保 : タンパク質立体構造に基づく保存領域の自動抽出, 次世代コンピューティングシステムに関する合同ワークショップ,2006 年 7 月. ( 講演 ) 山田晃太郎, 山田真介, 山名早人, 野口保 : タンパク質立体構造に基づく保存領域の自動抽出, 第 6 回日本蛋白質科学会年会,2006 年 4 月. ( 講演 ) 山田真介, 富井健太郎 : 構造プロファイルを用いた局所構造予測法の開発産総研生命情報科学人材養成コース設立 1 周年記念シンポジウム,2002 年 10 月. ( 講演 ) 山田真介, 富井健太郎, 太田元規, 秋山泰, 山名早人 : 構造プロファイルによる局所構造予測法の開発, 第 2 回日本蛋白質科学会年会,2002 年 6 月. 以上

7 早稲田大学博士 ( 工学 ) 学位申請研究業績書 No.3 種類別題名発表発行掲載誌名発表発行年月連名者 ( 申請者含む )

多重配列アラインメント最近のソフトウェアについてた. 計算時間は数分程度である. また, 類似性の高い入力配列に限定すれば, 計算量は配列の長さの 1 乗に比例する. そのため Pfam や ASTRAL など大量のアラインメントを実行する必要のあるプロジェクトで TCoffee などとともに使

多重配列アラインメント最近のソフトウェアについてた. 計算時間は数分程度である. また, 類似性の高い入力配列に限定すれば, 計算量は配列の長さの 1 乗に比例する. そのため Pfam や ASTRAL など大量のアラインメントを実行する必要のあるプロジェクトで TCoffee などとともに使生物物理 46(6),312-317(2006) 多重配列アラインメント最近のソフトウェアについて九州大学デジタルメディシンイニシアティブバイオインフォマティクス部門かずさ DNA 研究所,CREATE, 千葉県産業振興センター加藤和貴三沢計治 Multiple sequence alignment is an important tool for computational analysis