近年、分子生物学において配列解析技術などの急速な進展にともない、DNA、RNA、蛋白質といった生物配列情報が爆発的に増大しており、そのため、そういった大量のデータを効率的に処理するための様々な高速なアルゴリズムが必要となってきている。これらの問題において最も重要な基盤技術の一つは、配列のアライジメント技術やモチーフ発見技術、DNAや蛋白質などの生物データベースの検索技術などの配列比較及び検索の技術である。

これらの技術は、パタンマッチング技術とも呼ばれる。本論文では、そういった配列比較や検索などのパタンマッチングの問題に対し高速なアルゴリズムを提供することで、分子生物学上非常に重要ないくつかの問題を効率的に解決する。さらに、それらのアルゴリズムの多くについて、実際に大規模な生物学的データを用いた実験を通じて、性質及び性能を検証する。

本論文では、まず、分子生物学全般で極めて多用されている最も基本的かつ重要な配列比較技術の一つであるマルチプル・アラインメント問題をとりあげる。この問題には、計算論的に得られる最適解が生物学的には最適ではない、という問題がある。これに対し本論文では2つの手法を提案する。まず一つ目の手法として、多くの準最適解を出力することで代替の解を提供する、という解決法を考えられるが、そのような準最適解はわずかに異なるだけの解が極めて多くあり、欲しい解を探すのが困難である。そこで、本論文ではいかなるアラインメントが列挙する必要がないかを論じ、必要なアラインメントだけを高速に列挙するアルゴリズムを提案する。また、このアラインメント問題においては、スコア行列などのパラメータを固定して求めた従来の最適解は生物学的に最適であるとは限らないともいわれている。そこで本論文ではさらに二つ目の手法として、パラメータを変化させた時の解をすべて得るための効率的なパラメータ空間の探索技法について議論する。

　次に本論文では、先に述べたアラインメントの一変形であるスプライスト・アラインメントという手法を用いて、cDNAライブラリに含まれる配列集合を選択的スプライス集合と呼ぶ集合にクラスタリングするという問題を扱う。最近ヒトゲノムの遺伝子数と実際の蛋白質数の違いがわかってきたことで非常に脚光を浴びている選択的スプライシングの研究において、このクラスタリング結果は極めて有用である。また、本論文でも次に扱う遺伝子発見のツール等の学習セットとしても有用である。本論文では、この問題を解くための高速かつ正確なアルゴリズムを提案する。さらに、マウスの大規模なcDNAライブラリであるFANTOMを用いた実験を通して、このアルゴリズムの性能を検証する。

　さらに、分子生物学研究上最も重要な問題の一つである、遺伝子発見あるいは遺伝子同定と呼ばれる問題を扱う。この問題に対しては、従来から様々な手法が提案されてきているが、それらは主に2種類に分類することができる。一つは隠れマルコフモデルなどの統計学的な手法を用いる方法であり、もう一つは異なる種の間の配列比較やデータベースからの類似配列検索に基づくパタンマッチング的手法である。前者は統計的な傾向が種によって異なるため、自身の種かそれに近い種の十分な学習セットがない場合うまく推定できない、という問題がある。一方、後者は類似しているものがないものについては全く見つけることができない、などの問題がある。それに対し、本論文では、両者の長所をあわせ持つような従来にはない全く新しい手法を提案する。この手法は、きわめて大規模なパタンデータベースのパタンを検索し、それらのパタンの統計的振舞いに基づいて遺伝子発見を行なう。この方法は、全く新しい学習セットのないような種のゲノムに対しても遺伝子を従来手法以上に正確に推定することができることが可能である。また、一般的にはパタンマッチング手法による遺伝子発見は統計的な手法より計算時間が大きいことが多いという問題点があるが、この手法では極めて大きなパタンデータベースからの高速検索を行なうための新しいパタン検索アルゴリズムを提案することで、一般的な統計的手法と比べても十分高速な遺伝子同定を実現している。本論文では、さらにこの手法を実際に様々な原核生物ゲノムに適用し、検証を行なう。

