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

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

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) では 両アルゴリズムとも最終的なアラインメント精度の低下を最小限に抑えつつ 計算量を削減させることを目的とする アンカーリングとは 与えられたアラインメントに対し アライン

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

早稲田大学博士 ( 工学 ) 学位申請研究業績書 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. 2007.( 投稿中 ) [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. 2006. 講演 [3] 山田真介, 後藤修, 山名早人 : マルチプルアラインメントプログラム PRIME の速度 精度両面からの改良, 情処研報 (MPS67/BIO11),Vol.2007, No.128, pp.267-274, 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. 2007. [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. 2007. [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. 2005. [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. 2004.

早稲田大学博士 ( 工学 ) 学位申請研究業績書 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. 2004. 著書 その他 [12] Osamu Gotoh, Shinsuke Yamada, Tetsushi Yada: Multiple sequence alignment, In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman & Hall, pp.3-1--3-36, Dec. 2005. ( 講演 ) 山田真介, 山名早人, 野口保 : タンパク質立体構造に基づいたアラインメント中の保存領域抽出手法の改良, 第 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. ( 講演 ) 山田真介, 山田晃太郎, 山名早人, 野口保 : タンパク質立体構造に基づく保存領域の自動抽出, 次世代コンピューティングシステムに関する合同ワークショップ,2006 年 7 月. ( 講演 ) 山田晃太郎, 山田真介, 山名早人, 野口保 : タンパク質立体構造に基づく保存領域の自動抽出, 第 6 回日本蛋白質科学会年会,2006 年 4 月. ( 講演 ) 山田真介, 富井健太郎 : 構造プロファイルを用いた局所構造予測法の開発 産総研生命情報科学人材養成コース 設立 1 周年記念シンポジウム,2002 年 10 月. ( 講演 ) 山田真介, 富井健太郎, 太田元規, 秋山泰, 山名早人 : 構造プロファイルによる局所構造予測法の開発, 第 2 回日本蛋白質科学会年会,2002 年 6 月. 以上

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