1994年AdlemanはDNA分子を用いてハミルトン経路問題を解き、分子を使ったコンピューティングの可能性を初めて示した。ある有向グラフについて、このグラフの各頂点をすべて通る道筋のことをハミルトン経路(Hamiltonian Path)と呼ぶ。この図1のように簡単なものでは容易にハミルトン経路(0から6まで頂点の数字通りの順)が発見できる。しかし、経路の効率の良い求め方が知られておらず、経路の探索はheuristicな方法によるかすべての可能な経路を手当りしだい調べるしかない。また、経路は頂点の数の階乗に比例して存在するので数千頂点のグラフでハミルトン経路を求めるには現在の最新のコンピュータでも7日間を要する。このハミルトン経路問題は「NP完全問題」(Nondeterministic Polynomial)として情報科学で知られている。NP完全問題としては並列計算のスケジューリングなどがありこの問題を解くことには高い意義がある。

図1 Adlemanの用いた有向グラフ

　Adlemanの実験で用いられたDNA分子は各頂点に対応した配列を持つ20merの長さのvertex oligomerと、各頂点を結ぶ矢印を表す20merのedge oligomerである。edge oligomerはそれが表す矢印の結ぶ都市に相補的な配列を持ち、橋渡しをする形でvertex oligomerとハイブリッドを形成する。(図2)これらすべてのvertex,edge oligomerをサンプルチューブ内でligationし、すべての頂点を含むちょうど7頂点分の長さを持つDNAを選択する。これらの手順により確かに当初予想されたハミルトン経路が得られた。

図2 vertexとedgeのハイブリッド

　この実験では7頂点のグラフを7日かかって解いている。しかし、経路を1頂点ずつ生成したとして1回の伸長が30分程度で済むならば、解く問題が大きい場合にシリコンベースのコンピュータの速度を上回ることができる。DNA分子の反応を計算に用いたときの特長は、(1)分子の反応が超並列性を持つ。(2)分子の反応によっては直接的で時間がかからない演算がある。例えばDNAで特定配列をハイブリッド形成で探索することである。(3)データ分子として設計、合成が容易である。(4)データ操作として増幅、切断、選択、結合、反転、消去、読み取り法などが確立されている点にある。このような特長をもつ分子計算機をハミルトン経路問題などの組み合わせ問題を解くのに用いると非常に有効であることが予想できる。

　本研究ではシリコンベースのコンピュータを上回る速度を目標に新しい実験方法でAdlemanのハミルトン経路問題をDNAを用いて解いた。実験方法の特長は、(1)Adlemanの方法より高速である。(2)自動化しやすい反応である。(3)固相上に頂点DNAをligationで1つずつ伸長していくので大きなグラフも解くことが出来る。(4)1つの経路上に同じ頂点が現われた場合(duplication)それを除くことができる。(5)伸長中の経路DNAを増幅でき、実験中に中間解を失うことがない。などである。

　実験に用いるDNAを図3に示す。RSとはRoot Sequence、TSとはTerminal Sequenceの略であり、それぞれEcoRI,BamHIの制限酵素認識配列を持っている。1は最初の頂点のDNAで、5’端のbiotinでstreptavidin磁気ビーズに固定する。2は各頂点を表すoligomerで、3は頂点とハイブリッドを形成するedge oligomerである。4は2度目の頂点が現われた経路とハイブリッドを形成するoligomerである。

図3 oligo DNA

　実験は図4の各ステップにより行う。(1)各vertex,edgeを65℃でハイブリダイズさせTaq ligaseにより完全に相補的なハイブリッドだけをligationする。(2)ligationされなかったoligomerの3’端にddTTPをTdTによりtailingし、このあとのligationが起こらないようにキャップする。(3)経路上にvertexの繰り返しを持つものの除去は、図3の4のoligomerをバルジを形成させて図5のようにハイブリダイズさせ、これをprimerとしてTaq polymeraseでRSまで相補鎖を合成させる。そして、RSを認識するEco RIで経路DNAを根元から切断することで繰り返しをもつ経路を除去する。以上のサイクルを繰り返すことでハミルトン経路を得ることができる。

図4実験の流れ

図5 duplicate vertexをもつ経路の除去

　この経路の伸長がグラフ通り特異的に行われていることを検証した。図6ではビーズ上のRS-V_startに対して接続すべきedge(0→1)とvertex(V₁-TS)とを、接続されない(2→1、1→2)と(V₂-TS)と混ぜてligationし、PCRでV₁、V₂に相補的なprimerでそれぞれPCRしてキャピラリー電気泳動装置で産物を比較したものである。この図から確かに高温で反応を行うことで特異的にligationが行われていることが確認できる。また、すべてのedge oligomerとvertex oligomerを含む場合にも実験を行い、65℃で反応を行うと特異的にligationが行われることを確認した。

図6 特異性の高いligation

　さらに、末端のTS配列を制限酵素で切断し、次の頂点が伸長できることをRS-V_start-V₁-TSをRS-V_start-V₁-V₂-TSに伸長することで確認した(図7)。

図7頂点の伸長

　本論文は、固相上のDNA分子反応を用いたハミルトン経路問題の解法について述べている。