　RNAなどの生物配列は、それが形作る立体構造がその性質に極めて影響を及ぼすことが知られている。本論文では、最後に、RNAなどの生物配列や2次構造データベースにおいて、接尾辞木というデータ構造を用いて、頻出する構造を高速に捜し出す手法を提案する。

　接尾辞木は、テキストなどから頻出文字列を発見したり、キーワードを検索する際に非常に重要かつ有用な検索のためのデータ構造である。本論文では、まず、同様の構造を持ち得るようなRNAの部分配列とは何かを考察し、それを考慮するように接尾辞木を一般化したデータ構造とそれを構築する高速なオンライン・アルゴリズムを提案する。また、RNAの2次構造は木構造で表現できることが知られている。さらに、そのような木構造から様々なパタンを検索あるいは発見することができる木に対する接尾辞木というものも知られているが、本論文ではそれに対する既存の最良の計算量より良いアルゴリズムを提案する。

　本論文では、これらのアルゴリズムを通じて、配列比較や検索といった効率的なパタンマッチング的技法を用いることで、いかに分子生物学における様々な重要な問題を解決することができるかを示す。

　本論文は、タンパク質やDNAといった生物における塩基配列情報に対する比較及び検索のための高速なアルゴリズムの研究を行ない、さらに計算機実験を通じてそれらの性能を検証し、生物学上重要な実問題への応用も行なったものである。

　本論文は七章からなり、第一章では、本論文で扱うアルゴリズム及び生物学上の諸問題の背景ならびに相互の関連性が概観されている。

　第二章は、第三章以降においてよく触れられる問題とそれに対する従来のアルゴリズムについて解説を行なっている。

　第三章は、複数の塩基配列を比較する重要な手法であるマルチプル・アラインメントを扱っている。この手法の計算上の最適解が生物学上最も最適な解であるとは限らないといわれている問題に対し、本章では最適解の代替解を提供する手法として、準最適解を代替の解として高速に列挙する手法と、使用するパラメータを変化させた場合の最適解の変化を効率的に列挙する手法を提案し、さらに、計算機実験を行なうことでこれらの手法の有効性も示した。

　第四章は、cDNA配列の集合を選択的スプライス集合と呼ばれる集合に分類する問題を扱っている。この分類はスプライスト・アラインメントという配列比較手法を用いることで正確に行なえるが、非常に計算量が大きい。これに対し、本章では、高速化のためのアルゴリズムを提案し、さらに実際のマウスの大規模cDNAライブラリを用いた計算でも、実時間内に高精度な分類が可能であることを示した。

　第五章は、大規模モチーフ検索に基づく遺伝子発見の全く新しい手法を提案している。この問題の従来の手法は統計に基づく手法と相同性検索による手法に分けられるが、本章の手法は、前者で困難な十分な学習セットのないような場合や、後者で困難な類似遺伝子が存在しない場合においても遺伝子を正確に推定できることを、計算機実験を通じて示した。さらに、モチーフ検索の高速アルゴリズムも提案することで、高速な遺伝子発見も実現した。

　第六章では、RNA構造の解析を行なう全く新しい手法を提案している。まず、RNA配列中において同じ立体構造を持ち得るような部分文字列を捜し出すことができるように接尾辞木という配列比較のためのデータ構造を一般化し、それに対する高速構築アルゴリズムを提案した。また本章では、RNA二次構造解析に応用できるものとして、木構造から様々なパタンを発見できるように接尾辞木を一般化したものに対しても、高速アルゴリズムを提案した。

　第七章は、六章までに述べられた問題及び手法を総括し、さらに、今後取り組むべき課題についての展望を示している。

　なお、本論文の第三章は今井浩氏と、第四章はChristian Schoenbach氏と小長谷明彦氏と鹿島久嗣氏と、第五章はIsidore Rigoutsos氏との共同研究であるが、論文提出者が主体となって分析及び検証を行なったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(理学)の学位を授与できると認める。