図 1 オイラーグラフと有向ハミルトングラフ
コンピュータといえば私たちは、通常、フォンノイマン型のＰＣで液晶画面が ついて、CPUがあり、メモリーがあり、ハードディスクがあり、キーボードがありと、 現在では、当たり前のように使用している計算機を想像する。しかし、『1936年に 英国の数学者チューリングが、プログラム可能な汎用計算機の概念を考案したとき、 「コンピュータ」という言葉が意味するのは、計算機ではなく、"計算する者"つまり 人間を指すのが普通だった』ようだ。[6] コンピュータといっても、いまのようなハ ードでなくても良いわけである。話題がそれるが以前、私は幼い頃に、誰にでも、１ 度は考えるような少し不思議な疑問につまづいた。それは、人の手は当たり前のよう に動いているが、どこで、何が手を制御しているのかということである。もちろん、 脳から指令がでるわけだが、脳以外で情報をためておく場所、それはDNAという分子が おこなっている。DNAは、細胞内でたんぱく質を生成するための符号化の機能とその 符号化の情報を子孫の細胞へと受け継がせるための自己複製の機能を実現させるため に利用されている。大学入学当初、コンピュータというものにあまり関わったことの ない私は苦手なプログラムの授業を受けながら戸惑いを感じていた。今となっては、自 明のことではあるが、プログラムを書いているnotepadすらもプログラムでできている のではないかと。コンピュータといって当たり前に仕事のお供として存在している機械 はエンジニアが使い手の使いやすいように意図して製造したものなのである。何が言い たいのかというと、コンピュータは今、存在するような形をしていなくてもよいのでは ないかということである。
DNAを使って計算を行った人物がいた。RSA暗号の開発者の一人Leonard M. Adlemanは 、1994年にDNAを使い、NP完全問題である有向ハミルトンパス問題を解いた。そこから、 DNAコンピュータという分野が生まれた。
本論文は、Adleman の論文とA Sticker-Based Model For DNA computationのレビュー を行う。Adlemanの論文はDNA コンピュータという分野ができたきっかけとなる論文であっ たからである。また、A Sticker-Based Model For DNA Computation の論文は、Adleman と同じNP完全問題をDNAを使って解いた論文でRAMの概念をはじめにDNAコンピュータに取 り入れた論文である。また、そこで提案されたstickers modelを使い、自動で演算を行うコンピュ ータシステムのアイデアも紹介されている。
グラフとは点とそれらを結ぶ線の集合のことをいう。グラフと聞くと、棒グラフ、円グラ フなどいくつかの数値を図表で示したもののように思うが、今回は違う。点のことを頂点 といい、線は辺という。グラフの辺に向きが必要で辺を線ではなく矢印で表現する場合も ある。こうしたグラフを有向グラフという。隣接している頂点同士をたどった辺の系列を 歩道（鎖・ウォーク）という。辺の重複を許さない場合、路（小径・トレイル）といい、 頂点の重複も許さない場合、道（パス（開いた歩道をパスという場合は単純パス））とい う。[7]
図1.のグラフを考える。左はオイラーグラフ。右は有向ハミルトングラフというグラフで ある。オイラーグラフとはすべての辺を1度だけ通る路をもつグラフのことで、直感的には一 筆書きことである。オイラーパス問題とは一筆書き可能かどうかを問う問題である。ハミルト ングラフとは、特殊な頂点startから特殊な頂点goalまで全ての頂点を一度だけ通るパスが存 在するか、しないかを問う問題である。一見、オイラーグラフの方が難しそうにみえるが、問 題の難しさとしては、ハミルトングラフの方が難しいのである。では、一体何が問題の難しさ を決めているのであろうか。
通常のコンピュータで多項式時間に解を得ることができる問題の集合をPという。
直感的に説明すると、 5,3,1,4,6,2という文字列が入力されたときに、6が最大値で
あるというのは、入力長に比例した時間がかかる。また、
という行列が正解かどうかを判定するには、行列の積、n×nなら
かかる。しかし、ともに通常
のコンピュータで解を得るのに多項式時間で実現可能である。このような問題はPの問題の集合
に属する。
多項式時間で解けない問題も存在する。例として
などがあるが、この通常のコンピュータでは多項式時間で解けないであろう問題の集合の中 にNPが存在する。NPとは「問題に対して多項式時間長のヒントがあれば、Yes, Noを多項式時 間で判定できる問題」である。Pはいわば、「解くのが簡単な問題」の集合、NPは「答え合わ せが簡単な問題」の集合といえるのである
図1のオイラーグラフ問題はPに属する。有向ハミルトンパス問題はNPに属する。この二つの
グラフがそれぞれ属する集合が等しいかどうか。これはP=NP問題といわれ、この問題が解け
れば、賞金＄100万が出る数学の7大問題の一つである。現在では
と予想されている。つまり
、NPは通常のコンピュータでは多項式時間で解けないと予想されているのである。
図1.のオイラーグラフ問題は問題が解けるかどうかのチェック方法が存在する。それは頂 点に辺が奇数本つながっている頂点を奇点というのだが、奇点の数が0か2であれば、そのオ イラーグラフは一筆書き可能であるとわかる。これを一筆書きが奇点の個数に帰着できると いう。 また、一筆書きが奇点の個数に帰着できるということは
⇒ 一筆書きは奇点の個数ほど難しくない
⇒ 一筆書き
奇点の個数
という関係がある。
問題Aが問題Bに帰着されるとき、Bの解法はAを解くために使うことができる。計算の効率 を考慮に入れた帰着可能性を定義する。このとき、問題Aが問題Bに効率的に帰着できるなら ば、Bに対する効率的な解法はAを効率的に解くために使うことができる。
任意の入力wで動作を開始し、テープにf(w)だけを書き出して停止するような多項式時間 Turing機械Mが存在するとき、関数f :∑＊ →∑＊ は多項式時間計算可能関数である。
言語AとBに対して、すべてのwについて
w∈A⇔f（w）∈B
であるような多項式時間計算可能関数f :∑＊ →∑＊ が存在するとき、A
Bと書き、言語A
は言語Bに多項式時間帰着可能であるという。関数fは、AからBへ多項式時間帰着とよばれる。
AからBへの多項式時間帰着は、Aの要素かどうかの判定をBの要素かどうかの判定に変換す る方法を与える。したがって、帰着fを用いれば、w∈Aであるかを判定するためには、 f（w）∈Bであるかを判定すればよい。しかも、fの計算は効率的に行われる。この性質を使 うと、Bの判定問題を解く多項式時間アルゴリズムを用いて、Aの判定問題を解く多項式時間 アルゴリズムを構成できる。[5] 又、逆にAを解くことが困難であることがわかっている場合 、fの存在によりBを解くことも困難であることがわかる。
1970年代初頭にStephen Cook とLeonid Levinは、個々の問題の複雑さがNPのクラス全体の 複雑さと関係づけられるような、そのような問題を発見した。これらの問題のいずれにかに 対して多項式時間アルゴリズムが存在するならば、NPに属するすべての問題は多項式時間で 解くことができるのである。このような特質をもつNP問題はNP完全と呼ばれる。[5]
次の条件をみたす言語BをNP完全(NP-complete)という。
| i 番目の非決定性チューリング機械Ni にx を入れると
+i ステップ以内にacceptする}
P=NP問題の現状はP
NPが予想されている。つまり、有向ハミルトンパス問題はコンピュータ
では解けなそうなのである。しかし、現在と原理の違うコンピュータを用いることでNP完全問
題である有向ハミルトンパス問題を解いた人物がいる。
DNAとはDeoxyribo Nucleic Acid の略でデオキシリボ核酸のことである。DNAはヌクレオチドが 一列に連なった化合物である。その化合物が2列に並びお互い引き付けあうことで図2右図のよ うに2重らせんを形成している。DNAはたんぱく質を生成するための符号化の機能とその符号化 の情報（遺伝情報）を子孫の細胞へと受け継がせるための自己複製の機能のために生体内で利 用されている分子である。
DNAを構成しているヌクレオチドは糖、リン酸、4種類の塩基から構成されている。4種類の塩基 はアデニン、グアニン、シトシン、チミンである。4種類の塩基はそれぞれ、A、G、C、Tと略す る。それぞれの糖とリン酸は同じ構成をしているので、ヌクレオチドはA、G、C、Tで表現する ことができる。つまりDNAをA、G、C、Tで表現することができる。また、重要なことに、DNAの 表す情報をA、G、C、Tだけで表現することができるのである。ヌクレオチドの連なったものを DNA鎖と表現する。
DNAを構成する各ヌクレオチドは共有結合と水素結合という2種類の結合で形成されている。
各ヌクレオチドにおけるリン酸とその隣のヌクレオチドの糖が共有結合をして1本鎖を形成する。 そしてその鎖が2本並んだときに、各ヌクレオチドの塩基部分が水素結合する。先程の引き付け あうとはこの水素結合をさす。この塩基部分というのは2本並んだときの別のDNA鎖同士の塩基 である。そして、その水素結合をするときは、AはTとGはCと必ず対をなす。これをワトソンク リックの相補性という。
PCRは目的となるDNA配列を得るための方法である。また、ただ1つの分子から始めて、その DNA分子のコピーを比較的短時間で大量に生成できる。
変性→アニーリング→伸長→変性を繰り返すことにより目標分子と同一の2つの完全な 二本鎖DNAが生成される。
DNA分子の長さを測るときに利用される。DNA分子がマイナスに帯電しているために 、電界におかれるとプラス極へ向かって移動する現象を利用している。ゲルは分子のふ るいのように作用するので、小さな分子は大きな分子よりも容易にゲル中を移動する。 同じ大きさの分子は同じ速度で動くので一定の時間内では小さな分子は大きな分子に比 べてより遠くへ（長距離を）移動することになる。(図4)
ある溶液から、配列αを含む一本鎖分子をすべて取り出したいとする。このとき、
αの相補配列をプローブとよぶ（
）。このプローブ
を小さな磁気ビーズに付着させておき、抽出させたい分子の入った溶液にいれ、よく混ぜて時間
をおくと、αを含む配列分子がプローブと水素結合する。そこで磁石を利用して磁気ビーズを容
器の壁に吸い寄せたまま、溶液を除くことによりプローブに結合した配列分子を残すという方法
である。(図5)
この論文は、DNA コンピュータという分野ができるきっかけとなった論文である。 この論文ではAdleman がNP完全問題とされている有向ハミルトンパス問題をDNAに符号化 しDNAでの実験を行うことで解を得ることに成功した。つまり、Adlemanは有向ハミルトン パス問題に対するアルゴリズムをDNAの実験に帰着したことになる。
Adleman は自身の考えたDNA計算の力をNP完全問題をそのmodelを使って解くことにより 示した。そのNP完全問題の中で選ばれたのが、有向ハミルトンパス問題である。図1の右 のグラフの問題である。
実際に、Adleman が解いた有向ハミルトンパス問題は図6のように7頂点,14辺の有向ハミル トンパス問題である。また、この問題は頂点につけられた数字を追っていけば、ハミルトン パスを得ることができるように、意図的に番号付けが行われている。本論文では、説明の便 宜上頂点の名前を図7のように変更する。
全ての解をしらみ潰しに探せば解にたどり着くかもしれないが、計算機科学上、それでは解を 得るまでに最悪、指数時間かかってしまうこともありえる。（上記の問題はスケールが小さい ので、すぐに解を得ることは可能である）この問題をAdleman は,DNAコンピュータを使って、 いくつかのstepを踏むことで現実的な時間で解いたのである。その手順を以下に示す。
頂点と辺を符号化する。また、各頂点、各辺を符号化する際の手順としては、本論分では複雑なDNA配列で頂点を符号化する、そして、同じ辺、頂点がないように配列を振り分ける。詳細は[3]を参考。 例として、start→大阪間の符号化について説明する。
手順１で生成された符号化された全てのDNAを（辺、頂点全て）DNAリガーゼという酵素と 一緒にして試験管にいれる。辺は頂点のワトソンクリック相補性によって決めていたので、 その辺を表すDNAが頂点を表すDNAのあて木のように用いられる。これは、DNAの相補性による アニーリングの性質を利用したものである。(図9)
step２で生成されたパスから、startはじまりgoal で終わるパスを表すDNA配列を全て分離 する。この作業は、PCR（ポリメラーゼ連鎖反応）を利用する。(図10)
step３で得られたパスの中から、今回は頂点数7のパスのみを全て分離する。 この作業には、ゲル電気泳動が使用される。(図4)
この時点でstep４で得られたパスというのは、start で始まり、goalで終わり、 さらに頂点数7のパスのみが残っている。その残ったパスの中から、全ての頂点を 通ったパスのみを分離する。マグネティック法を利用して、大阪、東京とすべて の頂点に対して検査を行う。(図11)
最後に、step５が終わった段階で、DNAが残っているかどうかを確認する。もしDNAが残っているならば、その残っているDNAというのが、問題の解を表すものとなる。
以上がAdlemanの実験である。
Adleman の有向ハミルトンパス問題の解法は単にひとつの実験に留まらず、非常に一般的は 計算メカニズムを提供したといわれる。そのことから、この演算パラダイムをDNA計算におけ る"Adlemanパラダイム"と呼ばれる
この論文は、Adlemanの論文や、それ以降に出たDNA Computerの論文と同じように、与えら れた情報を表現する中心のメカニズムとして、DNA鎖を使用している概念モデルである。また 、後半にはこのモデルを利用して自動で演算を行うための実装を行うアイデアが紹介されてい る。与えられた情報を2進数で処理するための工夫がなされている。この論文が出る以前のDNA コンピュータに比べて、このモデルの利点は、DNA鎖の拡張を要求しないRAM(ramdom access memory)をもっていること、酵素を必要としないこと、材料を再利用できることである。また 、目標として4つあげられている。一つ目はDNAコンピュータ によって、汎用目的のアルゴリ ズムを構築する。この汎用目的のアルゴリズムとは探索問題の広いクラスを解きうるアルゴリ ズムである。広いクラスとは、NP完全問題か、それ以上のものである。二つ目はほどほどの量 のDNAでNP完全問題かそれ以上の問題を解けることを証明すること。三つ目は構造や共有結合 の破壊はDNA Computer には本質的ではないことを示す。四つ目はSequence-specific separat ion は汎用目的の分子コンピュータを構築するには、DNA工学としても十分であることを示す 。以上4つが目標としてあげられている。
この方式はひとつのbit情報を表現するために、単一のDNA鎖とそのDNA鎖と相補的な関係 のDNA鎖の小片が水素結合でくっつくことにより表現する。まず、このモデルを理解するた めに基本的な語句の説明をする。
※例として(7,3)libraryとは、{0000000,0010000,0100000,1000000,0110000,1010000,1100000,1110000}のことである。 次に、情報の表現方法を説明する。 図12はsticker modelの情報表現方法の概略図である
memory strand の長さはNあり、bit領域は各々K個存在し、各々のbit領域の長さをMとする。
このとき、
である。それぞれmemory strandにはN領域以外に汎用領域なる領域をもっている。
また、長さとはヌクレオチドの列のことである。例えば、AGCTTであれば長さ5である。memory
strandには先頭に特定の配列をもっているものも存在する。この配列をinitial setと呼ぶ。
このinitial setをもつtubeのことをmother tubeと呼ぶ。initial bit はK bit中にL bitの問
題により与えられた入力を符号化するための領域のことである。また、(K-L)bitは初めの状態
として全てbit をoffにしている。この(K-L)bit領域のことをワークスペースと呼び、問題を
計算するなかで演算が行われるスペースとして利用される。
stickersがmemory strand の対応するbit領域にはりつくことで、2進数を表現する。 bit 1 にはS1、bit 2 にはS2、bit k にはSkというようにstickersは各々決められたbit にだけにはりつく特性をもっている。(Sとはstickerを表す) stickersがmemory strand の所定のbit領域にはいついたら、そのはりついたbit領域は"1"とする。はりつかない領 域は"0"とする
この方式には、tube に対して、4つの基本演算が用意されている。combine, separate on Bit X, Set Bit Y, Clear Bit Z である。(図14)
今まで定義したモデルの力を証明するために、NP完全問題以上の難しさとされている問題の 最小被覆問題を解くことにする。最小被覆問題とは全体集合Uを部分集合Ci（i={1…B}）の和集 合で被覆する場合、どの組み合わせが全体集合Uの要素を被覆するために最小の和集合で被覆す ることができるかを問う問題である。
U：全体集合
C= {C1, …,CB} , Ci
{1,…,A}, 最小部分集合I{1,…,B} , ∪i
ICi = {1,…, A}
但し、A,Bは自然数とする。
問題の例として U={1,…,10} ,C={{1,3,5,7,9}=C1, {2,4,6,8,10}=C2, {3,6,9}=C3, {1,2,3,5,7}=C4とする。 Uを被覆するものとして、C1∪C2=U と、C2∪C3∪C4=U など多数考えられるが最小被覆なので、I={1,2} となる。この問題を基本演算を利用して解くことにする
以上のアルゴリズムに従い、例題を解いてみる。
図15例題の問題の符号化と初期化を表している。mother tube先頭のB bit 分に0,1の全て の組み合わせ分のmother tubeを用意する。また、A bit はすべてのbit 領域を0にしておく 。
mother tube の先頭のbit が1となっているものと、0になっているものを基本演算separateにより分離する。そして、先頭のbit 領域が1になっているtubeの入っている容 器にstickers を投入する。そして、分離させたtubeをもう一度、基本演算combineに より合わせる。この作業を問題の入力を表すbit 領域（例題ではB bit）の全てで行う 。(図16)この作業を終えることで、(K,L)libraryが作られる。
以上の作業を例題において行うと、表1の(K,B)libraryを得る。 表1について説明する。1行で1つのmemory complexを表現している。 先頭4列はB bit を部分集合、つまりC= {C1, …,CB}。残りの10列はC= {C1, …,CB}に含まれ る要素を表している。また、全ての要素を被覆したmother tubeには1列目に☆が、要素が1つでも 被覆されていないものには×が記されている。
例えば、表上から3行目の場合、 00011110101000はC4={1,2,3,5,7}を表現している。 また、12行目の場合、 11001111111111はC1∪C2={1,2,3,4,5,6,7,8,9,10}を表現している。また、全ての要素を被覆しているので1列目には☆が記載されている。 ※今回は、例題を分かりやすくするために表を用いたが、実際のDNA実験では表が作られるわけではない。
| memory complex→ | C1 | C2 | C3 | C4 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| × | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| × | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| × | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| × | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| × | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| × | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| × | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| × | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| × | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| × | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| ☆ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| ☆ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| × | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| ☆ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| ☆ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| ☆ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
表1.(K,B)library
以上が、stickers modelで最小被覆問題を解く際のアルゴリズムである。 ここからは、stickers model を実際にDNAで実装する際の方法、注意点を紹介する。
この実装は、2つのtubeを再び水和させることによって実行可能である。しかし、この単純 な方法は、混ぜたり、ピペットでtubeを取り出したりするときに、細心の注意が必要である。 もし、ピペットにごくわずかな量のDNAが残っていたとしても、それは大変な誤差の原因にな る。なぜなら、問題の演算において、入力を表現するDNA等、関係のある分子がはじめから少 ない状態であるからである。
この実装は、sticker modelで一番重要である。なぜなら、解を表現するDNAを分離してい く中で、毎回使用される演算であるからである。実装の注意点はmemory complex 同士を分離 させる時に、そのmemory complexにアニールされているsticker はsticker がアニールされ ていたbit領域にはりついた状態でなければいけない。つまり、そのbit領域から、stickerが はがれてはいけないのである。対応策としてseparation の実装には、プローブを使う。プロ ーブは対応するbit領域にそれぞれ用意しておく。※マグネティックビーズ法参照
プローブは、対応したbit領域と相補関係のあるDNAで構成されているが、stickerがはがれ ないようにするために、sticker がアニールされている力よりも弱い力でmemory complexを とらえなくてはいけない。(図17)
setting は対象になるbit領域に直接stickerをアニールする。set を行うbit領域に対応し
たstickerを大量に用意しておく。そして、setを行うbit領域を含むmemory strandとその
大量に用意したstickerを合成させる。大量に用意したため、アニールされなかったsticker
は取り除く。
clearing は現段階では実装可能でないとされているが、clearingの実装ができなくて
もsticker model の計算能力は変わらないとされている。
アルゴリズムとして
と、紹介したがアルゴリズムの②(K,L)libraryを用意することはstickerが1…Lのbit領域 内で、memory strandにランダムにstickerが加えられなければならない。その手順を以下に示 す。
memory strandを2つの等しい量に分ける。ひとつには、1…Lの全てのbitよりも多い量の sticker を加える。これで、1…Lの全てのbit領域にsticker がアニールされることになる。 このとき、アニールされなかったsticker は取り除き、その後、最初にわけたものと結合さ せ、また、熱する、そしてもう１度、sticker を解離させる。その後、もう1度、冷やすこと でsticker をアニールさせる。
この方法で実際に(K,L)libraryを作ってたとき、どのくらいの確立で(K,L)libraryが
できるかということを考える。上の手順で各bit 領域はアニールされるものとされない
ものの1/2の確立をもつことになる。また、bit領域は全て合わすと L bitになるので、
L桁の特定のbit ストリングが現れる確立は
となる。また、
L桁の特定のbit ストリングが現れない確立は1-となる。
(K,L)libraryで特定のbitストリングが現れない確立は2
個のbit パターンが存在するので、
となる。これを計算すると、各々のmemory complexは少なくとも1回でおよそ63%の可能性を
持って作られる。このパーセンテージはmemory strand を 2 個以上を合成することによって
明らかに増やすことが可能である。この手段は化学量論的にはエラーに強いパーセンテージ
といえる。
最終的に解を得るためには溶液の中でmemory complexが存在するか、しないかを検出できる 必要がある。もし、何か存在するならば、少なくともひとつのmemory complexを単離できる 必要があるし、そして、それにアニールされているstickerを確認する必要がある。
memory complexの検出は、各々のmemory strand に蛍光性のラベリングを施すことにより 可能となる。また、アプローチとしては、全ての答えとみなされるmemory complexを含んで いる溶液の中から器具を利用して答えとなるDNA配列を実際に目で見て確認するのである。
stickers modelを具体的なシステムとして紹介する。
図18はstickers modelをシステム化したstickers machineである。この装置は2種類のTube と呼ばれる管により構成されている。ひとつは、情報を表現する全てのDNAが入っているData Tube と各基本演算を行うoperator Tube である。Data Tube にはmemory strand も stickers も通さないMembrane(薄膜)が存在し、この薄膜は情報を表現するDNA に極性を与える。薄膜に 近いコネクター部の先はclean side と呼び、memory strand ,memory complex, stickers, tube等つまりDNAは存在せず、冷水、熱湯のみが存在する。その反対のコネクター部は dirty side と呼び、memory strand ,memory complex, stickers, tube等、情報を表現する DNAが存在する。Operator Tubeはseparation のためのプローブを固定したSeparation Tubeと、 stickersは通過できるがmemory strand は通過できないフィルターをもったsticker Tube, 単に管をつなぐだけの役割だけをもったblank Tube の3種類がある。
この装置は図18下段のように、両側にData Tube を置き、この間にあるoperator Tubeをコ ンピュータ制御のロボットのようなもので必要に応じて置き換え、さらにDNA 複製のアルゴ リズム（主にアニーリングなど）に合わせて左右から自由に温かい水流や冷たい水流を流せ るようにしたもので、先に示した4種類の演算を自動で行える。そのため、最初に問題の設定 をするだけで、自動で演算を行うことが可能である。
以上、stickers modelを紹介した。このmodel はNP完全問題以上の問題を解く力を持ち合わせ ており、また、酵素をつかわないこと、ramの機能を果たしているという利点をもっている。 また、問題の設定を行うだけで自動で演算を行う装置の紹介もされている。解を得るために4つ の基本演算、特にseparateはDNA工学においてもDNAコンピュータを構築するうえで十分である ことも示されている。また、Adlemanの実験に比べ、限りある量のDNAで計算を行うことが可能 である。
本論分はDNA コンピュータの論文として、AdlemanのMolecular computation of solution to combinatorial problemsとSam Roweis、W.K.RothemundらのA Sticker-Based Model for DNA Computationを紹介した。Adlemanの論文は何もないところから、このDNAコンピュータ という分野を起こしたすばらしい論文である。また、DNAを使った計算スタイルでそれまで通常 の計算機では解くのが難しいとされていたNP完全問題を解いたので、計算機科学としても新た なアルゴリズムの開発にもなった。
stickers model の論文は、NP完全問題を解く能力のある演算を用意し、その演算を利用して NP完全問題である最小被覆問題を解いた。そして、RAMの機能をもっており、酵素を使わなくて よいという利点をもちあわせている。また、実装のアイデアやその実装におけるDNA実験の可能 性についても紹介されている。
これからの私の方針として、DNA コンピュータの関係する分野に入り社会的に良い影響や良い 循環を生むことのできる研究や開発を行っていきたいと思う。
DNA コンピュータについてご指導いただきました東京工業大学大学院 木賀大介准教授、山村雅幸教授、 東京大学大学院 有田 正規准教授に感謝いたします。
最後に、研究者としてはなんであるか、また、論文を読むにあたっての様々な注意、DNA コンピュータを卒論のテーマとして扱っていただいた坂本直志准教授に感謝いたします。