(57)【要約】【課題】ＤＮＡ等以外の生化学分子を用いて超並列コンピューティングを可能とする方法を提供する。【解決手段】この方法は、複数種類のポルフィリン金属錯体のシーケンスにより、解に対する制約を有する所与の組合せ問題中の組合せ要素を符号化するステップ３０と、符号化するステップ３０により得られた符号に対応するポルフィリン金属錯体のシーケンスの集合を準備するステップ３４と、ポルフィリン金属錯体のシーケンスの集合を反応槽４２に投入し自己組織化させるステップと、反応槽４２中に自己組織化により得られた構造体５０中で、所与の組合せ問題の制約を充足するものを選択するステップ５２と、選択するステップで得られた構造体を構成するポルフィリン金属錯体のシーケンスの符号を解読することにより、所与の組合せ問題に対する解答を得るステップ５４とを含む。【選択図】      図３
2006244103.tif 000002
【特許請求の範囲】
【請求項１】
ポルフィリン金属錯体を用いた分子コンピューティング方法であって、
複数種類のポルフィリン金属錯体のシーケンスにより、解に対する制約を有する所与の組合せ問題中の組合せ要素を符号化するステップと、
前記符号化するステップにより得られた符号に対応するポルフィリン金属錯体のシーケンスの集合を準備するステップと、
前記ポルフィリン金属錯体のシーケンスの集合を反応槽に投入し自己組織化させるステップと、
前記反応槽中に前記自己組織化により得られた構造体中で、前記所与の組合せ問題の前記制約を充足するものを選択するステップと、
前記選択するステップで得られた構造体を構成するポルフィリン金属錯体のシーケンスの符号を解読することにより、前記所与の組合せ問題に対する解答を得るステップとを含む、ポルフィリン金属錯体を用いた分子コンピューティング方法。
【請求項２】
ポルフィリン金属錯体を用いた分子コンピューティング装置であって、
複数種類のポルフィリン金属錯体のシーケンスにより、解に対する制約を有する所与の組合せ問題中の組合せ要素を符号化する符号化装置と、
前記符号化装置により得られた符号に対応するポルフィリン金属錯体のシーケンスの集合を作成するポルフィリン金属錯体シーケンス作成装置と、
前記ポルフィリン金属錯体のシーケンスの集合が投入される反応槽と、
前記反応槽中に、ポルフィリン金属錯体のシーケンスの集合における自己組織化により得られた構造体中で、前記所与の組合せ問題の前記制約を充足するものを選択する選択装置と、
前記選択装置で得られた構造体を構成するポルフィリン金属錯体のシーケンスの符号を解読することにより、前記所与の組合せ問題に対する解答を得るポルフィリン金属錯体シーケンス解読装置とを含む、ポルフィリン金属錯体を用いた分子コンピューティング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は分子コンピュータに関し、特に、ＤＮＡ以外の生化学分子を用いた並列処理コンピューティング技術に関する。
【背景技術】
【０００２】
コンピュータはもはや現代生活に不可欠となっている。今ではコンピュータの存在しない家庭の方が少数派であり、またコンピュータを用いない職場は数えるほどしかない。コンピュータはあらゆるところに使用されている。このようにコンピュータが普及したのは、半導体関連の技術の進歩とソフトウェアの進歩とによるところが大きい。
【０００３】
しかし、コンピュータの能力が高くなるにつれ、暗号化通信、遺伝子解析、地球規模での気象解析等、さらに大量かつ高速のコンピューティング資源を必要とする技術が現れてきている。従って、コンピュータの能力をさらに高める要求はさらに強くなっている。
【０００４】
しかし、現在のコンピュータの大部分はいわゆるノイマン型コンピュータであり、本質的には直列的に命令を実行するものである。そうしたノイマン型コンピュータを高速化するためにはいくつかの方策がある。
【０００５】
第１の方策は、動作速度を規定するクロック信号の周波数を高くすることである。過去のコンピュータの高速化は、この方策によって実現されてきた。
【０００６】
しかし、クロック周波数が高くなると消費電力も高まり、また信号のスキューなどを回避するために回路をさらに高集積化する必要がある。従って製造技術をさらに高度化するための技術の確立が必要であるが、それは難しい。また現状で半導体を用いた回路の大きさはそろそろ限界に近づいており、例えば配線間でのマイグレーションやメモリにおけるソフトエラーなど、高密度化ゆえに起こる問題点に対処する必要がある。実際上、そうした問題を解決することは極めて困難である。
【０００７】
第２の方策は、処理の並列化を高めることである。並列化には少なくとも２種類ある。第１の種類の並列化は、コンピュータプログラムで実現される処理に内在する、並列化可能な部分を抽出し、異なるＣＰＵ（中央演算処理装置）で実行することである。１台のコンピュータに複数のＣＰＵを搭載してもよいし、いわゆるグリッドコンピューティングのように、物理的に種々の場所に存在する多数のコンピュータを互いに通信網で接続することで並列処理を実現化してもよい。
【０００８】
しかしこの第１の種類の並列化では、必然的にハードウェアが高価となる。また、単一のＣＰＵで処理を実行する場合と比較して、複数のＣＰＵで処理を行なうためのオーバヘッドが大きくなるという問題もある。
【０００９】
第２の種類の並列化は、コンピュータのアーキテクチャそのものを見直し、本質的に並列処理が可能なアーキテクチャを採用することである。例えばデータ駆動型コンピュータ等はその典型であるが、この他にも有力な候補としてＤＮＡ（デオキシリボ核酸）コンピュータがある。
【００１０】
ＤＮＡコンピュータは、ＲＳＡ公開暗号化方式の提案者の一人でもあるコンピュータ化学者Ｌｅｏｎａｒｄ  Ａｄｌｅｍａｎ（レナード  エイデルマン）により発案され、１９９４年にその実験結果が公表されてコンピュータ技術者及び生物化学者の間に大きな波紋を広げた（非特許文献１を参照されたい。）。エイデルマンは、ＤＮＡを計算資源として用いていわゆるＮＰ完全問題のひとつであるハミルトン経路問題（Ｈａｍｉｌｔｏｎ  Ｐａｔｈ  Ｐｒｏｂｌｅｍ：以下「ＨＰＰ」と呼ぶ。）を解く実験を行ない、実際にその解を得たのである。
【００１１】
エイデルマンの提案したＤＮＡコンピュータは、ＤＮＡの持つ符号としての特性を利用して、ＨＰＰにおいて出現する「都市」とそれらを結ぶ「道」とを符号化し、さらにＤＮＡの相補性を利用して、それら都市と道とを表すＤＮＡ断片を生化学反応で結合させることにより、問題に対する解の候補（都市を表すＤＮＡと道を表すＤＮＡとが様々な組合せで連結したもの）を得る。得られた候補の中から所定の条件を充足するＤＮＡ配列を選択して解とする。
【００１２】
このＤＮＡコンピュータがノイマン型コンピュータと異なるのは、処理が、多数のＤＮＡ断片を用いて本質的に高度に並列的に行なわれるという点である（「超並列性」）。しかもＤＮＡの相補性を利用しているため、解の候補は自律的に得られ、反応の過程で特に操作を必要としない。このＤＮＡコンピューティングの技術を用いたものも既に製品化されている（特許文献１）。
【特許文献１】特開２００２−３１８９３２号公報
【非特許文献１】レナード  Ｍ．  エイデルマン、「組合せ問題に対する解の分子計算」、サイエンス、第２６６巻、第１１号、１０２１頁〜１０２４頁、１９９４年（Leonard  M.  Adleman,  “Molecular  Computation  of  Solutions  to  Combinatorial  Problems”,  SCIENCE,  Vol.  266,  No.  11,  pp.  1021-1024，1994）
【発明の開示】
【発明が解決しようとする課題】
【００１３】
エイデルマンの論文発表後、種々のＤＮＡ計算手法が発表されている。しかしそれらはいずれもエイデルマンの基本的な考え方に従いＤＮＡ又はたんぱく質（以下「ＤＮＡ等」と呼ぶ。）を計算資源として用いるものである。ＤＮＡ等以外の生化学分子を用いてＤＮＡコンピュータと同様の超並列性を実現しようとする試みはほとんど見られない。ＤＮＡ等以外の生化学分子として利用できるものを見出し、それを用いた超並列コンピューティング技術を確立することが望ましい。
【００１４】
それゆえに本発明の目的は、ＤＮＡ等以外の生化学分子を用いて超並列コンピューティングを可能とする方法を提供することである。
【課題を解決するための手段】
【００１５】
本発明の第１の局面に係るポルフィリン金属錯体を用いた分子コンピューティング方法は、複数種類のポルフィリン金属錯体のシーケンスにより、解に対する制約を有する所与の組合せ問題中の組合せ要素を符号化するステップと、符号化するステップにより得られた符号に対応するポルフィリン金属錯体のシーケンスの集合を準備するステップと、ポルフィリン金属錯体のシーケンスの集合を反応槽に投入し自己組織化させるステップと、反応槽中に自己組織化により得られた構造体中で、所与の組合せ問題の制約を充足するものを選択するステップと、選択するステップで得られた構造体を構成するポルフィリン金属錯体のシーケンスの符号を解読することにより、所与の組合せ問題に対する解答を得るステップとを含む。
【００１６】
所与の組合せ問題中の組合せ要素を、複数種類のポルフィリン金属錯体のシーケンスを用いて符号化する。これらシーケンスを反応槽中で自己組織化させることにより、ポルフィリン金属錯体のシーケンスの構造体を得て、その中から組合せ問題の制約を充足するものを選択する。こうして得られたポルフィリン金属錯体のシーケンスの構造体中に含まれるポルフィリン金属錯体のシーケンスにより表される符号を解読することにより、所与の組合せ問題に対する解答が得られる。反応槽中における自己組織化は、多数のポルフィリン金属錯体のシーケンスの間で並列的に行なわれるので、組合せを求める計算が並列化され、非常に多数の組合せの可能性を含む組合せ問題を所与の時間内に解くことができる。その結果、ＤＮＡ等以外の生化学分子であるポルフィリン金属錯体を用いて超並列コンピューティングを可能とする方法を提供することができる。
【００１７】
好ましくは、複数種類のポルフィリン金属錯体は、互いに異なる金属と錯体を形成したポルフィリン錯体を含む。
【００１８】
ポルフィリン金属錯体に含まれる金属は互いに区別できる。従って、それら金属を含むポルフィリン錯体のシーケンスを用いると、組合せ要素を符号化することと、ポルフィリン金属錯体のシーケンスから組合せ要素を復号化することとができる。
【００１９】
より好ましくは、符号化するステップは、複数種類のポルフィリン金属錯体のシーケンスにより、組合せ問題中の第１の種類の組合せ要素を符号化するステップと、第１の種類の組合せ要素の組合せの内、制約に従う組合せを抽出するステップと、抽出するステップで抽出された組合せを実現するように、ポルフィリン金属錯体のシーケンスを互いに連結するための第２の種類の組合せ要素を構成するポルフィリン金属錯体を定めるステップとを含む。準備するステップは、第１の種類の組合せ要素を符号化するポルフィリン金属錯体のシーケンスの集合と、定めるステップで定められた第２の種類の組合せ要素を構成するポルフィリン金属錯体の集合とを準備するステップを含む。
【００２０】
組合せ問題中の第１の種類の組合せ要素を符号化し、さらに問題の制約に従って、これら第１の種類の組合せ要素の組合せ方を定め、そうした組合せを実現するような第２の種類の組合せ要素を構成するポルフィリン金属錯体を定める。これらを定めることにより、例えばＨＰＰ問題のようにグラフのノードを符号化するとともに、それらを結ぶエッジを分子コンピューティングに組込むことができ、ＨＰＰのような組合せ問題を解くことができる。
【００２１】
本発明の第２の局面に係るポルフィリン金属錯体を用いた分子コンピューティング装置は、複数種類のポルフィリン金属錯体のシーケンスにより、解に対する制約を有する所与の組合せ問題中の組合せ要素を符号化する符号化装置と、符号化装置により得られた符号に対応するポルフィリン金属錯体のシーケンスの集合を作成するポルフィリン金属錯体シーケンス作成装置と、ポルフィリン金属錯体のシーケンスの集合が投入される反応槽と、反応槽中に、ポルフィリン金属錯体のシーケンスの集合における自己組織化により得られた構造体中で、所与の組合せ問題の制約を充足するものを選択する選択装置と、選択装置で得られた構造体を構成するポルフィリン金属錯体のシーケンスの符号を解読することにより、所与の組合せ問題に対する解答を得るポルフィリン金属錯体シーケンス解読装置とを含む。
【００２２】
好ましくは、複数種類のポルフィリン金属錯体は、互いに異なる金属と錯体を形成したポルフィリン錯体を含む。
【００２３】
より好ましくは、符号化装置は、複数種類のポルフィリン金属錯体のシーケンスにより、組合せ問題中の第１の種類の組合せ要素を符号化するための手段と、第１の種類の組合せ要素の内、制約に従う組合せを抽出するための手段と、抽出するための手段により抽出された組合せを実現するように、ポルフィリン金属錯体のシーケンスを互いに連結するための第２の種類の組合せ要素を構成するポルフィリン金属錯体を定めるための手段とを含む。ポルフィリン金属錯体シーケンス作成装置は、第１の種類の組合せを符号化するポルフィリン金属錯体のシーケンスの集合と、第２の種類の組合せ要素を構成するポルフィリン金属錯体の集合とを準備するための手段を含む。
【００２４】
本発明の第３の局面に係るポルフィリン金属錯体を用いた分子コンピューティング方法は、解に対する制約を有する所与の組合せ問題に応じて選択される複数種類のポルフィリン金属錯体を用い、当該複数種類のポルフィリン金属錯体により形成されるシーケンスの間での自己組織化により得られる構造体から制約を充足するものを選択することより、組合せ問題に対する解を超並列的に算出することを特徴とする。
【発明を実施するための最良の形態】
【００２５】
生化学上で重要な物質に、ポルフィリンがある。ポルフィリンとは、４つのピロール環がα位置で４つのメチン基と交互に結合した構造を持つ、大環状化合物とその誘導体とをいう。ポルフィリン自体は天然には存在しないが、その誘導体は金属錯体として天然に見出される。代表的なものに、鉄との錯体であるヘモグロビン、マグネシウムとの錯体であるクロロフィル等がある。以下、このように金属との錯体を形成可能なポルフィリン誘導体を単にポルフィリンと呼ぶ。
【００２６】
ポルフィリンは様々な金属との間で錯体を作る。例えば鉄（Ｆｅ）、亜鉛（Ｚｎ）、マグネシウム（Ｍｇ）、マンガン（Ｍｎ）、銅（Ｃｕ）等との錯体が代表的なものである。またポルフィリン錯体は自己組織化と呼ばれる性質を持ち、互いに連結してナノワイア状構造体を形成することでも知られている。この場合の自己組織化は、ポルフィリン間の何らかのメカニズムに基づく分子構造認識による自発的な集合体生成によるものと思われる。ポルフィリン錯体中の金属は、こうした構造体の骨格形成を担っていると考えられる。
【００２７】
一方、分子構造中の金属を同定する技術が進み、ポルフィリン錯体中の金属についても同定することが可能になっている。従って、自己組織化により得られた構造体中で、どのポルフィリン金属錯体中にどの金属が含まれているかを確認することができる。
【００２８】
このようなポルフィリンの性質を利用すると、ポルフィリン構造体をＤＮＡコンピューティングにおけるＤＮＡと同様に扱うことができる。もちろん、ポルフィリン構造体とＤＮＡとの性質の相違を考慮する必要がある。そこで、以下の実施の形態では、ポルフィリン金属錯体を用いて、エイデルマンと同様にＨＰＰを解くための分子コンピューティング方法について述べる。
【００２９】
図１に、エイデルマンが解いたのと同じハミルトン経路問題を与えるグラフを示す。図１を参照して、このグラフは有向グラフであって、０から６までの７つのノードと、これら７つのノードを結ぶ有向エッジとを含む。７つのノードはＨＰＰ問題における「都市」に対応し、有向エッジはこれら都市を結ぶ方向付きの経路に対応する。
【００３０】
エイデルマンが解いたＨＰＰ問題は、図１に示すグラフにおいて、都市０を始点、都市６を終点とする経路であって、全ての都市を一度だけ通るような経路を求める、という問題である。
【００３１】
図１に示す問題の解としてエイデルマンがＤＮＡコンピューティングにより得た経路を図２に示す。図２において、解を構成するエッジを実線で示し、解を構成しないエッジを点線で示す。図２を参照して、このグラフにおける解は、都市０→１→２→３→４→５→６という経路である。
【００３２】
以下に述べる本実施の形態では、この問題をポルフィリン錯体を用いて解く。
【００３３】
＜構成＞
図３に、本実施の形態による分子コンピューティングを用いてＨＰＰ問題を解く際の全体システムの構成を示す。図３を参照して、本実施の形態では３種類のポルフィリン金属錯体を用いる。ただし、ポルフィリン自体が互いに同一である必要はなく、種々のポルフィリン誘導体を用いることができる。
【００３４】
本実施の形態では、ポルフィリン鉄錯体２０と、ポルフィリン亜鉛錯体２２と、ポルフィリン銅錯体３２とを用いる。まず、ＨＰＰ問題である問題２６が与えられると、この問題２６に基づき、ポルフィリン鉄錯体２０とポルフィリン亜鉛錯体２２とを用いてポルフィリンのナノワイアを形成することにより、ポルフィリンナノワイアの集合３０で各都市を符号化する。すなわち、このナノワイアはポルフィリン鉄錯体２０及びポルフィリン亜鉛錯体２２からなるシーケンスを含み、そのシーケンス中のポルフィリン鉄錯体２０及びポルフィリン亜鉛錯体２２の配列により、問題２６の組合せ要素である各都市の符号を表す。符号化の例については後述する。また形成されたナノワイアの各々には、各都市を表すラベル２４を付してもよい。
【００３５】
各都市の符号化方法について図４を参照して説明する。図４を参照して、本実施の形態では、ナノワイアを構成するポルフィリン金属錯体に含まれる金属の種類により、各ポルフィリン金属錯体に０又は１の２値のいずれかの値を割当てる。より具体的には、ポルフィリン鉄錯体には１、ポルフィリン亜鉛錯体には０を、それぞれ割当てる。ポルフィリン金属錯体からなるナノワイアは直鎖状に並んだ複数のポルフィリン金属錯体を含む。従って先頭から順にポルフィリン金属錯体に含まれる金属を調べることにより、このナノワイアに割当てられた符号を調べることができる。又はラベルを見ることにより、符号を判定するようにしてもよい。
【００３６】
例えば図４（Ａ）に示す例では、先頭から５番目までのポルフィリン金属錯体の金属は鉄、鉄、鉄、亜鉛、亜鉛である。従ってこのナノワイアに割当てられた符号は「１１１００…」となる（６番目以降は省略。以下同様である。）。同様に図４（Ｂ）に示すナノワイアに割当てられた符号は「１０１００…」となる。
【００３７】
このようにして、問題２６に従い、各都市に所定長で各桁が２値の符号を割当て、当該符号に対応するナノワイアをポルフィリン鉄錯体２０及びポルフィリン亜鉛錯体２２を用いて生成する。
【００３８】
次に、問題２６において与えられている経路（エッジ）を実現するために、問題で認められている経路を抽出し、その経路に応じた「都市−エッジ−都市」の形式の組合せを調べる。すなわち、問題の制約に従う経路のみを、問題２６の第２の組合せ要素として抽出する。そして、そうした経路を実現するために、所定のナノワイアを連結する機能を持つポルフィリン銅錯体３２を準備する。このポルフィリン銅錯体３２はエッジの役割を果たし、選択された組合せの二つのナノワイアを自己組織化により連結する。その結果、この分子コンピューティングシステムの計算部本体への入力となるナノワイアとエッジとの集合３４が得られる。
【００３９】
ナノワイアとエッジとの集合３４を反応槽４２に投入し、さらにポルフィリン金属錯体の自己組織化を助けるための酵素４０を反応槽４２に投入する。この結果、ナノワイア及びエッジを構成するポルフィリン金属錯体が自己組織化によりポルフィリン銅錯体を仲立ちとして互いに連結され、様々な長さでかつ様々なポルフィリン金属錯体の配列からなる多数のナノワイア構造体からなる集合５０が得られる。
【００４０】
こうして得られたナノワイア構造体からなる集合５０から、問題２６により規定される条件に合致するものを選択する処理５２を行なう。例えば先頭のナノワイアがＨＰＰの先頭都市と一致し、最後のナノワイアがＨＰＰの最終都市と一致するもの、かつナノワイア構造体を構成するナノワイアの数が問題２６のグラフのノード数と一致するもの、かつナノワイア構造体を構成するナノワイアが互いに全て異なっているもの、をこの処理で選択する。
【００４１】
こうして最後に得られたナノワイア構造体について、それを形成する各ナノワイアの符号を調べる。各ナノワイアの符号は、当該ナノワイアを構成するポルフィリン金属錯体の金属が鉄か亜鉛かを調べることにより特定できる。こうして、ナノワイア構造体に含まれるナノワイアにより表される都市のシーケンスが判定できると、それがＨＰＰの解５４となる経路を表している。
【００４２】
＜動作＞
以上説明した分子コンピューティングシステムは以下のように動作する。図５に、本実施の形態に係る分子コンピューティングシステムにより行なわれる一連の動作をフローチャート形式で示す。このフローチャートはプログラム構造を表しているものではない。
【００４３】
まず、ステップ８０で、ポルフィリン鉄錯体２０及びポルフィリン亜鉛錯体２２を準備する。これは前述したとおりＨＰＰの都市を符号化するために用いられる。
【００４４】
ステップ８２で、問題２６に応じて、問題となるグラフのノード（都市）を、ポルフィリンナノワイアで符号化する。実際には、ここではポルフィリン鉄錯体２０及びポルフィリン亜鉛錯体２２を符号にあわせて連結したシーケンスを生成し、都市を表すナノワイアを形成する。
【００４５】
ステップ８４で、問題２６に応じて、ノード（都市）間を接続するエッジ（経路）の組合せを調べ、そうした組合せを実現するエッジの役割を果たすポルフィリン銅錯体３２を準備する。
【００４６】
ステップ８６で、ステップ８２及びステップ８４で生成されたナノワイアの集合とポルフィリン銅錯体３２の集合を反応槽４２に投入する。このとき、ポルフィリン金属錯体の自己組織化を促進する酵素を一緒に反応槽４２に投入する。この結果、反応槽４２中ではナノワイアを構成するポルフィリン金属錯体相互の間の自発的な集合体生成（自己組織化）により、ナノワイアがポルフィリン銅錯体で直鎖状に連結され、ナノワイア構造体が形成される。
【００４７】
ここで形成されるナノワイア構造体は、自己組織化を用いるため、その長さもナノワイア構造体を構成するナノワイアの種類も、ステップ８２で生成されたものでありかつステップ８４で生成されたエッジによる連結制約を受けること以外、全く制約がない。ナノワイア構造体を構成するナノワイアの数にも制約はない。その結果、ステップ８６の処理によって、様々な長さのナノワイア構造体が得られる。それらを構成するナノワイアは、ステップ８２で準備されたものの一つではあるが、その結合順序は様々である。
【００４８】
ステップ８８では、長さが問題２６のグラフを構成するノード（都市）数と一致するナノワイア構造体が選択される。ＨＰＰの解では、得られる経路に含まれる都市の数は必ずグラフのノード数と一致するからである。
【００４９】
ステップ９０では、ステップ８８で選択されたナノワイア構造体のうち、先頭のナノワイアが問題２６のグラフの先頭都市に、最後のナノワイアが問題２６のグラフの最終都市に、それぞれ一致するもののみを選択する。ＨＰＰの解では、得られる経路は特定の都市を先頭とし、特定の都市を最後とするからである。
【００５０】
最後に、ステップ９２で、ステップ９０の処理で得られたナノワイア構造体のうち、ナノワイア構造体を構成するナノワイアが互いに異なるもののみを選択する。ＨＰＰの解では、一つの都市を複数回通ることができないためである。
【００５１】
以上の処理を行なった後、残ったナノワイアの構造体が、問題２６の解を与える。ステップ９４では、この残ったナノワイア構造体を構成するナノワイアに含まれるポルフィリン金属錯体の金属を調べることでナノワイアの符号を解読する。さらに解読されたナノワイアの符号を、ナノワイアの構造体におけるナノワイアの順序に従って配列することで問題２６に対する最終的な解が得られる。
【００５２】
以上のとおり、本実施の形態に係る分子コンピューティング方法によれば、ＤＮＡ等ではなく、ポルフィリン金属錯体を用いることで、ＨＰＰを解くことができる。この処理では、計算にポルフィリン金属錯体の自己組織化を用いるので、反応槽における分子コンピューティング処理は超並列的に行なわれる。その結果、エイデルマンによるＤＮＡコンピューティングと同様、ＮＰ完全問題を有限時間内で解くことが可能になる。計算に必要な資源は、ポルフィリンと金属とであり、安価でかつ容易に準備することができる。
【００５３】
＜変形例＞
なお、上記実施の形態では、鉄錯体と亜鉛錯体とを用いて各都市を２値符号化した。しかし本発明はそのような実施の形態には限定されない。例えば３種類以上の金属錯体を用い、３値以上の符号で都市を符号化してもよい。用いる金属としては、前述したもの以外でもよく、ポルフィリンと錯体を作成しやすいものを用いるのが望ましい。
【００５４】
さらに、上記実施の形態では、ＨＰＰ問題の解法に本発明の分子コンピューティングを用いている。しかし本発明はそのような実施の形態には限定されず、具体的な問題に合わせて何を符号化し、制約としてどのようなものを抽出するかを決定し、それらに対応するポルフィリン金属錯体またはそのシーケンスの構成を決定すればよい。なお、自己組織化による解の候補の生成については、問題において解の探索空間の最も広い部分に適用すれば、その部分の探索が並列的に行なわれ、効果的に分子コンピューティングの超並列性を生かすことできる。
【００５５】
今回開示された実施の形態は単に例示であって、本発明が上記した実施の形態のみに制限されるわけではない。本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味及び範囲内でのすべての変更を含む。
【産業上の利用可能性】
【００５６】
この発明は、生化学反応を利用して超並列コンピューティングを行なう分子コンピュータの製造及び分子コンピューティング方法に利用することができる。
【図面の簡単な説明】
【００５７】
【図１】ハミルトン経路問題を示すグラフである。
【図２】図１に示すハミルトン経路問題の解を示すグラフである。
【図３】本発明の一実施の形態に係る分子コンピューティングシステムの概略構成を示す図である。
【図４】本発明の一実施の形態におけるノードの符号化方法を示す図である。
【図５】本発明の一実施の形態に係る分子コンピューティングシステムの動作手順を示すフローチャートである。
【符号の説明】
【００５８】
２０  ポルフィリン鉄錯体
２２  ポルフィリン亜鉛錯体
２４  ラベル
２６  問題
３０  ポルフィリンナノワイアの集合
３２  ポルフィリン銅錯体
３４  ナノワイアとエッジとの集合
４０  酵素
４２  反応槽
５０  ナノワイア構造体からなる集合
【図１】
2006244103.tif 000003
【図２】
2006244103.tif 000004
【図３】
2006244103.tif 000005
【図４】
2006244103.tif 000006
【図５】
2006244103.tif 000007