ヒトゲノム計画が1980年代に始まって以来、現在に至るまでゲノム解析が活発に行われている。多くの生物実験が、配列決定、遺伝子発現パターンの解析などを目的に数多く行われている。そして、膨大な生物実験から処理しなければならない膨大なデータが生まれ、情報科学の研究者の計算生物学という分野の研究も数多くなされている。本研究では生物学的に大変重要なDNA配列決定、遺伝子発現パターンの解析といった目的の実験デザインとその周辺の問題を情報科学的な問題と捕らえ直し、効率的で実用的なデザインとその情報科学的性質を明らかにすることを行う。

　はじめに、配列決定アルゴリズムを扱う。DNA配列を決定することはゲノムサイエンスにおいて大変重要な問題である。配列を決定する方法は様々な方法が考えられている。ここではシーケンシングバイハイブリダイゼーション(SBH)と呼ばれるDNAチップによって得られる部分文字列の有無のデータによる配列決定の方法について扱う。このSBHは理論的にはさまざまな研究がなされているが、実用上大切なエラーに対する対処があまり考えられていない。本論文では、DNAチップにおけるハイブリダイゼーションに誤りがある場合に対しても効率的に動くようなアルゴリズムを提案する。そして、エラーを入れたランダムデータに対して適用した。それにより、ハイブリダイゼーションデータが欠損している場合の影響が過剰にハイブリダイゼーションしているときより大きいものとなっていることを示した。また少量のエラーに対するこの手法の有用性を示した。

　次に、PCR実験におけるプライマー選択を行う。プライマー選択はPCR実験の効率を大きく左右するものである。今までに作られてきたプライマー選択に対するプログラムは1つのDNA配列に対して1組のプライマーを選択するものであった。本論文では、プライマーが複数の箇所につくことを許すことにより全てのDNA配列を増幅するような少ないプライマーの集合を選択することを考える。このプライマー選択問題を定式化して、その問題の計算量的性質を解析する。それにより、増幅の長さを異なるようにするのが計算量的に難しいということを示した。そして、単純な定式化に対する貧欲アルゴリズムに禁止条件を作って、生物学的制約を満たすようにした。このアルゴリズムを酵母などの配列が分かっているDNA配列に対して適用して、よいプライマーセットを得、複数実験に対するプライマーセットも得ている。

　SBHの解析というのはランダムな配列に対してなされている。しかし、実際にはDNA配列に適用するものであるし、また、DNA配列はランダムな配列でないのは明らかである。そこでランダム配列とDNA配列との違いをSBHのアルゴリズムを適用することによって解析する。また、SBHによって解が一意に定まらない場合について理論的な考察を行う。

ヒトゲノム計画が1980年代に始まって以来、現在に至るまでゲノム解析が活発に行われている。多くの生物実験が、配列決定、遺伝子発現パターンの解析などを目的に数多く行われ、情報科学の研究者の計算生物学という分野の研究も数多くなされている。本論文では生物実験に対するCADをおこなっている。生物実験に対するCADとは計算機による生物実験のデザインのみならず、生物実験のシミュレーションや生物実験の評価などを含んだことを意味している。

第1章では、計算機による生物実験の構成のみならず生物実験の計算機シミュレーションを行い、生物実験の評価をすることの意義を議論している。

第2章では、配列決定アルゴリズムを扱っている。DNA配列を決定することはゲノムサイエンスにおいて大変重要な問題である。ここではシーケンシングバイハイブリダイゼーション(SBH)と呼ばれるDNAチップによって得られる部分文字列の有無のデータによる配列決定の方法について扱っている。DNAチップにおいては多くのハイブリダイゼーションを行うためにエラーが多くおこる。よって、ハイブリダイゼーションエラーに対する対処を考えなければ現実的なアルゴリズムとはならない。そこで本論文では、DNAチップにおけるハイブリダイゼーションに誤りがある場合に対しても効率的に動くようなアルゴリズムを提案している。計算機実験により、ハイブリダイゼーションデータが欠損している場合の影響が大きいこと、また少量のエラーに対する有用性が示されている。

次に、SBHのアルゴリズムをi.i.d.情報源から得られる文字列とDNA配列とに適用し、DNA配列の特徴を調べている。i.i.d.情報源から得られる文字列はそのGC含量が偏っているほど特定率が低くなっていることが示されている。DNA配列も同様の傾向を示し、GC含量が偏っているほど特定率が低くなっており、しかもDNA配列はi.i.d.情報源から得られる文字列よりは特定率が低くなることが指摘されている。このようにDNA配列はSBHによって特定しにくい性質を持った配列ということが分かり、DNA配列に対するSBHの性能はi.i.d.情報源から得られる文字列に対する性能よりも悪いということが示されている。

第3章では、PCR実験における効果的なプライマー選択について考察している。プライマー選択はPCR実験の効率を大きく左右するものである。今までに作られてきたプライマー選択に対するプログラムは1つのDNA配列に対して1組のプライマーを選択するものであったのに対して、本論文では、プライマーが複数の箇所につくことを許すことにより全てのDNA配列を増幅するような少ないプライマーの集合を選択することを試みている。実用上は大規模なデータに対して適用しなくていけないため、複数回PCRを行わなくてはいけない。複数解のPCRのデザインも行い、計算機実験によりその解の良さを示している。

次に、プライマー選択のアルゴリズムをi.i.d.情報源から得られる文字列とDNA配列とに適用する場合を考察している。このことにより、DNA配列はi.i.d.情報源から得られる文字列より同じ文字列が多く都合の悪い配列ということが示されている。最後に実験結果の理論的裏付けを行い、SBHにおける特定率はi.i.d.情報源から得られる文字列においてはエントロピーとの相関があることを示されている。また、GC含量よりエントロピーが特定率とよく相関している場合があることを明らかにしている。i.i.d.情報源から得られる文字列に対してハイブリダイゼーションデータが欠損している場合の影響が過剰にハイブリダイゼーションしているときよりも影響が大きいことが証明されている。また、部分文字列の分布の理論的解析を行い、ランダムなプライマーによるDNA配列に対するPCRを計算機上でシミュレーションしてその理論的解析のように短い増幅が多くだんだん少なくなっていく傾向があることが指摘されている。これはPCRの増幅に対する電気泳動にとって都合のよい分布である。

これらの理論的、実験的解析により、DNA配列はi.i.d.情報源から得られる文字列よりも偏りが大きい配列ということがわかり、SBH,プライマー選択を行う際にはランダム配列でシミュレーションするだけでは不十分であり、ランダム配列よりも結果は悪くなってしまうことを考慮しなくてはならないといえる。このような結果から、本論文が目指した生物実験のCADを構築する目標が精密な考察を通じて具現化されたといえる。

なお本論文は今井浩氏との共同研究であるが、論文提出者が主体となって提案・分析・評価を行ったもので、論文提出者の寄与が十分であると判断する。

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