博 士 論 文 概 要
論 文 題 目
An algorithm for alignment of multiple biological sequences with generalized gap
penalty functions
一般化ギャップペナルティ関数を用いた 生物配列のマルチプルアラインメント
アルゴリズム
申 請 者
山田 真介
Shinsuke Yamada
情報・ネットワーク専攻 並列・分散アーキテクチャ研究
2008 年 1 月
Ｎｏ.
1 ヒトゲノムをはじめとする様々な生物種のゲノムが解読され、計算機の速度向上率を上回るペース で DNA の塩基配列や、タンパク質のアミノ酸配列などの生物配列が蓄積されている。ゲノムとは、全 遺伝情報のことであり、DNA 塩基配列として保持される。従って、生物種の違いはゲノムの違いである と言うことができる。同様に DNA 塩基配列から転写・翻訳というプロセスを経て合成されるタンパク 質についても、その構成要素である個々のアミノ酸の相違が立体構造や機能の変化となって表れる。そのため、タンパク質の立体構造や遺伝子発現などの高次の情報も配列情報に支配されている。
進化の過程において、配列上の塩基ないしアミノ酸（まとめて残基と呼ぶ）が別の残基に変化した り（置換）、残基が配列の途中に入ったり（挿入）、ある残基が配列中から欠落したり（欠失）という 現象が起こる。そのため、進化の過程で配列上に生じた置換・挿入・欠失といった現象を反映するよ うに配列中の残基同士を対応づけることが様々な配列解析を行う上で重要である。このように配列中 の残基同士を対応づけたものがアラインメントである。アラインメント中で挿入や欠失により対応さ せることのできない残基には空白文字を対応させ、連続した空白文字のことをギャップと呼ぶ。２配 列間でのアラインメントをペアワイズアラインメント、３配列以上でのアラインメントをマルチプル アラインメントという。最適なペアワイズアラインメントは平均配列長の二乗の計算量で計算可能で ある。マルチプルアラインメントの場合、アラインメントの良さを表す目的関数とその最適化を考え なければならないが、単純な目的関数を用いたとしても最適なマルチプルアラインメントが現実的な 時間内で計算できるのはせいぜい十数配列に限られてしまう。そのため、現実的な計算時間で実用的 なマルチプルアラインメントを得るべく、様々なアルゴリズムが開発されてきた。
主要なマルチプルアラインメントアルゴリズムとして、累進法と反復改善法が挙げられる。累進法 とは、ペアワイズアラインメントからはじめて、徐々にアラインメントを組み上げて最終的なマルチ プルアラインメントを得る方法である。アラインメントを行う順番は、配列ペア間の距離を基に計算 される系統樹に従って決定されることが多い。累進法では、高速にアラインメントを計算することが 可能であるものの、途中段階のアラインメントに生じたエラーを取り除くことが出来ないため、最終 的なアラインメントの精度は反復改善法に比べて低下することが多い。累進法の代表的なアルゴリズ ムとして ClustalW、T-Coffee、POA などを挙げることができる。
一方、反復改善法は、累進法などで得られたアラインメントに対し、アラインメントを２つに分割 し、それらのアラインメントから再び１つのアラインメントを計算する、ということを繰り返す方法 である。そのため、アラインメント中のエラーを取り除くことが可能となる。多くのアルゴリズムで は、系統樹の枝を切断する形でアラインメントを２つに分割する。反復改善法では、累進法に比べて 計算量が多いものの、概ね高精度なアラインメントを得ることができる。Prrn、MAFFT、ProbCons、MUSCLE、
DIALIGN-T などが主要な反復改善アルゴリズムである。
累進法であれ、反復改善法であれ、繰り返し用いられるアルゴリズムがグループ間アラインメント
アルゴリズムである。グループ間アラインメントアルゴリズムとは、２つの配列グループ（アライン メントと同義）から１つのアラインメントを計算する方法である。ペアワイズアラインメントと異な り、グループ内部に様々な長さのギャップが既に存在しているため、それらの扱いに注意を要する。
アラインメントアルゴリズムは、比較の仕方によって２つのタイプに分けられる。１つが配列全体 同士を比較するグローバルアラインメントアルゴリズムであり、もう１つが部分配列同士の比較を行 うローカルアラインメントアルゴリズムである。アラインメントアルゴリズムの比較評価を行った論 文において（a）グローバルなアルゴリズムの方がローカルなアルゴリズムよりも多くの場合において アラインメント精度が良い、（b）進化の過程で長い挿入や欠失が生じた配列を含むアラインメントの 場合にはローカルなアルゴリズムの方が概ね高精度である、ということが報告されている。
上記の背景のもと、本研究ではグローバルアラインメントを行う反復改善法によるアラインメント 精度の向上と計算の高速化を目的とする。具体的には、主に以下の３点について提案・検証を行って いる。
(1) 区分的線形関数をギャップペナルティとして用いたグループ間アラインメントアルゴリズ ムの提案。
(2) maximal expected accuracy (MEA)に基づいたグループ間アラインメントアルゴリズムの有 効性について検証。
(3) グループ間アラインメントされる領域を制限するアンカーリングアルゴリズムや反復改善 数を削減するグルーピングアルゴリズムの提案。
（１）のアルゴリズムは、長い挿入や欠失の生じた配列を含むアラインメント精度を向上させるこ とが主要な目的である。MAFFT や ProbCons、T-Coffee では、グローバルなペアワイズアラインメント とローカルなペアワイズアラインメントから整合性スコアを計算し、最終的なマルチプルアラインメ ントの計算時にその整合性スコアを用いることで精度を向上させているが、整合性スコアの計算には 配列数の二乗のメモリと計算量が必要になるという問題点がある。それに対し、本研究ではグループ 間アラインメントアルゴリズムに使用するギャップペナルティ関数として、区分的線形ギャップペナ ルティ（複数の線形関数を組み合わせた関数）を用いることで、精度向上を図る。従来のアフィンギ ャップペナルティ（切片が０でない線形関数）では長いギャップに対して大きなペナルティを与え過 ぎるという問題点があるが、区分的線形ギャップペナルティによりこの問題を回避できる。
（２）に関しては ProbCons でも用いられているが、他の配列解析の分野で MEA に基づく手法の有効 性が最近いくつかの論文で報告されており、本研究においても検証を行い、精度向上に有効であるこ とを示す。
（３）では、両アルゴリズムとも最終的なアラインメント精度の低下を最小限に抑えつつ、計算量 を削減させることを目的とする。アンカーリングとは、与えられたアラインメントに対し、アライン
Ｎｏ.
3 メント中で保存された領域をアンカーポイントとして抽出することである。アンカーポイントを固定 してグループ間アラインメントされる領域を制限することで、反復改善時の計算において１回の計算 量を減らすことが可能となる。グルーピングとは、アラインメントから計算される系統樹に基づき、保存された部分アラインメントを抽出することである。その部分アラインメントを変更するような分 割をしないことで反復改善の回数そのものを削減し、計算時間の大幅な短縮を実現する。
上 記 の （ １ ） か ら （ ３ ） の ア ル ゴ リ ズ ム を PRIME と い う プ ロ グ ラ ム と し て 実 装 し 、 http://prime.cbrc.jp/にてソースコードを GPL2 ライセンスの下で公開している。
本論文は８章から成り、その内容について以下で述べる。
２章では、本論文で用いる記号を導入し、マルチプルアラインメント問題について定義する。
３章において、これまでに開発されてきた代表的なマルチプルアラインメントアルゴリズムを示す。
４章では、区分的線形ギャップペナルティを用いたグループ間アラインメントアルゴリズムについ て提案する。まずは既存のアフィンギャップペナルティに用いたグループ間アラインメントアルゴリ ズムについて述べる。次に区分的線形関数ギャップペナルティを導入し、区分的線形ギャップペナル ティを用いたグループ間アラインメントアルゴリズムについて提案する。
５章では、maximal expected accuracy に基づいたグループ間アラインメントアルゴリズムについて 述べる。MEA 法は、正しくアラインメントされると期待される残基ペアの数を最大化する方法である。
その正しさを表す指標としてペア HMM と呼ばれる隠れマルコフモデルから計算される事後確率を使用 する。本論文で用いたペア HMM の実際のモデルを示し、事後確率の計算アルゴリズムを述べる。そし て、事後確率をスコアリング関数として用いたグループ間アラインメントアルゴリズムについて記す。
６章では、アンカーリングアルゴリズムとグルーピングアルゴリズムについて提案する。両アルゴ リズムとも、２種類のアルゴリズムについて提案を行っている。一方は、単体のアラインメント中の 保存度に基づく方法で、もう一方は、反復改善の前と後の２つのアラインメントを比較する方法であ る。まず、保存度に基づくアンカーリングとグルーピングについて示す。次に、２つのアラインメン トの比較によるアンカーリングとグルーピングについて述べる。
７章では、４章から６章で述べたアルゴリズムについて、上述の他のマルチプルアラインメントア ルゴリズムも含めた評価を行う。使用する BAliBASE ベンチマークと PREFAB ベンチマークについて紹 介した後、両ベンチマークの違いやアラインメント精度を表す評価尺度について説明する。最後に、
ベンチマーク結果を述べ、PRIME が世界最高精度を誇るプログラムと統計的に見ても同等のアラインメ ント精度を実現でき、またアンカーリングやグルーピングにより精度の低下を抑えつつ高速化できる ことを示す。
８章において、本論文のまとめを行い、結論を述べる。また、今後の課題と展望について記す。
早稲田大学 博士（工学） 学位申請 研究業績書
氏 名 山田 真介 印
（２００７年１２月 現在）
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）
論文
○
○
講演
○
○
○
○
○
○
○
[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.
Ｎｏ.
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.
その他
（講演）山田真介, 山名早人, 野口保：タンパク質立体構造に基づいたアラインメント 中の保存領域抽出手法の改良，第７回日本蛋白質科学会年会，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 月．
（講演）山田晃太郎，山田真介，山名早人，野口保：タンパク質立体構造に基づく保存 領域の自動抽出，第６回日本蛋白質科学会年会，2006 年 4 月．
（講演）山田真介，富井健太郎：構造プロファイルを用いた局所構造予測法の開発 「産総研 生命情報科学人材養成コース」設立１周年記念シンポジウム，2002 年 10 月．
（講演）山田真介，富井健太郎，太田元規，秋山泰，山名早人：構造プロファイルによ る局所構造予測法の開発，第２回日本蛋白質科学会年会，2002 年 6 月．
以上
早稲田大学 博士（工学） 学位申請 研究業績書
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）
