|
|
トップページ ナノテクノロジーナノコンピューティング |
|
|
分子コンピュータ
|
おそらくナノコンピュータと言われるもので、一番最初に実現しそうなのが、この分子コンピュータというもの。分子の性質をアルゴリズムに取り入れることで、一つのプロセッサで複数の計算処理を可能にし、さらにコンピュータ自体も非常に小さく安価にできる可能性を秘めています。
ここではDNAコンピューティングについて紹介します。
数学的に有名な問題、「有向ハミルトン経路問題」（通称は出張セールスマンの経路問題）をDNAコンピューティングで解く場合について書いています。
「出張セールスマンの経路問題」とDNAコンピュータ
現在のCPUにとって苦手な処理といえば、答えの候補が一度にたくさん出てくるものでしょう。その例として古典的な数学の問題に「有向ハミルトン経路問題(directed
Hamiltonian Path Problem)」というものがあります。イメージがわきやすいように言いかえれば、「悩める出張セールスマンの旅行計画問題」といったところでしょうか。この悩めるセールスマンの問題を取り上げて、DNAコンピュータがどのような仕組みで情報処理をしているか見てみましょう。
あるセールスマンが飛行機に乗って、セールスのために、いくつかの都市すべてを立ち寄らなければならないとします。ただし、このとき重要なポイントとなるのが、すべての都市どうしがエアラインで結ばれているわけでないということと、一度通った都市は二度と通ってはいけないという制限があるということです。これがセールスマンの悩みの種です。
モデル図「悩める出張セールスマンの旅行計画問題」 |
この図の場合、「長崎」から出発して、「広島」、「大阪」、「東京」のすべての都市を一回ずつ立ち寄り、目的地である札幌に向かわなくてはいけません。あなたならどのように旅行計画を立てるでしょうか？それほど難しくありませんね。答えは「長崎＞東京＞広島＞大阪＞札幌」という順です。（実際の問題では、都市数がもっと多いが、話しやすくするために５都市にした。）
この程度の都市の数なら紙も鉛筆も必要なく、頭の中で簡単に解けるでしょう。しかし、都市の数が増えると、それを結ぶエアラインの数も指数関数的に増えてきます。おそらく都市の数が10を越えるころには、頭の中では解けなくなり、コンピュータに頼ることになります。しかし、今のコンピュータでも1万都市を超えるとなると、多くのハイパワーコンピュータを同時に稼動させても何週間かかかるでしょう。いずれにしても、現在のコンピュータにとってはあまり相性のよい問題ではありません。
この問題は数学的にもコンピュータサイエンス的にもよく出てくる古典的なものなのですが、DNAコンピュータはこれをどのように解くのでしょうか？いくつかのステップに分けて考えてみましょう。
[step1 考えられうるすべての旅行計画を手当たり次第つくる]
何はともあれ、コンピュータが「０/１」の文字に置き換えて処理しているように、DNAコンピュータもDNAの扱いやすい文字、つまり「A,T,C,G」に置き換えてやる必要があります。そこで、５つの都市を区別できるように、次のように置き換えてやりましょう。以下のようなDNA断片をつくります。
| 「長崎」 |
ATGCCG |
| 「広島」 |
TCGTAC |
| 「大阪」 |
GCTACG |
| 「東京」 |
CTACGG |
| 「札幌」 |
CTAGTA |
（※置き換え方にとくに決まりや法則性はないが、下で述べるエアラインと合わせて、お互いの都市が区別できればよい。）
「完璧な旅行計画書の書き方 図1」 |
次に、「長崎＞広島」、「東京＞大阪」など、それぞれのエアラインをDNAの文字に置き換えてやらなければなりません。ただ、ここで、都市名とうまく対応させる方法がないか考えます。そこで「広島＞大阪」の場合なら、「広島(ATGCCG)」の後半の３文字'CCG'と、「大阪(GCTACG)」の前半の３文字'GCT'をくっつけて'CCGGCT'を考え、これと相補性をもった'GGCCGA'を「広島＞大阪」を表すエアラインとします。逆に「大阪＞広島」なら'ACGATG'と相補性を持つもの、つまり'TGCTAC'になります。
この方法で置き換えれば、旅行経路を、都市の順番(「長崎」＞「東京」＞「広島」＞「大阪」＞「札幌」)に並べた'ATGCCGCTACGGTCGTACGCTACGCTAGTA'と、エアラインの順(「長崎＞東京」、「東京＞広島」、「広島＞大阪」、「大阪＞札幌」)に並べた、'GGCGATGCCAGCATGCGATGCGAT'が、頭尾の３文字を除いて相補性を保っているという仕組みになっています。
「完璧な旅行計画書の書き方 図2」 |
あとは、都市とエアラインを表すDNA断片を試験管のなかに放り込みます。そのときに小さなDNA断片を結合する役割をもつ「リガーゼ」という酵素を一緒に入れておけば、自己組織化によって小さなDNA断片は自然と集まっていきます。都市名を表すDNA断片とエアラインを表すDNA断片が、お互いにくっつき合って、自然と答えとなる旅行計画書を書いてくれるというわけです。
もちろんこれだけで、正しい旅行計画を表すDNA断片だけができるわけではありません。むしろ正しい計画書はほんのわずかで、あとのDNA断片の集まりは数が足りなかったり配列が間違っていたりと、デタラメなものばかりができているはずです。そのため、正しい旅行計画に相当するDNAだけを取り出してやる必要があるのですが、それはまるで大草原の中から小さな藁を拾い上げるようなもので、簡単なものではありません。
そこで、次にどうやって正解の旅行計画を見つけ出すかを考えてみましょう。
[step2 デタラメな旅行計画書の山から、正しいものを取り出すには…]
1.試験管の中には、さまざまの長さや配列のDNA断片が存在しているはずです。そんな中でも、まずは出発点が「長崎」、最終地点が「札幌」になっているもの、つまりDNA断片の端が「長崎」と「札幌」を表す配列になっているものだけを拾い上げたいのです。これは、「ポリメラーゼ連鎖反応(PCR)」で「プライマー(primer)」という相補性を持ったDNA小断片を利用することで可能になります。私たちが欲しいDNA配列は出発点が「長崎(ATGCCG)」で最終地点が「札幌(CTAGTA)」のものです。そこで、それと相補性をもったプライマー「長崎'(TACGGC)」と「札幌'(GATCAT)」を用意します。これによって、端に「長崎」と「札幌」をもつものばかりが複製されます。（ポリメラーゼ連鎖反応(PCR)については下に詳しい解説サイトを紹介）
（完璧な旅行計画書の書き方 図3） |
しかしこの時点では、「長崎」と「札幌」の間にくる都市の順序が間違っていたり、長すぎたり短すぎたりと、デタラメな旅行計画書が多く残っているはずです。そうは言っても、とにかくこれで出発地点が「長崎」、最終地点が「札幌」の計画書だけに絞り込むことができました。このとき図3のＡは取り除かれます。
2.次に、上で選択した計画書の中から、５つの都市だけを通っているものだけを選び出しましょう。ここでは、ゲルの上にDNA断片を染み込ませ両側から正負の電気をかけて、負に帯電したDNA断片を泳がせる「電気泳動」という操作を行います。このとき、DNA断片の長さ(重さ)に応じて、泳ぐ距離が変わってくるので、30塩基対(6塩基対×5都市)のものだけを選び出すことができるというわけです。こうして図3のＢは取り除かれます。
これでだいぶ計画書を絞り込めましたが、まだデタラメなものが含まれています。例えば「長崎>大阪>広島>大阪>札幌」(図3のＣ)というような計画書が含まれているはずです。つまり、すべての都市を１度だけずつ立ち寄るという条件を満たしていないものです。そこで、今度はすべての都市に立ち寄っている計画書だけを選ぶために、次のような方法を考えます。
3.たえば、東京(CTACGG)に立ち寄る計画書を拾い上げるために、東京と相補性をもった「東京'(GATGCC)」というDNA断片で、計画書のDNA断片を探します。このとき東京を含んでいない計画書があれば、それは「東京'」とうまくくっつかないので拾い上げられることはありません。つまり、「長崎>大阪>広島>大阪>札幌」という間違った計画書はそのまま見捨てられてしまうのです。こうして、５都市すべてに相補性をもったDNA断片で拾い上げの操作を行います。
この一連の結果得られるものは、出発は長崎、最終は札幌で、５つの都市すべてを５回だけで旅行するというもの・・・つまり、それこそが完璧な旅行計画書なのです(図3のＤ)。
[step3.完璧な旅行計画書の都市の順番を吟味する]
さて、完璧な旅行計画書を選び出すことはできましたが、そのATCGの配列を読んで都市がどのような順番で並んでいるかを知らなくては、旅行計画書を書いたことにはなりません。現在では、直接DNAの塩基配列を読むことのできる特殊な顕微鏡(STMなど)があるのですが、それらを使わない方法を考えてみましょう。
ここではstep2のはじめに行ったプライマーを利用したポリメラーゼ連鎖反応(PCR)を行います。例えば、「大阪」の位置にプライマーを取り付けてPCRを行うとしましょう。すると「長崎、…、大阪」のDNA断片ができます。それの塩基数を数えれば24塩基となるはずです。したがって24÷6=4で大阪が４番目ということになります。
（参考図：ポリメラーゼの利用↓） |
あとは同じようにして、「東京」、「広島」とプライマーをつけてPCRを行えば、12,18塩基となり、２番目、３番目と判断することができます。
これでついに完璧な旅行計画を書き上げることができたのです。出張セールスマンの悩みは解消されました。
DNAコンピュータの課題と展望
これまで長々と話してきたセールスマンの旅行計画書の問題が、実際にDNAを使って実験されたのは、1994年のことでした(このときは20都市で行われた)。
それから5年以上が経ち、ヒトゲノム解析が終わるなど、DNAコンピュータに深く関連している分野は大きく進歩し、それに伴って、ゲノム解析などの操作の多くが機械化されました。例えば、step2,step3のややこしい操作も、今では機械でほぼ自動化することは可能です。
ところが、現時点でもDNAコンピュータがいつ登場するかということになると、誰もはっきりしたことはいえません。5年以上も前にあれほど輝かしい成果があげられたのに対し、今でも問題が山ずみで、DNAコンピュータの実現へはまだ時間がかかるのです。しかし、それはなぜでしょうか？どういった問題があるのでしょうか？
まず、小型化が難しいということがあります。94年のセールスマンの実験のときには、試験管の中で行われましたが、この方法では小型化などという言葉と無縁です。もっとも、現在では試験管の中以外でも、金属プレートにDNA断片を固定して実験を行うなどして、一連の操作をしやすくしていますが、やはり小型化には難しい課題が山済みになっています。このままでは高集積のコンピュータをつくることは非常に困難です。
また、DNAの複製などの際には、酵素などの読み違えなどを起こし、エラーが生じることは避けられません。エラーが起こる割合は非常に小さいのですが、ポリメラーゼ連鎖反応のように何度も複製を繰り返していると、エラーの影響がだんだんと大きくなって誤差が無視できなくなるという問題が起こります。これも、DNAコンピュータ実現への大きな障害です。
なにより、DNAコンピュータに本当に向いている処理方法というものが、いまだはっきりしていないことに大きな問題があります。94年のときのセールスマンの計画書に関する実験方法では、他の問題を解くのに応用しにくいということがあります。
そのため、これまでにセールスマンの旅行計画以外にも、チェスの解き方や、ピザのトッピングの仕方など、別のさまざまな方法が試されてきました。しかし、いずれの場合も、DNAコンピューティングのごく限られた一例に過ぎません。DNAのどんな特徴に注目して情報処理に応用するかを見つけ出せるかどうかが、DNAコンピュータ、そして分子コンピュータの成功の大きな鍵と考えられているのです。
さらに詳しく読見たい方は
 気になる科学ニュース調査