　ハミルトン経路は、有向グラフのすべての頂点を一度だけ通過して始頂点から終頂点に至る道筋である。多項式時間で決定論的に経路を求めるアルゴリズムは未だ見つかっておらず、「NP完全」という、ノイマン型の通常の電子コンピュータでは解くことが非常に難しい問題のクラスに属している。基本的には、すべての可能な経路を網羅的に調べるしかなく、最悪の場合、頂点数の頂点乗に比例する時間が必要とされる。NP完全問題には、巡回セールスマン問題や並列計算機のスケジューリングなど、実用上重要な問題が数多くある。NP完全問題は互いに多項式時間で他の問題に変換できるため、このクラスのいずれかひとつの問題でも、それを多項式時間で解く方法を見つけることは画期的な意義をもつ。

　論文提出者は、DNA分子を利用して、代表的NP完全問題であるハミルトン経路問題を頂点数に比例する計算時間で解く方法を考案している。NP完全問題を多項式時間で解くことが可能になったのは、アボガドロ数のDNA分子が超並列に計算を進めるからである。論文で述べられている方法の概要は次のとおりである。有向グラフの頂点と辺を表現するDNAオリゴヌクレオチドを合成する。始頂点に対応するDNAオリゴヌクレオチドを、5’末端に導入したビオチンを介してストレプトアビジン磁気ビーズに末端固定する。4つの命令(EXT、CAP、RMVDV、DEBLK命令)からなるサイクルを(頂点数-1)回繰り返すことにより、磁気ビーズ上にハミルトン経路を合成する。PRNT命令により得られた経路中の頂点の並びを出力する。

　サイクルを構成する4つの命令は以下のような反応で実現されている。EXT命令は、既に合成されている経路の末端に隣接する頂点を付加し、経路の長さを1頂点分だけ伸長させる命令である。すべての頂点と辺を65℃でハイブリダイズさせ、Taq ligaseにより隣接頂点を表すDNAオリゴヌクレオチドを付加する。CAP命令は、EXT命令の効率が100%でないときに計算の誤りを防止するための命令である。ターミナルデオキシヌクレオチジルトランスフェラーゼで、未反応末端にddTTPを付加する。RMVDV命令は、付加された隣接頂点と同じ頂点をすでにもつ経路を除去する命令である。同一頂点をタンデムに並べたオリゴヌクレオチドをハイブリダイズさせると、頂点の繰り返しがあるときのみバルジループが形成され、Taq polymeraseで経路の根元まで相補鎖が合成される。根元まで二重らせん化された経路は、Eco RIにより根元から切断・除去される。DEBLK命令は、次のサイクルでEXT命令を実行するために、経路の伸長末端に付加されたddTTPのキャップを除去する命令である。除去にはBamHIによる末端切断が用いられる。RMVDV命令と同時に実行することが可能である。

　論文では、頂点および辺を表現するDNAオリゴヌクレオチドの塩基配列を設計する方法、各命令を実現するDNA分子反応の手順、命令の効率と正確度を計測する方法、反応条件を最適化した命令の効率と正確度の実測結果について詳しく述べられている。各命令を実現する反応を最適化した結果、RMVDV命令を除く命令の効率、正確度はDNA計算を進める上で問題がないことが示されている。RMVDV命令については、正確ではあるが正しい解も除去してしまうため、効率の点で改善の余地が残されていることが述べられている。しかし、サイクルをまわした実験結果から、総合的にはハミルトン経路を求めるためのDNA計算を正確に実行することが可能な効率が得られた、と結論されている。

　DNA分子反応を用いたハミルトン経路問題の解法は、1994年にエーデルマンが行った先駆的実験以降、確実な実験に裏付けられた報告はない。エーデルマンの実験はPCR、ゲル電気泳動、アフィニティ分離など、分子生物学で用いられている実験手法をそのままの形で利用したもので、7頂点の有向グラフのハミルトン経路を求めるのに約1週間を費やしている。また、いろいろな長さの経路が一度に生成されるため、頂点数が増えると急激に分子数が不足する問題点がある。そのため、頂点数の多い大きなグラフの解を求めることは難しい。それに対して、本論文で述べられている解法は、(1)エーデルマンの方法に比べはるかに高速で、同じ7頂点の問題を4時間程度で解くことが出来る。(2)ハミルトン経路を頂点単位で固相合成するため、必要な分子数が少なく、大きなグラフの解を求めることが出来る。(3)部分ハミルトン経路を表す仮想頂点単位でハミルトン経路を合成することが可能なので、大きなグラフの問題をより高速に解くことが出来る。(4)自動化しやすい反応のみで構成されているので、自動DNA計算機をつくることが可能である、など画期的な特徴を備えたものである。計算で使用する個々の命令を実現する反応の効率、正確度なども詳細に測定されており、しっかりとした実験に根ざしたDNA計算による解法を与えたはじめての研究といえる。よって本論文は博士(学術)の学位請求論文として合格と認められる。

　なお、本論文の研究は、有田正則氏、陶山明氏との共同研究であるが、論文提出者が主体となって実験及び解析を行ったもので、論文提出者の寄与が十分であると判断する。