図1: DNA計算による遺伝子発現プロファイリング
大きなサイズのNP完全問題やバイオテクノロジーへの応用など、実用性の高い 問題を解くことができるDNAコンピュータの開発を目指して研究を行ってきた。
まず、取り組んだ問題は大きなサイズのNP完全問題をDNA計算で解くことであ る。そのためには、Adlema-Liptonの計算パラダイムが抱える深刻なスケール 問題を解決しなくてはならない。陶山たちは、ダイナミックプログラミング法に基 づくアルゴリズムをDNA分子反応の操作で実装することにより、このスケール 問題を実用的なレベルで克服することに成功した。大きなサイズのNP完全問題 を解くためには、さらに計算反応の自動化と計算の誤りを効率よく除去する方 法を確立することが不可欠である。DNA計算のための基本命令を自動実行する ハードウェアを開発するとともに、計算の誤りを効率よく除去する方法を考案 し、大きなサイズのNP完全問題を解く目標に向けて大きく前進する成果をあげ ることができた。
また、DNA計算をNP完全問題よりさらに実用的な問題に応用することを行った。 生命体自身が分子コンピュータであることを考えると、その解明にDNAコンピュー タなどの分子コンピュータが利用できると考えることはごく自然であろう。陶山たち は、DNA計算によりDNA/RNA分子がもつ情報を解析する方法の原理を提案し、そ の原理にしたがったDNA計算により実際に遺伝子発現プロファイル解析が行え ることを実験により示した。この原理にしたがったDNA計算は、さらにいろい ろな生体分子の情報解析への応用が可能であり、DNAコンピュータのバイオテ クノロジーへ応用は大きな将来性をもっていると考えられる。
以下に、これらの成果について簡単に述べる。
分子コンピュータは溶液中での特異性の高い分子認識反応を利用した“ウェッ ト”なコンピュータである。極微量の溶液中にも莫大な数の分子が存在し、し かもそれらが関与する分子反応は並列に同時進行する。したがって、分子でデー タやプログラムを表現し、その分子反応で命令を実行すれば、現在の電子コン ピュータに比べて桁違いに大きなメモリ容量と高い並列処理能力を実現するこ とが可能である。1994年、Adlemanはこれらの特徴がＮＰ完全問題を解くため に有効であることに着目し、実際にDNA分子を用いて7頂点14辺からなるハミル トン経路問題を解く実験を行った[Adleman94Science]。この実験が今日のDNA コンピュータ研究の出発点である。
Adlemanの研究は翌年Liptonにより代表的なNP完全問題である3SATに適用され、 Adleman-Liptonの計算パラダイムが確立された[Lipton95Science]。この計算 パラダイムでは、最初にワンステップの計算処理により、すべての解の候補を 表現するDNA分子のプールが生成される。その後、分子反応による並列処理に より、プールの中から解の条件を満たすDNA分子が選択・抽出され、問題が解 かれる。しかし、NP完全問題の指数関数的時間計算量を単に分子の量に置き換 えただけであるため、当然のことながら、大きなサイズの問題を解くためには 莫大な量のDNA分子が必要になる。これがAdleman-Liptonの計算パラダイムに よるDNA計算が内包する深刻なスケール問題である。
陶山たちは、ダイナミックプログラミング法に基づいたアルゴリズムをDNAコンピュー タで実行することにより、このスケール問題を大幅に軽減することを行った [陶山00数理科学, Yoshida00DIMACS, Morimoto99DIMACS, Morimoto97BCEC]。 すなわち、Adleman-Liptonパラダイムのように最初にすべての解の候補を生成 するのではなく、部分問題の解の候補を生成し、その中から解を選択抽出する。 この操作を部分問題のサイズを逐次的に大きくしながら繰返し、最終的に本来 の問題の解を得るのである。このようにすれば、生成される解の候補の数を大 幅に減らすことができる。
この考えに基づき、陶山たちは幅優先探索により問題のサイズに比例する計算ステッ プ数で3SATを解くことができる、DNA分子の反応操作で実装が可能なアルゴリ ズムを考案した[陶山00数理科学, Yoshida00DIMACS]。このアルゴリズムを実 装したプログラムであるdna_3satでは、一連のDNA分子反応操作により実現さ れるget、append、amplify、merge、detectの5つの基本命令が使用されている。 これらの基本命令の中で、特にappend命令は重要である。これは、与えられた 末端条件を満たすDNA分子の端に指定した配列を付加する命令で、 Adleman-Liptonの計算パラダイムにはなく、ダイナミックプログラミング法に 基づいたアルゴリズムをDNA計算により実現するために新たに導入したもので ある。
計算に必要なDNA分子の量を見積もるために、変数と節の数の比が最も解くこ とが難しい条件を満たす n = [20, 31] 変数、m = [4.3, 4.7] × n 節 の3SAT問題をそれぞれ2,000例作成し、電子コンピュータでプログラムdna_3sat を実行して解いたところ、必要なDNA分子の数の最大値は 20.55n 程度であ ることがわかった[Yoshida00DIMACS]。n を100に外挿すると、 Adleman-Liptonの計算パラダイムでは100万トンも必要であるDNA分子がわずか mgで済むことになり、実現可能な量のDNA分子で3SATを解けることがわかった。
実際にdna_3satで3SATの問題を解くことができることを示すために、4変数10節 の3SAT問題を解く実験を行った[Yoshida00DIMACS]。まず、基本命令を実行す る正確さと効率を実験的に決定し、反応条件を調整してそれらをある程度最適 化することを行った。また、論理変数の値を表現するために正規直交化された DNA塩基配列を設計するアルゴリズムとプログラムを開発し、200を超える正規 直交化配列を得た。正規直交化した塩基配列は、相補塩基配列とは同一の安定 性をもつハイブリッドを、それ以外とは安定したハイブリッドを形成しない、 それ自身で安定した構造をとらない塩基配列である。DNAの分子反応操作で命 令を正確かつ効率よく実行するためには、命令の引数となるデータのDNA分子 は正規直交化配列のビット列であるDNA符号で表現されていることが必要であ る。設計した正規直交化配列を用いて手動でdna_3satの計算反応を実行する実 験を行ったところ、正しい解を得ることができた。
さらに大きなサイズの問題を解くためには手動による反応操作では限界がある。 ダイナミックプログラミング法に基づくアルゴリズムをDNA分子反応で実装す ることによりスケール問題は実用的なレベルで克服できたといえるが、問題の サイズに比例する計算ステップ数とはいえ、Adleman-Liptonの計算パラダイム に比べて計算ステップ数が多くなっている。計算の途中で一度でも反応操作を 誤ったり、命令を実行する正確さや効率が落ちたりすると、計算全体が失敗に 終わってしまう。したがって、命令の実行するための反応操作を自動化するこ とが不可欠であるといえる。
分子コンピュータに適した問題は、NP完全問題のような純粋に数学的問題だけ ではない。分子コンピュータの方が電子コンピュータよりも原理的に適してい る問題がある。たとえば、ゲノム情報解析のように入力データがDNA/RNA分子 あるいはタンパク質分子などで与えられるような問題、あるいは、機能性分子 や機能性ナノ構造体の設計・探索問題のように、入出力が分子であるというだ けでなく、評価関数を第一原理に基づいて計算することが電子コンピュータで は困難な問題などである。このような問題に対してDNAコンピュータが有効で あることを実証するために、DNA/RNA分子の情報解析をDNAコンピュータにより 行う方法の原理を構築するとともに、実際に遺伝子発現プロファイル解析のた めの計算処理の実験を行った[陶山00数理科学, Suyama00CCMB]。
DNAコンピュータのCPUは一連のDNA分子反応で構築されている。CPUが同じ反応 条件の下で正確かつ効率よく命令を実行するためには、命令の引数であるデー タが正規直交化した塩基配列のビット列であるDNA符号で表現されていること が必要である。したがって、DNA/RNA分子の情報をDNAコンピュータで解析する 場合、入力データであるそれらの情報をDNAコンピュータの内部コードである DNA符号に変換することを最初に行う必要がある。これはちょうど、CPUが論理 回路で構築されている電子コンピュータの内部ではデータが2進符号で表現さ れているため、入力装置から入力されたデータは内部コードである2進符号に 変換されてから計算処理にかけられることに対応する。
DNA符号に変換された入力データは、DNAコンピュータのCPUがサポートする一 連の命令で処理されたのち、DNA符合で表現されたDNA分子として出力される。 そのDNA分子のDNA符号をデコードすると計算処理の結果が得られる。DNA符号 をデコードして表示する方法には、graduated PCRやDNAシーケンシングがある。 しかし、最も効率的な方法は、DNA符号のビットを構成する正規直交化配列の 相補配列鎖を集積したDNAチップを用いる方法である。同じDNA符号の体系を使 用する限り、チップ上に集積されたDNAプローブは変わらない。したがって、 このチップはユニバーサルDNAチップといえる。
遺伝子の機能を解明するための重要な解析のひとつとして、転写産物分子が与 えられたときに発現されている遺伝子の種類とその量のプロファイルを決定す る遺伝子の発現プロファイル解析がある。前述した原理に基づいて、陶山たちは DNA計算により遺伝子の発現プロファイル解析を行うためのプログラムである dna_gepを開発した[陶山00数理科学, Suyama00CCMB]。このプログラムは、ダ イナミックプログラミング法により3SATを解くためのDNAコンピュータプログ ラムであるdna_3satと同じ基本命令を用いて書かれている。転写産物である mRNA分子から調製したcDNAを入力データとしてプログラムdna_gepを実行し、 出力されたDNA分子のDNA符号をユニバーサルDNAチップでデコードして表示す ると、遺伝子の発現プロファイルが得られる。DNA符号の1ビットを25塩基とし たとき、300近くの正規直交化配列が得られているので、2桁のDNA符号を用い ると、プログラムdna_gep により2万を超える遺伝子の発現プロファイルを同 時に解析することが可能である。
実際、このプログラムにより遺伝子の発現プロファイル解析を行うことができ るかどうかを調べるために、プログラムdna_gepを実行する実験を行った。入 力データとして、移植断片対宿主病に関連する8個の遺伝子の転写産物を同定 するための標的配列をもつ30塩基長のDNAオリゴヌクレオチドを使用した実験 の結果、計算反応が特異的かつ定量的に進むことが確認された（図1）。 計算に要した時間は、手動による一連の反応操作とDNAチッ プスキャナーによる検出を含めて約3時間であった。
遺伝子の発現プロファイル解析を行う方法として、DNAチップで直接に転写産 物分子を検出する方法が、医・生物学者の間で注目されている。それと比べて DNA計算による方法はいくつかの優れた点を有している。まず、ハイブリダイ ゼーション反応が最適化されたユニバーサルDNAチップを使用するため、解析 対象ごとにDNAチップを作製して性能を確認する手間がかからないことが挙げ られる。また、増幅特性が異なる転写産物を直接増幅するのではなく、増幅特 性が一様なDNA符号に変換してから増幅するため、定量性の高い解析を行うこ とが可能である。さらに、解析に使用するサンプルを直接ラベルする必要もな い。これらの利点は、遺伝子の発現プロファイル解析という非数学的問題にお いてもDNA計算が有効であることを端的に示しているといえる。
プログラムdna_gepでは、入力データを内部コードに変換してから増幅し、そ の結果をデコードして表示するという非常に単純な処理しか行っていない。し かし、ひとたび入力データを内部コードであるDNA符号に変換すると、より複 雑な計算処理を行うことができる。たとえば、遺伝子が非発現であることを示 す情報を生成して遺伝子の発現状態の論理的関係を判定することや、遺伝子の 発現ネットワークの探索問題などへ適用することができる[Sakakibara00GIW]。 また、DNA計算によるデータベース演算[Arita97ICEC]を利用した解析を行うこ とも可能である。
陶山たちは、ダイナミックプログラミング法に基づくアルゴリズムをDNA計算で実 装することにより、Adleman-Liptonの計算パラダイムによるNP完全問題の解法 が抱えるスケール問題を克服できること、DNA計算が遺伝子の発現プロファイ ル解析という生体分子情報解析にも適用できることを、計算処理の反応操作を 手動で行う実験により明らかにした。これらの成果に基づいて、より大きなNP 完全問題を解く計算や複雑な生体分子情報解析を行うためには、計算処理の反 応操作を自動化し、必要とされる多数の反応操作を正確かつ効率よく、しかも 高い再現性で実行できるようにすることが不可欠である。
そこで、磁気ビーズを利用した核酸抽出ユニット(プレシジョン・システム・ サイエンス社製)を基にして、DNA分子の計算反応操作を自動化するハードウェ アを開発した[中島00MPS, 陶山00数理科学]。（巻頭の図~1）プログラム dna_3satやdna_gepで使用されている基本命令は磁気ビーズを使用した操作に より実装できるため、それらの命令の実行を自動化することは容易である。酵 素溶液の注入を自動化することも技術的には可能であるが、予算の都合上、酵 素溶液の添加は手動で行うことにした。開発したDNAコンピュータのハードウェ アでgetおよびappend命令の実行精度と効率を計測したところ、手動で実行し た場合の最適値かそれ以上の値を再現性よく得ることができることがわかった [中島00MPS]。
DNAコンピュータのハードウェアを使用して、手動の反応操作で解いた4変数10 節の3SATの問題を解いたところ、正確に解くことができた[中島00MPS]。さら に、より大きな6変数10節の問題を解いたところ、正しい解も得られたが誤っ た解が20％程度も混入することがわかった。 誤った解が混入する原因を調べたところ、命令を実行する精度のバラツキでは なく、誤りの伝播に原因があることがわかった。充足可能性を判定する命題論 理式の形によっては、一度発生した誤りが正しい解よりも小さな減衰率で計算 処理の最後まで伝播し、誤った解を表現したDNA分子の割合が大きくなること が判明した。このような誤りを除去するために、dna_3satで求めた解のDNA分 子に対して節の数だけのget命令を直列に実行する計算処理を行った。その結 果、 完全に誤りを除去できること がわかった。得られたDNA分子をクローニングして塩基配列を決定したところ、 シーケンシングした10クローンのすべてが正しい解であった。プログラム dna_3satを実行したのち、さらに節の数だけget命令を実行することは、計算 反応を手動の操作で行う場合は大変である。しかし、計算反応を自動実行する DNAコンピュータのハードウェアを用いれば、この計算処理は容易に実行する ことができる。
正確かつ効率のよいget命令を直列に実行することにより誤りを除去する方法 は、任意の3SAT問題の計算で使用することができる。3SATを解くプログラム dna_3satの中で、変数についてのループを適当な回数だけ実行するごとにこの 誤りを除去する計算処理を行えば、大きなサイズの問題を正確に解くことが可 能である。電子コンピュータでは厳密に解くことが困難なサイズの3SAT問題が、 DNAコンピュータで実際に解ける可能性が出てきたことになる。
DNA計算反応の自動化は汎用DNAコンピュータのハードウェアを開発することに もつながる。3SATをDNA計算で解くためのプログラムdna_3satと遺伝子の発現 プロファイル解析を行うためのプログラムdna_gepは、同じDNA計算の基本コマ ンドを使用している。すなわち、同一ハードウェア上で異なるプログラムを実 行することにより、異なる問題を解くことができるのである。開発したDNAコ ンピュータのCPUが現在サポートしている基本命令のセットでは、万能チュー リングマシンとしての計算能力はない。したがって、解くことができる問題に は限りがある。しかし、開発したＤＮＡコンピュータのハードウェアは様々な 溶液反応操作を実装できるので、今後さらに実行できる基本命令を拡張するこ とにより、その計算能力を高めることが可能であるといえる。
陶山たちは、いわゆるtoy problemではなく、実用性の高い問題を解くことができ るDNAコンピュータの開発を目標にして本研究を行ってきた。大きなサイズの NP完全問題を解く際に障害となるスケール問題や計算の誤りの問題を実用的な レベルで解決したこと、遺伝子の発現プロファイル解析などの生体分子情報解 析にＤＮＡ計算が有効であることを示すことができたことにより、本研究の目 標はほほ達成できたと考えられる。
大きいサイズの3ＳＡＴを解く実験は現在も進行中である。10変数40節、20変 数80節と次第に問題のサイズを大きくし、将来は50変数200節から100変数400 節の問題に挑戦したいと考えている。20変数を超える問題を解くには、酵素の 添加も自動化した、すべての反応操作が自動実行できるDNAコンピュータのハー ドウェアが必要になると考えられるが、その開発は十分に可能である。
DNA計算が遺伝子の発現プロファイル解析という生体分子情報の解析に有効に 適用できたことは、DNA計算が単にNP完全問題のような純粋に数学的問題を解 くための計算パラダイムではなく、バイオテクノロジーへの様々な応用が可能 であることを意味している。ゲノムプロジェクトが進むにつれて、いわゆるトッ プ・ダウン的アプローチによる研究の重要性が増しつつあるが、ゲノム全体の 情報を正確に捉えることが必要とされるこのアプローチにとって、DNA計算は 強力な手段を提供するものとなろう。さらに、単に基礎科学を推進するための 技術としてだけではなく、ゲノム情報を利用した産業にとっても有効な手段を 約束するものであるといえる。
本研究で開発したDNAコンピュータのハードウェアは、ある問題を解く際に分 子コンピュータと電子コンピュータのそれぞれが得意とする計算処理を分担し て実行するハイブリッド計算機とみなすことができる。分子コンピュータと電 子コンピュータは得意とする計算処理が異なっている。分子コンピュータは、 並列処理は得意であるが、単一の命令を単一のデータに対して高速に実行する ことは必ずしも得意ではない。それに対して、電子コンピュータは、大規模な 並列処理は不得手であるが、単一の命令を単一のデータに対して実行する速度 は分子コンピュータよりもはるかに速い。一般にある問題を解く場合、すべて の計算ステップで並列処理が必要かというと、必ずしもそうではない。並列処 理が必要なところもあれば、直列処理しかできないところもある。また、分子 を入出力データとする計算であっても、すべての計算ステップを分子反応で実 現することが適当かというと、必ずしもそうではない。電子コンピュータで行っ た方がはるかに容易に処理できる計算ステップも多数あるのが普通である。し たがって、最も実用的なコンピュータの形は、分子コンピュータと電子コン ピュータを一体化したハイブリッド計算機であると考えられる。本研究で開発 したDNAコンピュータの基本構成とハードウェアをベースにし、基本命令の拡 張とコンパイラーの開発を行うことにより、実用性の高い汎用ハイブリッド計 算機を実現できると考えられる。
目次へ