生物配列からのパターン発見手法に関して研究をする．近年様々なゲノムプロジェクト等により，DNA，RNA，タンパク質などの生物配列データが大量に蓄積されて来ている．しかし，何種類もの生物種の完全ゲノムが決定されて来てはいるものの，未だにこれらの配列にどのような情報がどのように埋め込まれているかに関してわかっていない事は多い．配列に潜む情報を解明する手掛りを得るために，共通の性質や機能を持つ配列集合から，効率的に，意味のありそうなパターンを発見する手法は，莫大な量の文字列データを生産している分子生物学の分野においては非常に応用性が高く，必要とされる技術である．

　本研究ではまず，アミノ酸配列のN末端側に存在する3種の局在化シグナルに関する特徴抽出を行なう．徹底したパラメータ空間の探索の結果，ニューラルネット法によって得られる最高性能に迫る予測性能を、比較的簡単なルールの組であげることに成功する．その際に従来の配列集合に共通するパターンを探索する技術は有効であったが，それらに加え，アミノ酸指標データベース (AAindex) に含まれる，アミノ酸の様々な物理化学的・生化学的性質を数値として表わした情報を用いた事が成功に繋がった．

　近年においてはマイクロアレイを始めとする観測技術の発達により，他にも配列情報と深く関係した様々な定量的なデータが大量に生産されつつあり，このような新しい情報をどのように用いて知識を抽出すれば良いのかが重要な問題となって来ている．そこで，本研究では従来文字列情報単独で行っていたパターン発見手法に数値・カテゴリ属性を加え，より有効に確かなパターンを抽出するための新しい手法の開発に取り組む．文字列データと対応付けられた数値データが存在する時に，パターンが文字列中に出現する/しないという事象と数値データとの相関が高くなるようなパターンを探す，相関パターン発見問題を定式化する．文字列属性とそれに深く関係した数値・カテゴリー属性の両方の情報をアルゴリズムの中で同時に扱う事で，それぞれを単独に用いるだけでは見逃してしまう関係性を発見できる事が期待される．

　本研究では特に，適当な条件を満たす評価関数の基で，最適なパターンを発見するアルゴリズムについて研究し，幾つかのパターンクラスに関して相関パターン発見問題を効率的に解くためのアルゴリズムを与える．まず，部分文字列パターンに対して接尾辞木 (suffix tree) を用いた線形時間アルゴリズムを示し，更に接尾辞配列 (suffix array) を用いた効率的な実装を与える．次に，複数の部分文字列パターンを論理的に組合せたパターンに関するアルゴリズムを示す．また，より複雑なパターンクラスを考えた場合，この問題は一般的には NP-hard であることが示されるが，多くのパターンクラスに関して有効な分枝限定法を用いたアルゴリズムを与える．

　開発したアルゴリズは実際の生物配列データに対してを適用し，手法の有効性を確かめる．具体的には転写因子結合部位に関するパターン発見，mRNA の寿命エレメントに関するパターン発見，長大イントロン配列に関するパターン発見，を行なう．いずれの例においても，開発したアルゴリズムは素朴なアルゴリズムに比べて速度の面で効率的である事が示された．また，発見されたパターンに関しても生物学的に妥当な解釈ができるものであった．

　本論文は，生物配列からのパターン発見手法に関して研究をしたものである．配列に潜む生命情報を解明する手掛りを得るために，共通の性質や機能を持つ配列集合から効率的に意味のあるパターンを発見する手法は，莫大な量の文字列データを生産している分子生物学の分野においては非常に応用性が高く，必要とされる技術である．

　まず，アミノ酸配列のN末端側に存在する3種の局在化シグナルの特徴抽出の問題に取り組み，パターン等の配列に関するルールを生物学的な知見に基いて設計し，徹底したパラメータ空間の探索を行なった．結果として，比較的簡素なルールであるにもかかわらず，ニューラルネット法によって得られる最高性能に迫る予測性能を得ることに成功した．得られたルールを基に，局在化シグナル予測システム iPSORT を構築し，サービスとして公開をしている．

　局在化シグナルの問題に取り組んだ際に，従来の配列集合に共通するパターン発見の技術は有効ではあったが，それらに加え，アミノ酸の様々な物理化学的・生化学的性質を数値として表わした情報 (アミノ酸指標) を解析に用いたことが成功に寄与した．近年においてはマイクロアレイを始めとする観測技術の発達により，配列情報と深く関係した様々な定量データが大量に生産されつつある．そのような背景から，従来は文字列情報単独で行っていたパターン発見の手法に，数値・カテゴリ属性を加えることで，より有効に確かなパターンを抽出することのできる新しいパターン発見の手法について研究を進めた．そこで，入力として文字列集合が与えられ，各文字列に対応付けられた数値属性が存在する時に，パターンが文字列中に出現する・しないという事象と数値データとの相関が高くなるようなパターンを探す，相関パターン発見問題を定義した．このように文字列属性と数値属性の両方の情報をアルゴリズムの中で同時に扱うことで，それぞれを単独に用いるだけでは見逃してしまう関係性を発見できることが期待できる．

　本論文では，数種類のパターンクラスに関して，相関パターン発見問題を最適にかつ効率良く解くためのアルゴリズムを示した．まず，部分文字列パターンに関しては接尾辞木 (suffix tree) を用いた線形時間アルゴリズムを示し，更に接尾辞配列 (suffix array) を用いた効率の良い実装を与えた．次に，二つの部分文字列パターンを論理演算で組合せたパターンに関して，最適な組合せを O(N2) で求めることのできるアルゴリズムを示した．更にそのアルゴリズムを一般に k 個のパターンを組合せた場合に一般化し，最適解が O(Nk) 時間で求められることを示した．より複雑なパターンクラスに関しては，この問題は多くの場合に NP-困難であることが示されるが，様々なパターンクラスに関して有効な分枝限定法を用いたアルゴリズムを与えた．

　最後に，それぞれのアルゴリズムを実際の生物配列データに対して適用した．具体的には，1) 遺伝子の発現量と相関するパターンを遺伝子のコード領域の上流配列から探す，転写因子結合部位に関するパターン発見，2) mRNA の分解速度と相関するパターンを 3' UTR 配列から探す，mRNA の寿命エレメントに関するパターン発見，3) イントロンの長さと相関するパターンをイントロンの acceptor site 配列から探す，長大イントロンの特徴に関するパターン発見を行なった．いずれの例においても，考案したアルゴリズムは素朴なアルゴリズムと比べて速度の面で効率が良く，素朴なアルゴリズムでは現実的な時間で計算が困難な場合でも問題を解くことができた．発見されたパターンに関しても生物学的に妥当な解釈ができるものであり，問題設定及びアルゴリズムの有効性・有用性を確認する事ができた．

　このように，本論文は情報理工学のコンピュータ科学分野において、特にバイオインフォマティクスにおける顕著な研究成果をあげたものである．なお，本論文の研究内容は共同研究者との研究遂行により得られたものであるが，申請者が主体となって行った研究による成果であると認めた．

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる．