現在，我々が利用しているコンピュータの能力には理論的かつ現実的な意味 において限界があることが明らかになっている．理論的には計算不可能性 の壁があり，現実的にはいわゆるＮＰとよばれる問題のクラスは実際的な 時間内では解けないと信じられている．これらの計算能力の限界を乗り越 えるべく近年提案された新しい計算パラダイムのひとつが``分子計算 (molecular computing)''である．1994年，Leonard Adleman（USC, 米国）の 分子生物学的な実験手法によるハミルトニアンパス問題の解法がScience 誌に発表されて以来，欧米をはじめ我が国においても非ノイマン型計算メカニズ ムを強く志向する機運と相まって分子計算への期待は徐々に高まり，ごく 最近では自然の行っている現象・原理に基づくいわゆる``ナチュラルコン ピュテーション''とよばれる新計算パラダイムの探究へと発展する広がりを みせている．
我々はこれまで，形式言語理論に基づく計算可能性の理論的な研究に従事し， チューリング計算可能性の立場からオートマトン・形式文法を基本とする 種々の計算モデルの計算能力とモデリング（記述）能力を解析してきた． またそれらの理論的な研究成果の応用として，例えば確率文脈自由文法を 用いてtRNAをモデル化することにより配列予測が可能であること，ある種 の木文法が複雑な構造をもつRNAのモデリング文法として有効であること などを示した．そのような研究活動において，1987年に発表されたTom Head（SUNY, Binghamton，米国）によるスプライシング・システムと呼ばれ る形式言語生成システムに関する研究に注目し，その計算能力・表現能力 に関する研究を開始した．（これらはAdelmanの実験結果の発表以前のこと である．）このスプライシング・システムは，いわゆる``DNA配列の組み換え'' メカニズム，すなわち「制限酵素による共通の切断サイトをもつ２つの DNA二重鎖配列がそれぞれの前半部と後半部を互いに交叉させることに よって新たな２つのDNA二重鎖配列を生成させるメカニズム」を説明する ための数学モデルである．Headによるこのスプライシング・システムの 研究成果は発表当初それほど注目されることはなかったが，Adlemanによ る分子計算実験の発表を契機として一躍その理論的な重要性が認識されるに 至った．我々がTom Headと研究交流を重ねる中で，Tom Head自身も``分子 に計算させる''という考えに魅せられ，分子計算の理論と実装法の研究 へと傾いていった．
その後，この分子計算の理論的研究動向は北米から欧州へと広がりをみせ， 理論計算機科学の分野で活躍する第一線の研究者達に浸透していった． その中には，Rozenbergに率いられるオランダのライデン大学のグループ， Paun, Mitranaらを中心とするルーマニアグループ，Salomaaらを擁する 北欧グループ，イタリアのMauriをリーダとするミラノ大学グループ等がある．
この様な状況を背景として，我々の理論研究グループは学術振興会による 未来開拓プロジェクト『分子コンピュータの理論と構築』に参画する機会を 得るに至った．
本研究を開始した1996年度から現在に至るまで，我々が一貫して探究した 研究の目的は『形式言語理論・計算理論に基づき, 分子コンピュータのため の万能計算モデルの理論を構築する』ということであった．より具体的に言 うと，形式言語理論などのコンピュータサイエンスにおける計算理論を駆使 して，分子コンピュータのための万能計算モデルを構成し，計算機シュミレ ーションなどを通して，そのモデルの計算可能性・計算複雑性に関する理論 的な解析を行なうことであった．
今日における計算理論の研究成果として，いわゆるチューリングの意味で 万能計算可能な計算モデルは実に数多く知られており，従ってこの研究目的 に対する基本的な戦略には，様々な種類のアプローチが可能である． そこで，我々はまず分子計算の基本操作の一つとして重要な``組み換え （スプライシング）''に立ち戻り，Headのスプライシングモデルを研究 の出発点とした．
研究成果を大別すると，（１）拡張スプライシング 計算モデルの研究，（２）論理型分子計算モデルの研究， （３）新しい計算モデルの探究，に分類される．
AdlemanのDNA計算実験より前の1987年にTom Headによって提案された スプライシングシステム(SS)は分子計算のための最初の形式的計算モデル であるとみなすことができる．これは，その基本的計算機構として 二つのDNA配列の間のいわゆる``組み換え(cross-over)''操作のみを持つ 非常に単純なモデルであり，計算能力の側面からは(正則言語のみが生成可能 であるという)明らかな限界があった．
上記の弱点を補いその計算能力をTuring機械と同等にするために，現在まで に数多くの拡張モデルが提案され研究されているが，(例えば，生物化学的に 解釈すると，無限個の制限酵素が必要であったり，非常に複雑な制御のもと でのDNA配列操作が仮定されたりして)非現実的な制約条件が要求されていて， 現実に実装可能なモデルにはなっていない．横森らは，これらの欠点を補うべく， 環状DNA配列を用いた新たな計算モデルとして``環状スプライシングシステム (Circular Splicing System : CSS)''を提案し，その計算可能性を形式言語 理論的に解析した．このモデルは，(i) 有限個の制限酵素しか用いず，しか も従来の組み換え操作を少しだけ修正した環状スプライシング操作のみに よってTuring機械と同等な計算能力をもつ，(ii) プログラミング可能なCSS が構築可能である，などの点において，より現実的なモデルになっている．
従来のスプライシングモデルに対する構造的な一般化として，榊原らは ``木スプライシングモデル''を導入しその計算能力を研究した．
スプライシングシステムの基本演算である``組み換え(cross-over)''操作 は２つのDNA配列の間の，つまり線型な単純構造をもつ２つの分子に 関する演算であり，それゆえ（生成されるのは正則言語のみという） 計算能力における限界があった．この弱点を補いその計算能力を高める ために，RNA分子が自然に形成する二次構造を用いて木構造を実現する ことにより木構造上でのスプライシングを提案した．結果として，この 木スプライシングシステムの計算能力は文脈自由言語のクラスと同等で あることを示した．
前述したように，Head のスプライシング操作を基本計算とするDNA コン ピュータは高々有限オートマトンと等価な能力しか持たない．そこで，小林 らは，複数の試験管を用いる計算方法を提案し，スプライシング操作を基本 とするシステムの能力をチューリング計算能力と等価なものになることを示 した．これは，２つの試験管の生成物を混合してスプライシングする操作を 基本操作として定義し，この基本操作を並列実行するスプライシングシステム となる．試験管の本数を少なくすることは，実現可能性の観点から重要な 因子の一つであるが，本研究では試験管の本数が 13 本あればTuring 機械 と同等の計算能力を持つことが示された．
今日までに知られている数多くの計算モデルの中で論理型計算モデルと よばれるものがある．これは，一階述語論理という形式的体系の部分系 である命題論理（ブール式）または、ホーン節からなる証明系を用いる． 理論的な結果として，一階の ホーン節による計算能力がTuring機械と同等であることが知られている．
従来の DNA 計算モデルがTuring 機械を直接的に模倣するタイプのもの が多いのに対し，小林らは， ホーン節による 論理型計算を DNA 分子に行なわせることにより，DNA 計算機を実現する ことを提案し，その基礎的な実験を行なった．すなわち，まず二項演繹を DNA 分子により実現させるための実験手法を提案し，基礎的な確認実験 を行なった．この手法では，事実およびルール(if-then ルール)は，一 本鎖 DNA 分子として表現される．ルール条件部にある事実が試験管中に 存在するときは，それらの事実がルールに Hybridize し，ルールの結論 部に存在する事実を表す一本鎖 DNA 分子が制限酵素により切断され抽出 される．この実験手法の妥当性を確認するために，ルールと事実と非特 異的な Hybridization を行なわないための Annealing 条件の確認や， 制限酵素による切断の確認などの，基礎的な実験を行なった．この実験の 結果，制限酵素による切断時に，分子間あるいは一分子内における予想外 の Hybridizationに起因する問題があることが判明した．そこで，「規則 分子の固定」と「複数の制限酵素の利用」を行なうことにより，分子間 ・分子内の意図しない相互作用を避ける方法を提案し，その有効性を確認 するための基礎実験を進めた．
その後，一階述語論理の演繹演算を DNA 分子を用いて行なう手法の研究も 進めた．萩谷らが提案している鞭打ちPCRという一分子内反応を引数情報 のコピーに利用することにより，関数を含まない非常に制限された形のホ ーン節ではあるが，演繹を実現する手法を提案した．また，理論的には この計算モデルはTuring計算機と同等の計算能力を持つことが示された． しかしながら，実験による確認はまだ全く行っておらず，今後の実験技術 の確立が期待される．
DNA計算において利用される最も重要な特徴の一つは，DNA分子の微小性と 超並列性を用いた試験管内での超並列的な探索である．そこで榊原は， DNA計算の超並列的探索を用いて，計算論的学習における未解決問題である ブール式の学習問題を多項式時間で効率よく解く方法を示した．この手法に おいては，ブール式をDNA配列に符合化する方法，符号化されたブール式を 試験管内で評価する方法が示されている．
榊原らは，DNA計算を用いて開発されたDNAコード化法とブール式の学習を解 くアルゴリズムを組み合わせることにより，遺伝子の発現データを試験管の 中で効率良く解析する手法を提案した．これは，遺伝子の発現プロファイル の解析に対して，その論理演算などを試験管の中で行なうことを提案するも ので，DNAコンピュータを遺伝子解析に応用する新しい方法である．この方法 を用いることにより，遺伝子の発現データから病気を特定したり，遺伝子ネット ワークを構築することが，より高速により正確に行なうことが可能となる．
情報処理能機能を持つ反応系の設計のためには，組合せ論的に複雑かつ 多数の分子種が生成されるような反応系のシミュレーション技術の確立が 必須である．このような系のシミュレーションの最大の問題点は，分子 の種類が時間とともに指数関数的に増大する特徴を持つことである．小林 は，反応系をライゲーション反応に限り，指定された時間の特定分子の濃 度を予測する問題を計算量的に考察した．そして，ライゲーション反応に 限れば，与えられた分子の指定時間の濃度を効率良く計算できることを示 した．今後は，この結果を反応系を効率の良く設計する問題へ応用するこ とを考えている．
分子コンピューティングの計算モデルとして``万能計算性''と分子生物 実験技法による``実装の容易性''とは二つの重要な要素である．我々は これらの知見を基に，「新たな計算メカニズムの探究と計算モデルの開 発」を目的として以下の３つの計算パラダイムに基づく計算モデルを提 案しその計算能力を解析した．
横森らは，入力データをDNAなどに符号化し，計算の基本原理を``Equality Checking''という簡単な制御機構で行なう新たな計算モデルDNA-EC を提案し，その計算可能性を形式言語理論的に解析した．従来提案され 議論されているDNA計算のモデルのほとんどはチューリング機械あるいは 句構造文法を模倣する形式でその万能計算可能性が論じられている．そこで， チューリング機械を著しく簡単化した``等価性機械(Equality Machine)''と よばれる計算モデルが万能計算能力を保持するという事実に注目し，この 抽象計算機械を基本にして分子計算モデルの設計を試みた．このモデルは ふたつの記憶テープが等価であるという情報を用いながら状態を遷移する だけで万能な計算能力を実現できるという利点を有し，したがって分子 計算モデルとしては原理的に``二重ラセンの相補配列DNA''を計算の制御 情報として``状態遷移''を実現すればよいことが明らかになった．よって このふたつの基本操作を現在の分子生物学的な基本操作技術によってどの ように実現するかが今後の課題となる．
自然が行なう情報処理の原理をよく観察すると，そこには幾つかの普遍的 かつ基本的な原理が見えてくる．そのような自然界において見られる２ つの原理として「自律的会合」と「形態変化」に注目した．自律的会合 とは例えば２つの分子が互いに規則正しい意図した構造体を自律的に 形成することであり，形態変化とは構造体がある種の等価変換によって 意図した形態に変化することである．横森は，この２つを基本原理とする 分子計算モデルを提案し，この計算モデルによってNP完全とよばれる難 しい問題のクラスが線形の分子計算時間で解けることを示した．また， 上記の計算原理がどれほどの一般性をもっているかを探究し，YAC とよぶ計算モデルに到達した．YACモデルはアニーリングにより自律的会 合を実現し，融解と再アニーリングによって形態変化を行わせる計算モデ ルであり，万能計算能力をもつことが示された．この結果は Adleman- Lipton型の計算モデルの拡張とみなすことができ，その意味でも興味深い．
自然による計算のひとつとして生物の細胞内で起こっている生体反応 系の情報処理現象に着目するとき，新しい計算のパラダイムが想起される． 横森は G. Paunとの共同研究において，細胞膜のもつ制御機構を利用する ``細胞膜計算モデル（P-Systems）''を提案するとともに膜構造と計算能 力の関係を考察した．その結果，幾つかの膜計算モデルがTuring万能計算 能力をもつことを示した．さらに，細胞膜による制御とスプライシング操 作とを組み合わせたモデルを考案し，その計算モデルがやはり万能計算能 力をもつことを示した．
本研究プロジェクトにおいて，我々は DNA 配列の組み換え（スプライシング）， 核酸塩基対の相補性によるハイブリダイゼーション，自律的会合，分子構造 の形態変化等々の様々な生体分子反応を解析し，それらの知見をヒントとして 情報処理のための新たな基本的計算機構の開発と分子計算モデルの提案を行 ってきた．提案した多くの計算モデルは従来の計算機と同等の計算能力 （チューリング計算可能性）を有することが証明され，実際に分子生物学 的な基礎実験によりその実装可能性の一部が検証されたものもある． また，細胞内の生体分子反応をモデル化した抽象化学反応系にコンパートメント を導入することにより細胞計算モデルを構築しその計算能力を理論的に解析 してきた．一方，分子計算の分子生物学実験におけるハミルトン経路問題 や充足可能性問題に対する解法はハイブリダイゼーションという分子反応 やPCR増幅等の実験操作を含んでいるが，それらの実行過程の信頼性はまだ 低く反応特性の詳細な解析や基本操作の問題点については不明な点が少な くない．上述の新規な計算モデルの実装可能性を検証するためにも計算機 シミュレーションシステムを開発し，人工的な仮想分子などを用いること によりPCRなどDNAによる様々な生体分子反応や分子計算モデルの挙動を シミュレートすることが必要となっている．この意味において，分子反応 系のための確率的あるいは近似的計算モデルとその解析手法に関する研究 の必要性が強く示唆される．
DNA，RNAの構造分子やタンパク質のような高次構造を持つ生体高分子は 分子認識（分子会合），自己組織化，形態変化などの生体反応・現象に よって目的をもった分子系を形成し機能を発現する．したがって，今後 の重要な課題として，生体構造分子と生体化学反応系に関わる情報処理 能力を計算理論的，アルゴリズム論的な視点から``解析し設計する''こ とが考えられる．すなわち，生体分子の構造とその機能との関係を計算 能力（あるいは情報処理能力）という視点から解析することにより，基 本計算ユニットの集合（基本構造分子群）と基礎となる計算原理（生体 反応系）を明らかにして，それらの組み合わせを基本とする体系的な分 子計算の理論モデルを構築することである．さらに，ある問題を解く （ある機能を実現する）ために基本構造分子群に属する各分子計算ユニ ット上にその問題をどのように符号化し制御すればよいかという分子計 算におけるプログラミング技法は``分子プログラミング''における研究 として重要な課題となるであろう．
目次へ