(57)【要約】ＤＮＡを利用して計算を実行するＤＮＡコンピュータは、解くべき問題を複数の部分問題に分割する分割部と、前記複数の部分問題の解に対応するＤＮＡ配列を組み合わせることで、前記問題の解に対応するＤＮＡ配列を求める演算部とを備えるように構成されている。
2004068398.tif 000002
【特許請求の範囲】
【請求項１】
ＤＮＡを利用して計算を実行するＤＮＡコンピュータであって、
解くべき問題を複数の部分問題に分割する分割手段と、
該複数の部分問題の解に対応するＤＮＡ配列を組み合わせることで、該問題の解に対応するＤＮＡ配列を求める演算手段とを備えたことを特徴とする、ＤＮＡコンピュータ。
【請求項２】
前記ＤＮＡコンピュータのパラメータを、遺伝的アルゴリズムにより最適化する最適化手段を更に備えたことを特徴とする、請求の範囲第１項記載のＤＮＡコンピュータ。
【請求項３】
前記パラメータは、前記演算手段が前記部分問題を解く計算順序であることを特徴とする、請求の範囲第２項記載のＤＮＡコンピュータ。
【請求項４】
前記遺伝的アルゴリズムの染色体の適応度は、前記ＤＮＡコンピュータによる前記問題の解の正解率、前記問題の解を計算するのに必要な計算時間、前記問題の解を計算するのに必要なＤＮＡ分子量及び前記解のＧＣ含量のうち、少なくとも１つに基づいていることを特徴とする、請求の範囲第２項又は第３項記載のＤＮＡコンピュータ。
【請求項５】
前記分割手段は、部分問題Ｐｋの解を部分問題Ｐｋ＋１を解く際の入力の一部として使用する直列型分割法を用いることを特徴とする、請求の範囲第１項〜第４項のいずれか１項記載のＤＮＡコンピュータ。
【請求項６】
前記演算手段は、前記複数の部分問題の解のコード法として、どの部分問題であるかを示すＤＮＡ配列と解を表すＤＮＡ配列の組み合わせで解を表現することを特徴とする、請求の範囲第５項記載のＤＮＡコンピュータ。
【請求項７】
前記演算手段は、各部分問題の解を表すＤＮＡ配列を中央に置き、その両側にどの部分問題の解であるかを示すＤＮＡ配列を置くことを特徴とする、請求の範囲第６項記載のＤＮＡコンピュータ。
【請求項８】
前記演算手段は、前記複数の部分問題の解を表すＤＮＡ配列から問題の解を表すＤＮＡ配列を合成するために、該複数の部分問題を表すＤＮＡ配列の組み合わせをプライマーとして利用することを特徴とする、請求の範囲第５項記載のＤＮＡコンピュータ。
【請求項９】
前記分割手段は、問題を解き易い順序で部分問題に分解することを特徴とする、請求の範囲第５項記載のＤＮＡコンピュータ。
【請求項１０】
前記演算手段は、前記複数の部分問題を解く順序を入れ換えることを特徴とする、請求の範囲第５項記載のＤＮＡコンピュータ。
【請求項１１】
前記分割手段は、各部分問題の解が他の１以上の部分問題を解く際の入力の一部として使用され、且つ、前記複数の部分問題をノードとしてこれらのノード間をアークとするグラフがレイヤードネットワークで表現されるレイヤードネットワーク型分割法を用いることを特徴とする、請求の範囲第１項〜第４項のいずれか１項記載のＤＮＡコンピュータ。
【請求項１２】
前記演算手段は、前記複数の部分問題の解のコード法として、前記レイヤードネットワークのどのレイヤのどの部分問題であるかを示すＤＮＡ配列と解を表すＤＮＡ配列の組み合わせで解を表現することを特徴とする、請求の範囲第１１項記載のＤＮＡコンピュータ。
【請求項１３】
前記演算手段は、各部分問題の解を表すＤＮＡ配列を中央に置き、その両側に前記レイヤードネットワークのどのレイヤのどの部分問題の解であるかを示すＤＮＡ配列を置くことを特徴とする、請求の範囲第１２項記載のＤＮＡコンピュータ。
【請求項１４】
前記演算手段は、前記複数の部分問題の解を表すＤＮＡ配列から問題の解を表すＤＮＡ配列を合成するために、該複数の部分問題を表すＤＮＡ配列の組み合わせをプライマーとして利用することを特徴とする、請求の範囲第１１項記載のＤＮＡコンピュータ。
【請求項１５】
コンピュータシミュレーションにより各部分問題の解が前記問題の解の一部分になる可能性があるか否かを判定する判定手段を更に備え、
前記演算手段は、各部分問題の解が前記問題の解の一部分になる可能性がある場合には演算を行い、可能性がない場合には演算を行わないことを特徴とする、請求の範囲第１項〜第１４項のいずれか１項記載のＤＮＡコンピュータ。
【請求項１６】
最終的に破綻することが前記コンピュータシミュレーションにより判定された部分問題の解より１つ前の部分問題の解を、別の部分問題の解を求める時に利用可能に保存する保存手段を更に備えたことを特徴とする、請求の範囲第１項〜第１５項のいずれか１項記載のＤＮＡコンピュータ。
【請求項１７】
ＤＮＡを利用して計算を実行するＤＮＡコンピュータを用いた計算方法であって、
解くべき問題を複数の部分問題に分割する分割ステップと、
該複数の部分問題の解に対応するＤＮＡ配列を組み合わせることで、該問題の解に対応するＤＮＡ配列を求める演算ステップとを含むことを特徴とする、ＤＮＡコンピュータを用いた計算方法。
【請求項１８】
前記ＤＮＡコンピュータのパラメータを、遺伝的アルゴリズムにより最適化する最適化ステップを更に含むことを特徴とする、請求の範囲第１７項記載のＤＮＡコンピュータを用いた計算方法。
【請求項１９】
前記分割ステップは、部分問題Ｐｋの解を部分問題Ｐｋ＋１を解く際の入力の一部として使用する直列型分割法を用いることを特徴とする、請求の範囲第１７項又は第１８項記載のＤＮＡコンピュータを用いた計算方法。
【請求項２０】
前記分割ステップは、各部分問題の解が他の１以上の部分問題を解く際の入力の一部として使用され、且つ、前記複数の部分問題をノードとしてこれらのノード間をアークとするグラフがレイヤードネットワークで表現されるレイヤードネットワーク型分割法を用いることを特徴とする、請求の範囲第１７項又は１８項記載のＤＮＡコンピュータを用いた計算方法。
【発明の詳細な説明】
【技術分野】  本発明は、ＤＮＡコンピュータ及びそれを用いた計算方法に係り、特に複雑な計算に適したＤＮＡコンピュータ及びそれを用いた計算方法に関する。
ＤＮＡコンピュータは、解の探索空間が非常に大きな最適化問題等をＤＮＡの分子反応を利用して高速に解くコンピュータである。ＤＮＡコンピュータのハードウェアは、ＤＮＡを構成するヌクレオチドと呼ばれる分子である。ＤＮＡに、ＤＮＡコンピュータの基本演算を施して得られるＤＮＡのヌクレオチド配列が、ＤＮＡコンピュータの出力となる。この出力を表すＤＮＡのヌクレオチド配列は、ヌクレオチド配列のコピーを大量に作成するポリメラーゼ連鎖反応（ＰＣＲ）を使用して増幅する。ヌクレオチドの分子量の違いを利用してＤＮＡのヌクレオチド配列を電気泳動法により決定することで、ＤＮＡコンピュータの出力が読み取られる。
【背景技術】  １．１  遺伝的アルゴリズム：
遺伝的アルゴリズムとは、例えばＤ．Ｇｏｌｄｂｅｒｇ，″Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｉｎ  Ｓｅａｒｃｈ，Ｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ″，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，１９８９等で説明されているように、生物の遺伝の機構を模倣して工学的に応用する技術である。
生物の進化の過程では、既存の個体（親）から新たな個体（子）が生まれる際に、個体の持つ染色体同士の交叉、染色体上の遺伝子の突然変異等が起こる。環境に適応しない個体は淘汰され、環境により適応した個体が生き延びて新たな親となり、更に新たな子孫を作って行く。
このようにして、環境に適応した個体の集団が生き延びて行く。各個体同士がどの程度環境に適応するかは、染色体（遺伝子の一次元ストリング）により決定される。遺伝的アルゴリズムでは、最適化問題の解候補を遺伝子の一次元ストリングである染色体として表現し、解候補の集団に対して選択（Ｓｅｌｅｃｔｉｏｎ）、自己複製（Ｒｅｐｒｏｄｕｃｔｉｏｎ）、交叉（Ｃｒｏｓｓｏｖｅｒ）、突然変異（Ｍｕｔａｔｉｏｎ）等の操作を繰り返し施すことにより、最適解の探索を行う。図１は、このような遺伝的アルゴリズムの世代の一例を示す図である。
最適化問題の目的関数が環境に相当し、目的関数を最適にするもの程大きい値を取るような適応度関数が染色体に対して定義される。選択（又は自己複製）とは、集団の中で適応度の高い染色体を持つ個体をより高い確率で選択して次世代の親とする操作である。図２は、遺伝的アルゴリズムの選択の一例を示す図である。交叉とは、２つの染色体（親）の一部を互いに入れ換えて新たな個体（子）を作り出す操作である。図３は、遺伝的アルゴリズムの交叉の一例を示す図である。突然変異とは、１つの染色体の一部の遺伝子をランダムに置き換える操作である。図４は、遺伝的アルゴリズムの突然変異の一例を示す図である。
これらの如き操作を繰り返すことにより、適応度（Ｆｉｔｎｅｓｓ）のより高い染色体、即ち、目的関数をより最適化する解が得られる。
１．２  ＤＮＡコンピュータ：
ＤＮＡコンピュータとは、例えばＫｅｖｉｎ  Ｂｏｎｓｏｒ，″Ｈｏｗ  ＤＮＡ  ｃｏｍｐｕｔｅｒ  ｗｉｌｌ  ｗｏｒｋ″，ＷＷＷ，Ａｕｇｕｓｔ，２００２（ｈｔｔｐ：／／ｗｗｗ．ｈｏｗｓｔｕｆｆｗｏｒｋｓ．ｃｏｍ／ｄｎａ−ｃｏｍｐｕｔｅｒ１．ｈｔｍ）等で説明されているように、生物の遺伝情報であるＤＮＡを利用して計算を行うコンピュータである。図５は、ＤＮＡコンピュータの計算処理の一例を示すフローチャートである。同図中、ステップＳ１は、計算処理により解くべき問題をＤＮＡにコード化する。ステップＳ２は、十分な量の解候補のＤＮＡを作成するハイブリダイゼイションを行う。ステップＳ３は、ＤＮＡコンピュータにより、解候補のスクリーニングを行い、解候補から解を選び出す。
ＤＮＡは、デオキシリボ核酸で構成されている。デオキシリボ核酸は、ヌクレオチドから構成されている。ヌクレオチドは、糖、リン酸基及び塩基から構成されている。糖及びリン酸基は、デオキシリボ核酸で共通であるが、塩酸基の違いでアデニン（Ａ）、グアニン（Ｇ）、シトシン（Ｃ）及びチミン（Ｔ）の４種類がある。ヌクレオチドの５’リン酸基と別のヌクレオチドの３’水酸基が結合して一種の共有結合（ホスホジェステル結合）を形成する。新しいヌクレオチドは、ＤＮＡの３’末端に付加される。ヌクレオチドの塩基部分は、他のヌクレオチドの塩基部分と水素結合により結合する。ヌクレオチドの塩基部分の結合の相手には制約があり、ＡとＴ、ＧとＣが塩基対を形成でき、これを相補性と言う。
ＤＮＡコンピュータは、与えられ問題の解候補を４種類のヌクレオチドＡ，Ｔ，Ｇ，Ｃで図６に示すようにコード化する。図６は、有効ハミルンパス問題を解く場合の解候補のコード化の一例を示す図である。このような解候補のコード化は、例えば荻谷昌己及び横森貴、「ＤＮＡコンピュータ」、培風館、２００１等で説明されている。
このようにしてコード化された問題の解候補は、溶液の入った試験管Ｓに注入され、後述する基本演算が施される。基本演算には、「増幅（Ａｍｐｌｉｆｙ）」、「合体（Ｍｅｒｇｅ）」、「分離（Ｇｅｔ）」、「付加（Ａｐｐｅｎｄ）」及び「検知（Ｄｅｔｅｃｔ）」の５つの操作が含まれる。尚、このような基本演算自体は、例えば陶山明、「分子コンピュータの実験」、数理科学、（４４５）；２７−３１、２０００等で説明されている。
「増幅」は、ＤＮＡの入った試験管Ｓ中のコピーを作る操作である。「合体」は、ＤＮＡの入った２つの試験管Ｓ１とＳ２を１つの試験管Ｓ＝Ｓ１∪Ｓ２に合わせる操作である。「分離」は、試験管ＳからヌクレオチドＡ，Ｔ，Ｇ，Ｃの記号列で表現される条件を満足する（或いは、満足しない）ＤＮＡを分離抽出して別の試験管に注入する操作である。「付加」は、試験管ＳのＤＮＡ分子の末端がある条件を満足する場合に指定されたヌクレオチド配列を付加する操作である。「検知」は、試験管Ｓに対して、試験管Ｓが少なくとも１つのＤＮＡを含むと「真」を返し、そうでないと「偽」を返す操作である。
ＤＮＡコンピュータは、上記の如き５つの操作を、解くべき問題に応じて組み合わせることにより、最初に準備されたＤＮＡの解候補から解を求める。このようなＤＮＡコンピュータの計算方法は、例えばＬｅｏｎａｒｄ  Ｍ．Ａｄｌｅｍａｎ，″Ｍｏｌｅｃｕｌａｒ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｓｏｌｕｔｉｏｎｓ  ｔｏ  ｃｏｍｂｉｎａｔｉｏｎａｌ  ｐｒｏｂｌｅｍｓ″，ＳＣＩＥＮＣＥ，２６６（５１８７）；１０２１−１０２４，１９９４等で説明されており、「エードルマンパラダイム（Ａｄｌｅｍａｎ  Ｐａｒａｄｉｇｍ）」と呼ばれる。
図７は、有効ハミルンパス問題を解く場合のスクリーニングの一例を示す図である。同図中、Ｓ１１は問題のコード化（Ｃｏｄｉｎｇ）段階を示し、Ｓ１２はハイブリダイゼイション（Ｈｙｂｒｉｄｉｚａｔｉｏｎ）段階を示し、Ｓ１３はスクリーニング（Ｓｃｒｅｅｎｉｎｇ）段階を示す。
しかし、従来のＤＮＡコンピュータでは、計算が複雑になるにつれて必要となるＤＮＡの量が増大してしまい、計算処理を実際に行うことが困難になると共に、計算ステップ数が非常に多いために解のエラーの発生率が高くなって正確な計算が困難になるという問題があった。
【発明の開示】
本発明は、上記の問題を解決した新規、且つ、有用なＤＮＡコンピュータ及びそれを用いた計算方法を提供することを概括的目的とする。
本発明のより具体的な目的は、計算が複雑になっても必要となるＤＮＡの量が増大せずに計算処理を容易に行うことがきると共に、比較的少ない計算ステップ数で計算処理を行うことで解のエラーの発生率を低く抑えて正確な計算が行えるＤＮＡコンピュータ及びそれを用いた計算方法を提供することにある。
本発明の他の目的は、ＤＮＡを利用して計算を実行するＤＮＡコンピュータであって、解くべき問題を複数の部分問題に分割する分割手段と、該複数の部分問題の解に対応するＤＮＡ配列を組み合わせることで、該問題の解に対応するＤＮＡ配列を求める演算手段とを備えたことを特徴とするＤＮＡコンピュータを提供することにある。本発明になるＤＮＡコンピュータによれば、計算が複雑になっても必要となるＤＮＡの量が増大せずに計算処理を容易に行うことができると共に、比較的少ない計算ステップ数で計算処理を行うことで解のエラーの発生率を低く抑えて正確な計算が行える。
本発明の更に他の目的は、ＤＮＡを利用して計算を実行するＤＮＡコンピュータを用いた計算方法であって、解くべき問題を複数の部分問題に分割する分割ステップと、該複数の部分問題の解に対応するＤＮＡ配列を組み合わせることで、該問題の解に対応するＤＮＡ配列を求める演算ステップとを含むことを特徴とするＤＮＡコンピュータを用いた計算方法を提供することにある。本発明になるＤＮＡコンピュータを用いた計算方法によれば、計算が複雑になっても必要となるＤＮＡの量が増大せずに計算処理を容易に行うことがきると共に、比較的少ない計算ステップ数で計算処理を行うことで解のエラーの発生率を低く抑えて正確な計算が行える。
本発明の更に他の目的及び特長は、以下図面と共に述べる説明より明らかとなろう。
【図面の簡単な説明】  図１は、遺伝的アルゴリズムの世代の一例を示す図、
図２は、遺伝的アルゴリズムの選択の一例を示す図、
図３は、遺伝的アルゴリズムの交叉の一例を示す図、
図４は、遺伝的アルゴリズムの突然変異の一例を示す図、
図５は、ＤＮＡコンピュータの計算処理の一例を示すフローチャート、
図６は、有効ハミルンパス問題を解く場合の解候補のコード化の一例を示す図、
図７は、有効ハミルンパス問題を解く場合のスクリーニングの一例を示す図、
図８は、ＤＮＡコンピュータの構成を示すブロック図、
図９は、直列型分割法で問題を部分問題に分割する場合を説明する図、
図１０は、問題を直列型分割法で部分問題に分割可能な場合のＤＮＡコンピュータの動作を説明する図、
図１１は、レイヤードネットワーク型分割法で問題を部分問題に分割する場合を説明する図、
図１２は、問題をレイヤードネットワーク型分割法で部分問題に分割可能な場合のＤＮＡコンピュータの動作を説明する図、
図１３は、遺伝的アルゴリズムによるＤＮＡコンピュータの制御を説明する図、
図１４は、遺伝的アルゴリズムによるＤＮＡコンピュータの制御を説明するフローチャート、
図１５は、組み合わせるオリゴヌクレオチド（ＤＮＡの断片）の長さとＧＣ含量の関係を示す図、
図１６は、制約付き解候補Ｄ０から進化的方法を利用して作られる制約付き解候補を説明する図、
図１７は、制約付き解候補Ｄ１から進化的方法を利用して作られる制約付き解候補を説明する図、
図１８は、制約付き解候補Ｄ２から進化的方法を利用して作られる制約付き解候補を説明する図、
図１９は、制約付き解候補Ｄ３から進化的方法を利用して作られる制約付き解候補を説明する図、
図２０は、制約付き解候補Ｄ４から進化的方法を利用して作られる制約付き解候補を説明する図、
図２１は、進化的方法を用いて無駄な演算を省略する方法を説明するフローチャート、
図２２は、進化的方法を用いて前の計算結果を参照して計算を高速化する方法を説明するフローチャート、
図２３は、解候補のＧＣ含量を説明する図、
図２４は、有効ハミルトンパス問題を示す有効グラフ、
図２５は、図２４に示す問題の部分問題を示す図、
図２６は、図２５に示す部分問題を含む部分問題を示す図、
図２７は、図２６に示す部分問題を含む部分問題を示す図、
図２８は、図２７に示す部分問題を含む部分問題を示す図、
図２９は、図２８に示す部分問題を含む部分問題を示す図、
図３０は、有効ハミルトンパス問題のノードのコード法を示す図、
図３１は、有効ハミルトンパス問題の有効辺のコード法を示す図である。
【発明を実施するための最良の形態】  以下、本発明になるＤＮＡコンピュータ及びそれを用いた計算方法の実施例を、図８以降と共に説明する。先ず、本実施例の動作原理を説明する。
２．１  動作原理
生物は、進化の過程で獲得した遺伝情報を捨て去ることなく保持している。このため、例えば生物の体節構造に関係した遺伝子のＤＮＡ配列は、広範囲の種に渡って類似している。原核生物から真核生物、単細胞生物から哺乳類へ進化するにつれてＤＮＡ配列の長さが増加してきた理由の１つは、このような遺伝情報の蓄積である。遺伝情報を問題に対する解とみなすと、生物のＤＮＡは進化の過程で解決してきた問題の解の集まりと解釈することができる。生物自体が解決しようとしている究極の問題自体は、自己増殖以外は現在のところは不明であるが、ＤＮＡコンピュータは、このようなプロセスを利用して問題を解くことができるコンピュータである。
ＤＮＡコンピュータが複雑な問題を解く場合には、必要となるＤＮＡの量が増大してしまい、計算処理を実際に行うことが困難になってしまう。このため、本実施例では、ＤＮＡコンピュータにより計算を実行したい問題が、部分問題から構成されていると考え、この部分問題の解を組み合わせることで、問題全体の解を得る。このようにして、進化的手法をＤＮＡコンピュータで使用することで、必要となるＤＮＡの量が増大することを抑制し、計算速度を向上させることができる。
又、ＤＮＡコンピュータのパラメータを後述する遺伝的アルゴリズムで調整することにより、ＤＮＡコンピュータが求める解のエラー発生率を低下させる。この場合、ＤＮＡコンピュータで計算を実行するべき問題が部分問題から構成されているものとすると、この部分問題の解を組み合わせて問題全体の解が得られる。問題全体の解は、論理的には部分問題を解く順番に依存しないものとする。しかし、ＤＮＡコンピュータの場合、部分問題を解く順番によってＤＮＡ配列が異なるため、予期できないエラーが発生する可能性がある。そこで、本実施例では、部分問題の計算順序といったＤＮＡコンピュータのパラメータを、遺伝的アルゴリズムにより最適化することで、解のエラー発生率を低下させる。
２．１  ＤＮＡコンピュータの構成
計算処理により解くべき問題をＤＮＡにコード化する際に用いるコード法は、１つの変数ｘｉとその値を表すＤＮＡの４種類のヌクレオチド（アデニン（Ａ）、グアニン（Ｇ）、シトシン（Ｃ）及びチミン（Ｔ））の組み合わせを使用する。即ち、解くべき問題は、変数を表すヌクレオチド配列と、変数の値（例えば「真」又は「偽」）を表すヌクレオチド配列とにコード化される。
このようにしてコード化された問題の解候補は、溶液の入った試験管Ｓに注入され、基本演算が施される。基本演算には、「増幅（Ａｍｐｌｉｆｙ）」、「合体（Ｍｅｒｇｅ）」、「分離（Ｇｅｔ）」、「付加（Ａｐｐｅｎｄ）」及び「検知（Ｄｅｔｅｃｔ）」の５つの操作が含まれる。
「増幅」は、ａｍｐｌｉｆｙ（Ｓ，Ｓ１，．．．，Ｓｉ，．．．）で表され、試験管Ｓ中のＤＮＡである条件を満足するＤＮＡの部分集合を増幅して別の試験管Ｓｉに分注する操作である。
「合体」は、Ｓ＝ｍｅｒｇｅ（Ｓ１，Ｓ２，．．．）で表され、ＤＮＡの入った２つ以上の試験管Ｓ１，Ｓ２，．．．を１つの試験管Ｓに合わせる操作である。
「分離」は、Ｓ１＝ｇｅｔ（Ｓ，ｃｏｎｄｉｔｉｏｎ）で表され、試験管ＳからヌクレオチドＡ，Ｔ，Ｇ，Ｃの記号列で表現されるある条件を満足する（或いは、満足しない）ＤＮＡを分離抽出して別の試験管Ｓ１に注入する操作である。
「付加」は、Ｓ１＝ａｐｐｅｎｄ（Ｓ，ｘ）で表され、試験管ＳのＤＮＡ分子の末端がある条件を満足する場合に指定されたヌクレオチド配列を付加する操作である。ここで、ｘは付加するヌクレオチド配列を示し、Ｓ１は試験管Ｓ中のＤＮＡにヌクレオチド配列ｘを付加したＤＮＡの集合（試験管）を示す。
「検知」は、試験管ＳにＤＮＡがあるか否かを確認する操作である。つまり、「検知」は、試験管Ｓに対して、試験管Ｓが少なくとも１つのＤＮＡを含むと「真」を返し、そうでないと「偽」を返す操作である。
ＤＮＡコンピュータは、上記の如き５つの操作を、解くべき問題に応じて組み合わせることにより、最初に準備されたＤＮＡの解候補から解を求める。
２．３  ＤＮＡコンピュータの制御法（アルゴリズム）
生物が単純な原核生物から真核生物、単細胞生物から哺乳類へ進化するような長い時間スケールで進化を捉えると、ＤＮＡ配列の長さはより長くなる傾向がある。ＤＮＡ配列の長さが増加してきた理由の１つは、このような遺伝情報の蓄積である。上記の如く、遺伝情報を問題に対する解とみなすと、生物のＤＮＡは進化の過程で解決してきた問題の解の集まりと解釈することができる。そこで、本実施例では、同様にして部分問題の解を一次元配列で表現し、元の問題の解又は解候補を、部分問題の解を結合させて元の問題の解を検索することで求める、進化的手法を用いる。
図８は、ＤＮＡコンピュータ１１の構成を示すブロック図である。同図中、ＤＮＡ分子化学反応部１は、溶液中にＤＮＡが注入された試験管からなる。化学反応制御部２は、ＤＮＡ分子化学反応部１への酵素、プライマー（ＤＮＡ断片）等の注入を行う。ＤＮＡエンコード部３は、ＤＮＡコンピュータ１１のセットアップに必要なＤＮＡを準備する。ＤＮＡコンピュータ制御部４は、ＤＮＡコンピュータ１１の基本演算を利用したプログラムを保持し、化学反応制御部２及びＤＮＡ分子反応部１に操作を指示する汎用のコンピュータからなる。検知部５は、ＤＮＡコンピュータ１１の出力（ＤＮＡ配列）を、電気泳動法等により読み取る装置からなる。
本実施例では、上記進化的手法を図８に示すＤＮＡコンピュータ１１に適用して、部分問題の解を対応するヌクレオチド配列として保存し、次の部分問題を解く際に利用する。この時、コンピュータシミュレーションによって部分問題の解が元の問題の解の一部分になる可能性があるか否かを判定し、可能性がある場合にはＤＮＡコンピュータ１１の演算を行い、可能性がない場合にはＤＮＡコンピュータ１１の演算を行わない。又、最終的に破綻することがコンピュータシミュレーションによって明らかになった部分問題の解より１つ前の部分問題の解は、破棄せずに保存しておく。これは、別の部分問題の解を求める時に利用可能であれば利用して、効率的に解を求めるためである。
次に、ある問題Ｐの部分問題Ｐｋが定義できる場合を考える。部分問題Ｐｋの制約付き解候補Ｃｋとは、「Ｃｋが部分問題Ｐｋの解である」、或いは、「Ｃｋが問題Ｐの解の一部分ではないことを明示的に示せない（問題Ｐの解の一部分である可能性がある）」場合として定義する。ＤＮＡコンピュータ１１の場合、解は常にヌクレオチド配列（Ａ，Ｔ，Ｇ，Ｃの一次元配列）として表されるので、部分問題Ｐｋの任意の制約付き解候補Ｃｋが部分問題Ｐｋ＋１のある制約付き候補Ｃｋ＋１の一部分である時、Ｃｋ＋１がＣｋを含むものとし、この時の部分問題Ｐｋ＋１は部分問題Ｐｋを含むものとする。
部分問題Ｐｋのある制約付き解候補から導かれる部分問題Ｐｋ＋１の制約付き解候補が実際の解候補になるか否かをコンピュータシミュレーションで明確にすることで、部分問題Ｐｋ＋１の制約付き解候補が実際の解候補とならない場合にはＤＮＡコンピュータ１１の演算を行わないことで、ＤＮＡコンピュータ１１の計算効率を向上することができる。
又、部分問題Ｐｋの解候補γｋ＋１（制約付き解候補でなくても可）が問題Ｐの解にならないことがコンピュータシミュレーションにより明確になった場合、１つ前の部分問題Ｐｋの制約付き解候補Ｃｋから解候補γｋ＋１とは異なる解候補を作り部分問題Ｐｋ＋１の制約付き解候補を見つける手法を用いることで、ＤＮＡコンピュータ１１の計算効率を向上することができる。
部分問題Ｐ１，Ｐ２，．．．，ＰＮをこの順番で解くことで得られる制約付き解候補の中から、問題Ｐの制約条件を満足する問題Ｐの解を選択する。このような部分問題の系列では、生物の進化の方法と同様に、部分問題Ｐｉ（ｉ＝２，．．．，Ｎ）は１つ前の部分問題の解候補を使用して解候補を構成する。
２．４  問題の部分問題への分割法
エードルマンパラダイムでは、予め解候補を全て用意しておき、その中から解を選択することで計算時間を短縮する。しかし、大規模な問題では、解候補の総数が非常に大きくなり、現実的な解法ではなくなってしまう。そこで、本実施例では、問題がいくつかの部分問題に分割可能な場合には、ＤＮＡコンピュータ１１で部分問題を順番に解くことにより、大規模な問題に対する現実的な解法を実現する。問題が分割可能な場合に適用できるＤＮＡコンピュータ１１のアルゴリズムには、以下に説明する如き直列型分割法とレイヤードネットワーク型分割法とがある。
２．４．１  直列型分割法：
直列型分割法の場合、部分問題Ｐｋの解が部分問題Ｐｋ＋１を解く際の入力の一部として使用される。ここで、ｋ＝１，２，．．．，Ｎである。このような関係を、部分問題Ｐｋと部分問題Ｐｋ＋１をノードとしてこれらのノード間をアークで結ぶグラフで表現する。図９は、直列型分割法で問題を部分問題に分割する場合を説明する図である。同図は、説明の便宜上、元の問題Ｐが４つの部分問題Ｐ１〜Ｐ４に分割されて、グラフを構成するアークで結ばれる場合を示す。
図１０は、問題を直列型分割法で部分問題に分割可能な場合のＤＮＡコンピュータ１１の動作を説明する図である。同図中、部分問題Ｐ１は、ＤＮＡコンピュータ１１により解かれ、解Ｃ１がＤＮＡコンピュータ１１にフィードバックされる。部分問題Ｐ２は、解Ｃ１を用いてＤＮＡコンピュータ１１により解かれ、解Ｃ２がＤＮＡコンピュータ１１にフィードバックされる。以下同様にして演算が行われ、ＤＮＡコンピュータ１１より解Ｃ４が出力されて演算が終了する。
例えば、部分問題Ｐ１の解をヌクレオチド配列Ｃ１で表すことができるものとする。この場合、ヌクレオチド配列Ｃ１の３’末端に、この解が部分問題Ｐ１の解であることを示すマーカーを付ける。このヌクレオチド配列Ｃ１を使用して、部分問題Ｐ２の解であるヌクレオチド配列Ｃ２を、ヌクレオチド配列Ｃ１に結合させる。ヌクレオチド配列Ｃ２の３’末端には、この解が部分問題Ｐ２の解であることを示すマーカーを付け、以下同様の操作を繰り返す。このようにして、部分問題の解のコード法として、どの部分問題であるかを示すヌクレオチド配列と解を表すヌクレオチド配列の組み合わせで解を表現することができる。又、部分問題の解を表すヌクレオチド配列を中央に置き、その両側にどの部分問題の解であるかを示すヌクレオチド配列を置くことができる。部分問題の解を表すヌクレオチド配列から問題の解を表すヌクレオチド配列を合成するために、部分問題を表すヌクレオチド配列の組み合わせをプライマーとして利用することもできる。
尚、直列型分割法の場合、部分問題を解く順序を入れ換える場合もある。この場合、問題を解き易い順序で部分問題に分解し、解を短時間で求めるようにしても良い。
２．４．２  レイヤードネットワーク型分割法：
レイヤードネットワーク型分割法の場合、部分問題の解が他の１以上の部分問題を解く際の入力の一部として使用され、且つ、部分問題をノードとしてこれらのノード間をアークとするグラフがレイヤードネットワークで表現される。図１１は、レイヤードネットワーク型分割法で問題を部分問題に分割する場合を説明する図である。同図は、説明の便宜上、元の問題Ｐが、４つの部分問題Ｐ１〜Ｐ４がアークで結ばれたグラフと、４つの部分問題Ｐ５〜Ｐ８がアークで結ばれたグラフと、４つの部分問題Ｐ９〜Ｐ１２がアークで結ばれたグラフとに分割される場合を示す。同図の場合、レイヤードネットワークは３レイヤからなる。
図１２は、問題をレイヤードネットワーク型分割法で部分問題に分割可能な場合のＤＮＡコンピュータの動作を説明する図である。同図中、部分問題Ｐ１は、ＤＮＡコンピュータ１１により解かれ、解Ｃ１がＤＮＡコンピュータ１１にフィードバックされる。部分問題Ｐ２は、解Ｃ１を用いてＤＮＡコンピュータ１１により解かれ、解Ｃ２がＤＮＡコンピュータ１１にフィードバックされる。以下同様にして部分問題Ｐ３，Ｐ４に対する演算が行われ、ＤＮＡコンピュータ１１より解Ｃ４が出力されてＤＮＡコンピュータ１１にフィードバックされる。部分問題Ｐ５〜Ｐ８に対する演算は、部分問題Ｐ１〜Ｐ４に対する演算と並行に、且つ、同様に行われ、ＤＮＡコンピュータ１１より解Ｃ８が出力されてＤＮＡコンピュータ１１にフィードバックされる。部分問題Ｐ９〜Ｐ１２に対する演算も、部分問題Ｐ１〜Ｐ４に対する演算と並行に、且つ、同様に行われ、ＤＮＡコンピュータ１１より解Ｃ１２が出力されてＤＮＡコンピュータ１１にフィードバックされる。ＤＮＡコンピュータ１１より解Ｃ４，Ｃ８，Ｃ１２が出力されてＤＮＡコンピュータ１１にフィードバックされると、演算は終了する。
例えば、あるレイヤに属するノードに対応する部分問題を解くためのＤＮＡが入った試験管には、１つ前のレイヤで解かれた部分問題（一般には複数の部分問題）の解であるＤＮＡと混ぜ合わせる。これらの解を、直列型分割法の場合と同様に結合することにより、解候補を得ることができる。最終的な解を得るには、最後のレイヤのノードに対応する部分問題の解を表現しているＤＮＡをまとめて同じ試験管に注入し、この試験管の中の解候補から解を選別する。
このようにして、部分問題の解のコード法として、レイヤードネットワークのどのレイヤのどの部分問題であるかを示すヌクレオチド配列と解を表すヌクレオチド配列の組み合わせで解を表現することができる。又、部分問題の解を表すヌクレオチド配列を中央に置き、その両側にレイヤードネットワークのどのレイヤのどの部分問題の解であるかを示すヌクレオチド配列を置くことができる。部分問題の解を表すヌクレオチド配列から問題の解を表すヌクレオチド配列を合成するために、レイヤードネットワークのどのレイヤのどの部分問題であるかを表すヌクレオチド配列の組み合わせをプライマーとして利用することもできる。
尚、レイヤードネットワーク型分割法の場合、レイヤードネットワークのレイヤの順序を入れ換える場合もある。この場合、レイヤの順序が染色体に対応することになる。
２．５  解のエラー発生率の抑制
直列型分割法を用いる場合、部分問題を解く順番を入れ換えることができる問題については、ＤＮＡコンピュータが求める解のエラー発生率が最も少なくなる順序で部分問題を解くことが望ましい。このような部分問題を解く順序は、遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を用いることで求める。遺伝的アルゴリズムの染色体の適応度（Ｆｉｔｎｅｓｓ）ｆは、正解率をＣＲ、解のエラー発生率をＥＲ、重み付け係数をＷ１〜Ｗ４、定数をＣＶ１，ＣＶ２、ＤＮＡコンピュータ１１が解を計算するのに必要な計算時間をＣＴ、ＤＮＡコンピュータが解を計算するのに必要なＤＮＡ分子量をＭＱで表すと、最終的な問題の解のエラー発生率ＥＲに基づいて計算され、以下の式（１）〜式（３）のいずれかの如く定義される。
ｆ＝ＣＲ＝１００−ＥＲ                                  式（１）
ｆ＝Ｗ１×（１００−ＥＲ）＋Ｗ２×（ＣＶ１−ＣＴ）      式（２）
ｆ＝Ｗ３×（１００−ＥＲ）＋Ｗ４×（ＣＶ２−ＭＱ）      式（３）
式（１）は、適応度ｆを最終的な解のエラー発生率ＥＲに基づいて計算する。式（２）は、最終的な解のエラー発生率ＥＲに加え、ＤＮＡコンピュータ１１が解を計算するのに必要な計算時間ＣＴに基づいて適応度ｆを計算する。又、式（３）は、最終的な解のエラー発生率ＥＲに加え、ＤＮＡコンピュータ１１が解を計算するのに必要なＤＮＡ分子量ＭＱに基づいて適応度ｆを計算する。尚、適応度ｆは、式（１）〜式（３）のうち、少なくとも２つに基づいて計算したものの平均値等を用いても良い。
図１３は、遺伝的アルゴリズムによるＤＮＡコンピュータの制御を説明する図である。同図中、部分問題Ｐ１，Ｐ２をこの順序で解く場合の適応度はｆ１であり、部分問題Ｐ２，Ｐ１をこの順序で解く場合の適応度はｆ２である。又、部分問題Ｐ１１，Ｐ１２をこの順序で解く場合の適応度はｆ３である。
染色体の交叉には、ＰＭＸ（Ｐａｒｔｉａｌｌｙ  Ｍａｔｃｈｅｄ  Ｃｒｏｓｓｏｖｅｒ）を用いる。ＰＭＸは、交叉の対象となる染色体の領域にある遺伝子間のマッピングを元に子供の染色体を矛盾なく構成する交叉法の１つである。ただし、部分問題を解く順序に制約があり、子供の染色体がその制約を満足しない場合には、子供を作らない。ＤＮＡコンピュータ１１が解を計算するのに長いＤＮＡ計算時間ＣＴを必要とする部分問題や、ＤＮＡコンピュータ１１が解を計算するのに多いＤＮＡ分子量ＭＱを必要とする部分問題を含む染色体の領域を交叉の対象として選択して、適応度ｆを効果的に増加させることができる。
突然変異は、２つの遺伝子をある定められた確率で変換する。突然変異の場合も、部分問題を解く順序に制約がある場合には、制約を満足しない突然変異は禁止される。更に、突然変異を起こす領域を、ＤＮＡコンピュータ１１が解を計算するのに長いＤＮＡ計算時間ＣＴを必要とする部分問題や、ＤＮＡコンピュータ１１が解を計算するのに多いＤＮＡ分子量ＭＱを必要とする部分問題を含む染色体の領域とすると、突然変異によって適応度ｆを効果的に増加させることができる。
図１４は、遺伝的アルゴリズムによるＤＮＡコンピュータの制御を説明するフローチャートである。同図中、ステップＳ２１〜Ｓ２８は、汎用コンピュータにより実行され、ステップＳ３１〜Ｓ３７は、ＤＮＡコンピュータ１１により実行される。
図１４において、ステップＳ２１は、解くべき問題を上記の如き部分問題に分割する。ステップＳ２２は、部分問題を解く順序をランダムにして遺伝的アルゴリズム（ＧＡ）の解候補の初期集団を作る。ステップＳ２３は、初期集団に対して、交叉という操作を行う。ステップＳ２４は、初期集団に対して、突然変異という操作を行い、ステップＳ２５は、ＤＮＡコンピュータ１１へ部分問題を解く順序を渡す。ステップＳ２６は、ＤＮＡコンピュータ１１からの正解率ＣＲ等の情報に基づいて適応度ｆを計算し、ステップＳ２７は、適応度ｆに基づいて、部分問題を解く順序のうち、ＤＮＡコンピュータ１１が求める解のエラー発生率ＥＲが最も少なくなる順序を選択する。ステップＳ２８は、選択された順序で解かれた部分問題の解がある基準（制約）を満たしているか否かを判定し、判定結果がＮＯであると、処理はステップＳ２３へ戻る。他方、ステップＳ２８の判定結果がＹＥＳであると、汎用コンピュータの処理は終了する。
他方、ＤＮＡコンピュータ１１において、ステップＳ３１は、上記ステップＳ２５から渡される部分問題を解く順序で、各個体の染色体が表す部分問題を計算する。ステップＳ３２は、部分問題の番目ｋをｋ＝０に設定する。ステップＳ３３は、ｋ番目の部分問題の解を求める。ステップＳ３４は、ｋ−１番目の部分問題の解を表すＤＮＡがあれば、ｋ番目の部分問題の解を表すＤＮＡと結合する。ステップＳ３５は、ｋをｋ＝ｋ＋１にインクリメントする。ステップＳ３６は、全ての部分問題について解を計算したか否かを判定し、判定結果がＮＯであると、処理はステップＳ３３へ戻る。他方、ステップＳ３６の判定結果がＹＥＳであると、ステップＳ３７は、正解率ＣＲ（又はエラー発生率ＥＲ）、計算時間ＣＴ、ＤＮＡ分子量ＭＱ等の、適応度ｆを計算するのに必要な情報を上記式（１）〜式（３）に基づいて計算し、汎用コンピュータへ渡す。具体的には、ステップＳ３７は、適応度ｆを計算するのに必要な情報を、上記ステップＳ２６へ渡す。
次に、異なる４種類のオリゴヌクレオチド（ＤＮＡの断片）Ｄ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４を組み合わせてＤＮＡの配列長が決まった長さである９塩基以下で、且つ、Ｇ，Ｃの含量（以下、単にＧＣ含量と言う）が大きいＤＮＡを合成するという元の問題Ｐを考える。つまり、この問題Ｐは、「長さが９塩基以下のＤＮＡでＧＣ含量が最大のものを求めよ」ということである。図１５は、組み合わせるオリゴヌクレオチド（ＤＮＡの断片）の長さとＧＣ含量の関係を示す図である。
この場合の部分問題Ｐ１〜Ｐ３は、次のように定義される。部分問題Ｐ１は、「１つのオリゴヌクレオチドで長さが９塩基以下のＤＮＡを作る」である。部分問題Ｐ２は、「２つのオリゴヌクレオチドで長さが９塩基以下のＤＮＡを作る」である。又、部分問題Ｐ３は、「３つのオリゴヌクレオチドで長さが９塩基以下のＤＮＡを作る」である。この場合、制約付き解候補は、長さが９塩基以下のＤＮＡである。
最初、試験管には４種類のオリゴヌクレオチド（ＤＮＡの断片）Ｄ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４が入っているものとする。この場合、オリゴヌクレオチドＤ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４の長さはいずれも９塩基以下なので、図１６〜図２０からわかるように、これらのオリゴヌクレオチドＤ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４はいずれも部分問題Ｐ１の制約付き解候補である。図１６は、オリゴヌクレオチド（制約付き解候補）Ｄ０から進化的方法を利用して作られる制約付き解候補を説明する図である。図１７は、制約付き解候補Ｄ１から進化的方法を利用して作られる制約付き解候補を説明する図である。図１８は、制約付き解候補Ｄ２から進化的方法を利用して作られる制約付き解候補を説明する図である。図１９は、制約付き解候補Ｄ３から進化的方法を利用して作られる制約付き解候補を説明する図である。図２０は、制約付き解候補Ｄ４から進化的方法を利用して作られる制約付き解候補を説明する図である。図１６〜図２０中、「×」印の付けられたＤＮＡは、制約付き解候補ではないので、実際のＤＮＡは作られない。又、制約付き解候補の近傍に示された括弧内の数字は、最初（１番目）の数字が制約付き解候補の塩基配列の長さを示し、２番目の数字が制約付き解候補のＧＣ含量（任意単位）を示す。
部分問題Ｐ２の制約付き解候補は、上記部分問題Ｐ１の制約付き解候補Ｄ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４を使って求める。先ず、オリゴヌクレオチド（ＤＮＡの断片）Ｄ０にオリゴヌクレオチドＤ１，Ｄ２，Ｄ３，Ｄ４を付加したオリゴヌクレオチドＤ０−Ｄ１，Ｄ０−Ｄ２，Ｄ０−Ｄ３，Ｄ０−Ｄ４を考える。オリゴヌクレオチドＤ０−Ｄ１，Ｄ０−Ｄ２，Ｄ０−Ｄ３，Ｄ０−Ｄ４は、長さが夫々６，７，９，８塩基であり、ＣＧ含量が夫々３７，４０，４９，４４である。つまり、オリゴヌクレオチドＤ０−Ｄ１，Ｄ０−Ｄ２，Ｄ０−Ｄ３，Ｄ０−Ｄ４は、いずれも長さが９塩基以下であり、制約付き解候補であるので、実際にＤＮＡコンピュータ１１を動作させて対応するＤＮＡを作る。図１６からわかるように、以下同様にして、オリゴヌクレオチドＤ１にオリゴヌクレオチドＤ２，Ｄ３，Ｄ４，Ｄ０を付加したオリゴヌクレオチドＤ１−Ｄ２，Ｄ１−Ｄ３，Ｄ１−Ｄ４，Ｄ１−Ｄ０、オリゴヌクレオチドＤ２にオリゴヌクレオチドＤ３，Ｄ４，Ｄ０，Ｄ１を付加したオリゴヌクレオチドＤ２−Ｄ３，Ｄ２−Ｄ４，Ｄ２−Ｄ０，Ｄ２−Ｄ１オリゴヌクレオチド、オリゴヌクレオチドＤ３にオリゴヌクレオチドＤ４，Ｄ０，Ｄ１，Ｄ２を付加したオリゴヌクレオチドＤ３−Ｄ４，Ｄ４−Ｄ０，Ｄ４−Ｄ１，Ｄ４−Ｄ２、オリゴヌクレオチドＤ４にオリゴヌクレオチドＤ０，Ｄ１，Ｄ２，Ｄ３を付加したオリゴヌクレオチドＤ４−Ｄ０，Ｄ４−Ｄ１，Ｄ４−Ｄ２，Ｄ４−Ｄ３も制約付き解候補であることが示せる。
次に、部分問題Ｐ３の制約付き解候補は、上記部分問題Ｐ２の制約付き解候補を使って求める。先ず、オリゴヌクレオチドＤ０−Ｄ１にオリゴヌクレオチドＤ２を付加したオリゴヌクレオチドＤ０−Ｄ１−Ｄ２を考える。オリゴヌクレオチドＤ０−Ｄ１−Ｄ２の長さは９塩基以下であり、制約付き解候補であるので、実際にＤＮＡコンピュータ１１を動作させて対応するＤＮＡを作る。
次に、オリゴヌクレオチドＤ０−Ｄ１にオリゴヌクレオチドＤ３を付加したオリゴヌクレオチドＤ０−Ｄ１−Ｄ３を考える。オリゴヌクレオチドＤ０−Ｄ１−Ｄ３の長さは１１塩基であり９塩基以下ではなく、制約付き解候補ではないので、実際にＤＮＡコンピュータ１１を動作させて対応するＤＮＡを作ることはしない。オリゴヌクレオチドＤ０−Ｄ１にオリゴヌクレオチドＤ４を付加する場合も同様である。つまり、部分問題Ｐｋのある制約付き解候補から導かれる部分問題Ｐｋ＋１の制約付き解候補が実際の解候補になるか否かをコンピュータシミュレーションで明確にすることで、部分問題Ｐｋの制約付き解候補が実際の解候補とならない場合にはＤＮＡコンピュータ１１の演算を行わないことで、ＤＮＡコンピュータ１１の計算効率を向上することができる。
図２１は、このように、進化的方法を用いて無駄な演算を省略する方法を説明するフローチャートである。同図中、ステップＳ４１は、例えばオリゴヌクレオチドＤ０−Ｄ１にオリゴヌクレオチドＤ３を付加すると長さが９塩基を超えるか否かを判定し、判定結果がＮＯであると、長さが９塩基以下なので制約付き解候補であると判断する。他方、ステップＳ４１の判定結果がＹＥＳであると、ステップＳ４２は、オリゴヌクレオチドＤ０−Ｄ１−Ｄ３は制約付き解候補ではないと判断する。又、ステップＳ４３は、オリゴヌクレオチドＤ０−Ｄ１−Ｄ３については演算が途中で破綻するので、ＤＮＡコンピュータ１１による演算は行わない。
次に、オリゴヌクレオチドＤ０−Ｄ２にオリゴヌクレオチドＤ１を付加したＤ０−Ｄ２−Ｄ１を考える。オリゴヌクレオチドＤ０−Ｄ２−Ｄ１の長さは９塩基であり、制約付き解候補であるので、実際にＤＮＡコンピュータ１１を動作させて対応するＤＮＡを作る。
オリゴヌクレオチドＤ０−Ｄ３の長さは既に９塩基になっているので、これ以上オリゴヌクレオチドを付加しない。オリゴヌクレオチドＤ０−Ｄ４についても、オリゴヌクレオチドＤ１，Ｄ２，Ｄ３のいずれを付加しても長さが９塩基を超えてしまうので、これ以上オリゴヌクレオチドを付加しない。
オリゴヌクレオチドＤ１−Ｄ２の場合、オリゴヌクレオチドＤ１−Ｄ２−Ｄ０，Ｄ１−Ｄ２−Ｄ４の長さは９塩基であり、制約付き解候補となるが、オリゴヌクレオチドＤ１−Ｄ２−Ｄ３の長さは１０塩基であり９塩基を超えるので、制約付き解候補とはならない。又、オリゴヌクレオチドＤ１−Ｄ３−Ｄ０，Ｄ１−Ｄ３−Ｄ２，Ｄ１−Ｄ３−Ｄ４はいずれも長さが１０塩基以上となるため、制約付き解候補とはならない。
次に、オリゴヌクレオチドＤ１−Ｄ４にオリゴヌクレオチドＤ０を付加したオリゴヌクレオチドＤ１−Ｄ４−Ｄ０を考える。オリゴヌクレオチドＤ１−Ｄ４−Ｄ０の長さは１０塩基であり９塩基以下ではなく、制約付き解候補とはならない。しかし、１つ前の制約付き解候補Ｄ１−Ｄ４は保存しておく。これにより、保存しておいた解候補（オリゴヌクレオチド）Ｄ１−Ｄ４にオリゴヌクレオチドＤ２を付加することで、オリゴヌクレオチドＤ１−Ｄ４−Ｄ２が得られる。このオリゴヌクレオチドＤ１−Ｄ４−Ｄ２の長さは９塩基なので、制約付き解候補となり、以下上記と同様の手順を繰り返す。
つまり、部分問題Ｐｋの解候補γｋ＋１（制約付き解候補でなくても可）が問題Ｐの解にならないことがコンピュータシミュレーションにより明確になった場合、１つ前の部分問題Ｐｋの制約付き解候補Ｃｋから解候補γｋ＋１とは異なる解候補を作り部分問題Ｐｋ＋１の制約付き解候補を見つける手法を用いることで、ＤＮＡコンピュータ１１の計算効率を向上することができる。
図２２は、このように、進化的方法を用いて前の計算結果を参照して計算を高速化する方法を説明するフローチャートである。同図中、ステップ５１は、例えばオリゴヌクレオチドＤ２を付加したオリゴヌクレオチドＤ１−Ｄ４は制約付き解候補になるか否かを判定し、判定結果がＹＥＳであると制約付き解候補であると判断する。他方、ステップＳ５１の判定結果がＮＯであると、ステップＳ５２は、１ステップ前の解が使えないかを確認する。この場合、１ステップ前のステップとは、例えばステップＳ５３である。このステップＳ５３は、オリゴヌクレオチドＤ１−Ｄ４の長さが６塩基であり制約付き解候補であると判断している。又、ステップＳ５４は、オリゴヌクレオチドＤ１−Ｄ４にオリゴヌクレオチドＤ０を付加したオリゴヌクレオチドＤ１−Ｄ４−Ｄ０の長さは１０塩基で９塩基を超えているので、制約付き解候補ではないと判断している。従って、この場合、ステップＳ５２は１ステップ前の解が使えることを確認し、ステップＳ５５は、オリゴヌクレオチドＤ１−Ｄ４にオリゴヌクレオチドＤ２を付加したオリゴヌクレオチドＤ１−Ｄ４−Ｄ２の長さは９塩基であり、制約付き解候補であると判断する。
部分問題Ｐ１の制約付き解候補Ｄ１から初めて得られる制約付き解候補は、図１７に示す如くとなる。同様にして、部分問題Ｐ１の制約付き解候補Ｄ２から初めて得られる制約付き解候補は、図１８に示す如くとなり、部分問題Ｐ１の制約付き解候補Ｄ３から初めて得られる制約付き解候補は、図１９に示す如くとなり、部分問題Ｐ１の制約付き解候補Ｄ４から初めて得られる制約付き解候補は、図２０に示す如くとなる。
ＤＮＡコンピュータ１１からＧＣ含量が最大のＤＮＡ配列を取り出すと、長さが９塩基でＧＣ含量が５８の解として、Ｄ１−Ｄ２−Ｄ４，Ｄ１−Ｄ４−Ｄ２，Ｄ２−Ｄ１−Ｄ４，Ｄ２−Ｄ４−Ｄ１，Ｄ４−Ｄ１−Ｄ２，Ｄ４−Ｄ２−Ｄ１が得られる。
上述の荻谷昌己及び横森貴、「ＤＮＡコンピュータ」、培風館、２００１（以下、単に「文献１」と言う）に記載されているように、ＤＮＡコンピュータが正常に動作するためには、ＤＮＡ配列のＧＣ含量が揃っていることが望ましい。そうすることで、ＧＣ含量が最大のＤＮＡ配列により、ＤＮＡコンピュータのコードとして安定したものを得ることができる。
２．６  遺伝的アルゴリズムの適用
上記文献１に記載されているように、ＤＮＡコンピュータ１１を正確に動作させるには、ＰＣＲ法で増幅対象のＤＮＡと相補的なＤＮＡ断片であるプライマーの溶解温度を揃えておく必要がある。このための必要条件として、ＤＮＡ配列のＧＣ含量が揃っていることが望ましいことが知られている。問題が３つの部分問題α，β，γで構成されていると仮定すると共に、この時の遺伝的アルゴリズムの染色体｛α，β，γ｝，｛β，α，γ｝，｛α，γ，β｝等を部分問題を解く順番であるものとする。上記文献１に記載されているように、初めの部分問題の解で誤りが発生すると、誤りが後の計算に伝播し、ＤＮＡコンピュータ１１の計算精度を低下させてしまう。
１つの染色体の適応度ｆは、次のようにして計算する。例えば、染色体が｛α，γ，β｝の場合、部分問題αの解候補がａ１，ａ２、部分問題βの解候補がｂ１，ｂ２、部分問題γの解候補がｃ１，ｃ２であると、解候補のＤＮＡも同じ記号で表して、そのＧＣ含量をｇｃ（ａ１）等で表すものとする。次式（４）中、ＣＶ３は定数を示す。又、図２３は、解候補のＧＣ含量（任意単位）を説明する図である。
ｆ＝ＣＶ３−［２３｛（＊ｇｃα−ｇｃ（ａ１））２＋（＊ｇｃα−ｇｃ（ａ２））２｝＋２２｛（＊ｇｃγ−ｇｃ（ｃ１））２＋（＊ｇｃγ−ｇｃ（ｃ２））２｝＋２｛＊ｇｃβ−ｇｃ（ｂ１））２＋（＊ｇｃβ−ｇｃ（ｂ２））２｝］  式（４）
上記式（４）中、＊ｇｃαは解候補ａ１，ａ２のＧＣ含量の平均値を示し、＊ｇｃγは解候補ｃ１，ｃ２のＧＣ含量の平均値を示し、＊ｇｃβは解候補ｂ１，ｂ２のＧＣ含量の平均値を示す。式（４）からもわかるように、初めに解くべき部分問題の解のＧＣ含量のばらつきが少なければ少ない程、適応度ｆは大きくなる。
ここで、次のような４個体から構成された遺伝的アルゴリズムの初期集団［｛α，β，γ｝，｛β，α，γ｝，｛β，γ，α｝，｛γ，β，α｝］を準備する。上記式（４）において定数ＣＶ３＝１００であるものとすると、適応度ｆは次式（５）〜式（８）のように求まる。
ｆ［｛α，β，γ｝］＝６０                                式（５）
ｆ［｛β，α，γ｝］＝３０                                式（６）
ｆ［｛β，γ，α｝］＝２７                                式（７）
ｆ［｛γ，β，α｝］＝５１                                式（８）
｛α，β，γ｝と｛γ，β，α｝を交叉させると、親の個体と同じものが得られる。２番目と３番目の遺伝子を交換する突然変異を｛α，β，γ｝，｛γ，β，α｝に施すと、｛α，γ，β｝，｛γ，α，β｝が得られ、適応度ｆは次式（９），（１０）のようになる。
ｆ［｛α，γ，β｝］＝７２                                式（９）
ｆ［｛γ，α，β｝］＝６６                                式（１０）
従って、この場合は適応度ｆが最も大きな解候補｛α，γ，β｝が最適解を与えることになる。
２．７  有効ハミルトンパス問題への適用
与えられた問題を部分問題へ分割する一般的なアルゴリズムを見つけるのは難しいが、与えられた問題にある程度の規則性がある場合には、この規則性を利用して問題を部分問題に分割することができる。
図２４は、有効ハミルトンパス問題を示す有効グラフである。同図は、１４個のノードＮ１〜Ｎ１４からなり、ノードＮ１のスタート地点からノードＮ１２のゴール地点まで各ノード（頂点）を必ず１回のみ含み向きのある辺の系列があるか否かを判定する有効ハミルトンパス問題を示す。同図からもわかるように、この有効グラフには、同じ構造の部分グラフが存在する。この有効グラフの規則性を利用して、図２５〜図２９に示す如き部分グラフを考える。図２５は、図２４に示す問題の部分問題を示す図、図２６は、図２５に示す部分問題を含む部分問題を示す図、図２７は、図２６に示す部分問題を含む部分問題を示す図、図２８は、図２７に示す部分問題を含む部分問題を示す図、図２９は、図２８に示す部分問題を含む部分問題を示す図である。図２５〜図２９中、破線で示す矢印がハミルトンパスを示す。又、部分グラフが上記部分問題Ｐｋ（ｋ＝１，２，３，４，５）に対応している。
有効ハミルトンパス問題を解くためのＤＮＡコンピュータ自体は、上述のＬｅｏｎａｒｄ  Ｍ．Ａｄｌｅｍａｎ，″Ｍｏｌｅｃｕｌａｒ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｓｏｌｕｔｉｏｎｓ  ｔｏ  ｃｏｍｂｉｎａｔｉｏｎａｌ  ｐｒｏｂｌｅｍｓ″，ＳＣＩＥＮＣＥ，２６６（５１８７）；１０２１−１０２４，１９９４（以下、単に「文献２」と言う）にて既に提案されている。そこで、１４個のノードＮ１〜Ｎ１４と２５個の有効辺を図３０及び図３１のようにコード化することで、上記文献２で提案されているＤＮＡコンピュータをＤＮＡコンピュータ１１として用いて図２４に示す有効ハミルトンパス問題を解くことができる。図３０は、有効ハミルトンパス問題のノードのコード法を示す図、図３１は、有効ハミルトンパス問題の有効辺のコード法を示す図である。
この場合、部分問題を次のように逐次解くことで、ＤＮＡコンピュータ１１が解を計算するのに必要な計算時間ＣＴと、ＤＮＡコンピュータが解を計算するのに必要なＤＮＡ分子量ＭＱを減少させることができる。つまり、図２５に示す部分問題に関係したノードと有効辺をコード化したＤＮＡを利用して上記文献２に提案された方法で解候補を求める。この場合、ノードＮ２，Ｎ３，Ｎ４のうちどのノードをゴール地点とするべきかが問題となる。本実施例では、ＤＮＡコンピュータ１１を使用する前に、コンピュータシミュレーションによりノードＮ２及びノードＮ３をゴール地点として選択した場合の解がないことを予め知ることができるので、そのようなゴール地点を有する部分問題は予め排除しておくことで、ＤＮＡコンピュータ１１を効率良く使用することができる。
又、ノードＮ４をゴール地点とする図２５に示す部分問題をＤＮＡコンピュータ１１に解かせる。次に、この部分問題の解候補を表すＤＮＡが入っている試験管に、図２６に示され新たに使われるノードＮ５，Ｎ６，Ｎ１３，Ｎ１４と有効辺４→５，４→６，４→１３，５→６，５→１４，１３→５，１３→１４，１４→６に対応した図３０及び図３１に示す如きＤＮＡを試験管に入れる。ここで、ｘ→ｙは、ノードＮｘとノードＮｙとを結ぶ有効辺を示すものとする。そして、上記と同様の方法で、図２６に示すようにノードＮ６をゴール地点に設定し、上記文献２に提案された方法で解候補を求める。以下同様の操作を図２９に示す部分問題まで繰り返すことで、上記文献２に提案されている方法より効率的に有効ハミルトンパス問題をＤＮＡコンピュータ１１で解くことができる。
上述の如く、本発明では、ＤＮＡコンピュータと進化的方法を組み合わせることで、ＤＮＡコンピュータが解を計算するのに必要な計算時間と解を計算するのに必要なＤＮＡ分子量を減少させて、計算を効率的に行うことができる。又、ＤＮＡコンピュータが扱う問題を部分問題に分割することで、解候補を効果的に発生させ、問題の解を効率的に探索することができる。更に、ＤＮＡコンピュータと遺伝的アルゴリズムを組む合わせることにより、ＤＮＡコンピュータが計算する解のエラー発生率を抑えて計算を効率的に行うこともできる。
尚、本発明は、上記実施例に限定されるものではなく、本発明の範囲内で種々の改良及び変更が可能であることは、言うまでもない。
【図１】
2004068398.tif 000003
【図２】
2004068398.tif 000004
【図３】
2004068398.tif 000005
【図４】
2004068398.tif 000006
【図５】
2004068398.tif 000007
【図６】
2004068398.tif 000008
【図７】
2004068398.tif 000009
【図８】
2004068398.tif 000010
【図９】
2004068398.tif 000011
【図１０】
2004068398.tif 000012
【図１１】
2004068398.tif 000013
【図１２】
2004068398.tif 000014
【図１３】
2004068398.tif 000015
【図１４】
2004068398.tif 000016
【図１５】
2004068398.tif 000017
【図１６】
2004068398.tif 000018
【図１７】
2004068398.tif 000019
【図１８】
2004068398.tif 000020
【図１９】
2004068398.tif 000021
【図２０】
2004068398.tif 000022
【図２１】
2004068398.tif 000023
【図２２】
2004068398.tif 000024
【図２３】
2004068398.tif 000025
【図２４】
2004068398.tif 000026
【図２５】
2004068398.tif 000027
【図２６】
2004068398.tif 000028
【図２７】
2004068398.tif 000029
【図２８】
2004068398.tif 000030
【図２９】
2004068398.tif 000031
【図３０】
2004068398.tif 000032
【図３１】
2004068398.tif 000033
【国際調査報告】
2004068398.tif 000034
2004068398.tif 000035
2004068398.tif 000036
2004068398.tif 000037