「DNAと自ら完成するジグソーパズル、チェス、数学の問題」
をどうぞ。
|
|
-アイコンの説明-
 ・・・「気になる科学ニュース調査」からの関連記事です。
 ・・・「こちらは気になる科学探検隊」の外部へのリンクです。
 翻訳サイトの紹介が別ウィンドウで開きます。
|
DNAと自ら完成するジグソーパズル、チェス、数学の問題
上で紹介したDNAコンピュータ+αの内容。自己組織化など。
Computing with Molecular（英語）
Scientific Americanの特集から。
Molecular Computing（英語）
MITのポピュラーサイエンス雑誌TechnologyReviewの記事から。
Molecular Electronics Change Everything（英語）
Wired Magazineの記事から。
How DNA computing works?（英語）
分子コンピュータの中で有力候補の一つに挙げられるDNAコンピュータについて。このサイトでは、テクニカルな内容はおさえて、比較的簡単な言葉で説明されています。
- How Stuff Works
Molecular Computer Project(英語)
専門的な内容を知りたい場合にどうぞ。
MITRE The Nanoscaleelectronics & Nanocomputing
Home Page（英語）
ナノコンピュータの中でも特に分子エレクトロニクスについて研究している組織。ホームページではナノコンピュータやナノエレクトロニクスの紹介など。
DNAコンピュータについて
Laboratory for Molecular Science（英語）
94年に世界で一番最初に、ハミルトニアン経路問題を使ってDNAコンピュータのデモンストレーションしたエイドルマンの研究室のホームページ。
Interview - Leonard Adleman（英語）
エイドルマンへのインタビュー 96年
Adleman's Lecture on Molecular Computing - MSRI（英語）
エイドルマンの公演のビデオ収録。ページの左上の方をクリック。start
56kps video
Water drop holds a trillion computers （英語）
DNAの文字配列を「ソフト」、制限酵素を「ハード」としたDNAコンピューティングについて。ムービーもあり。
- Nature Science Update
Game of life: Biocomputers take their first
step with a little chess puzzle- Princeton（英語）
チェスを題材にしたDNAコンピューティングのデモンストレーション。そのときのプレスリリース。
DNAコンピューティングで重要な成果 - Hotwired
DNAコンピューティングを試験管のなかから金属平面上にうつしたときのニュース。
DNA Computing: A Primer - arstechnica（英語）
DNAコンピューティングについてとても詳しい解説
 |
|
|
