(57)【要約】染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。ストランドを構成する４種類のヌクレオチド（Ａ、Ｇ、Ｃ、Ｔ）を２進エンコーディングする手段を有し、相補的なリンクを形成するヌクレオチドに相補的なコードが割り当てられ、ヌクレオチドのコードおよびその相補体のコードのストレージユニット（１）を含み、ストレージユニットを直列に接続し、「ＤＮＡ」鎖の各ストランドを構成するヌクレオチドの鎖を形成し、それによってその電子的構造を得、ヌクレオチド、ストランド、および「ＤＮＡ」鎖を構成する２つのストランドへの選択的なアクセスを可能にする。ストレージユニット（１）においてエンコードされたグラフによって表すことができるあらゆる問題に適用され、今日では解くことができない問題を、並列形式および多項式時間での軌跡の計算において解くことを可能にする。
2010535370.tif 000002
【特許請求の範囲】
【請求項１】
染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システムであって、
前記鎖は、２つのストランドを有し、
各ストランドは、アデニン（Ａ）、グアニン（Ｇ）、シトシン（Ｃ）、およびチミン（Ｔ）を含むヌクレオチドの鎖によって構成され、
前記ストランド間において、アデニン（Ａ）がチミン（Ｔ）とリンクし、グアニン（Ｇ）がシトシン（Ｃ）とリンクすることによって実行される、相補的なリンクが生成され、
前記ストランドを構成する前記４つの異なる種類のヌクレオチドを２進エンコーディングする手段を有し、相補的なリンクを形成するヌクレオチドに、一方を反転することによる相補的なコードが割り当てられ、
前記ヌクレオチドのコードを保存するストレージユニットであって、その相補的なコードから選択されたコードを保存するおよびコードを保存しないことを選択的に行うストレージユニットを含み、前記ヌクレオチドを得るとともに、その相補体を選択的に得、
前記ストレージユニットを直列に接続し、「ＤＮＡ」鎖の各ストランドを構成するヌクレオチドの鎖を形成し、それによって、その電子的構造を得るとともに、ヌクレオチドへの選択的アクセスを可能にし、ならびにその相補体、ストランド、および「ＤＮＡ」鎖の２つのストランドへの選択的アクセスを選択的に可能にする、染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項２】
異なるモジュールが設けられ、各モジュールはストレージユニットをグループ化することによって構成され、各モジュールには「ＤＮＡ」鎖が保存され、前記モジュールが行および列において接続され、行または列を選択することによって各「ＤＮＡ」鎖にアクセスする、請求項１に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項３】
各ヌクレオチドに割り当てられた２進コードが、２つのビットを含み、その保存が、各ストレージユニットへと加えられる入力に依存する、請求項１または２に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項４】
「ＤＮＡ」の４つのヌクレオチドで構成される底４での命数法のエンコーディング手段を有する、請求項１、２、または３に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項５】
各ヌクレオチドに対応する２つのビットが、０から３の１０進法の量をとり、２つのビットの位置および該位置が受ける値によって決定される複数の数値表現を形成する、請求項４に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項６】
加算、減算、乗算、および除算から選択された演算を実行する手段を有するとともに、任意の単精度もしくは倍精度の固定数または浮動小数点数のエンコーディングを有する、請求項５に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項７】
前記ストレージユニットが、揮発性メモリ（ＩＡＭ）および不揮発性メモリ（ＩＲＯＭ）から選択される、請求項１に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項８】
ストランドの位置の特定後ならびにヌクレオチドおよびヌクレオチドグループの選択的指定後の「ＤＮＡ」鎖の位置の特定によって、構造化されたアクセスの手段を有する、請求項２および７に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項９】
頂点および辺によって構成され、ならびに重み（方向）によって選択的に構成されるエレメントを含むグラフによる問題の表現を、ストランドを形成するストレージユニットにおいてエンコードする手段を有し、最初のエレメントに対応する頂点および辺ならびに最後のエレメントを含まないエレメントに対応する頂点および辺によって構成されるグラフのエレメントを含む第１集合を、１つのストランドにおいてエンコードし、
最後のエレメントと最後のエレメントを含まないエレメントに対応するエレメントとによって構成されるグラフのエレメントを含む第２集合を、相補的なストランドにおいてエンコードし、
両方のストランドの各ストレージユニットが、行列を形成する比較器によって互いに連結され、両方の集合におけるすべてのエレメント間の比較を並行して実行し、グラフによって表すことができる問題を解く、請求項１から８に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１０】
行列を形成する比較器がバッファへと接続され、該バッファに多項式次数の経路回復手段が加えられ、グラフの２点間の最適ルートを割り出す、請求項９に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１１】
辺の重みのさらなるストレージ手段、各辺に重みを加え、各辺の総重みを得る手段、およびあらかじめ確立された基準に従って各辺の総重みを並べ替える手段を有し、ダイクストラ、フロイド−ワーシャル、ベルマン−フォード、およびフォード−フルカーソンから選択されたアルゴリズム問題を解く、請求項１０に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１２】
車両の集団、工業用車両の最適化、工業プロセスの最適化、ワークフロー、カップリング問題、および通信ネットワークから選択されるフロー問題に適用される、請求項９に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１３】
２つのストランドを構成するストレージユニットにおいてハミルトン経路問題をエンコードする手段を有し、該ストランドの一方において完全グラフがエンコードされ、相補体において既知の制限を有する完全グラフがエンコードされ、
前記２つのストランドは、両方のグラフの辺を２対２で並列に比較する行列を形成する比較器へと接続され、各比較結果の２つのビットがすべて等しくかつ同じ辺を指し、結果として両方のグラフに属すかどうかを示し、
前記比較結果を、前記辺が経路であるかどうかを示すウォレスツリーレベルを生成する手段へと加える、請求項９に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１４】
前記辺を２対２で比較する比較器は、論理的桁上げ保存半加算器を有し、該比較器の出力が、前記比較結果の単一ビットの論理検出ポートへと接続され、単一データを得る、請求項１３に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１５】
前記ウォレスツリーレベルを生成する手段は、完全グラフを表す比較器のユニットにおける各列用の第１論理ポートを有し、該ポートは該比較器の出力へと接続され、制限を有するグラフへの前記辺の所属を確認し、経路であるかどうかを示す、請求項１４に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１６】
前記第１論理ポートの出力は、すべての辺が経路であるかどうかを検出する第２論理ポートへと接続され、ハミルトン経路を決定し、得られた結果のストレージ手段を含む、請求項１４に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１７】
見つけられた経路を受け、重みと辺との間の対応を確立し、各経路の重みを得る手段を有し、最良経路の選択のためにあらかじめ確立された基準に従って経路の重みを並べ替える手段を有する、請求項３および１６に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１８】
辺の重みのさらなるストレージメモリを有し、頂点のエンコーディングを参照するメモリアドレスの保存によって、重みと辺との間の対応を確立し、重みを加え、連続するアドレスにおいて前記さらなるメモリに保存された各経路の合計を得、経路の重みを並べ替えることによって、あらかじめ確立された基準に従って最良経路の選択を確立する、請求項１５に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項１９】
グラフの出力頂点が目的地頂点と同じである表示的エンコーディングによって、ハミルトン閉路の解決に適用される、請求項１８に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項２０】
頂点が辺を表し、辺が頂点を表すようにグラフをエンコーディングする手段を有し、すべての辺を通過するために辿らなければならない頂点の並びを得、オイラー経路の問題を解くことを可能にする、請求項９に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項２１】
辺の重みのエンコーディングを確立し、オイラー経路における新たな最適化問題を提示する手段を有する、請求項２０に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【請求項２２】
最初の頂点が最後の頂点と同じであることを、前記ストランドにおいてエンコーディングする手段を有し、オイラー閉路を解く、請求項２０または２１に記載の染色体の「ＤＮＡ」構造の鎖をエミュレートする電子システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、この明細書の表題に示されるとおり、「ＤＮＡ」構造の鎖をエミュレートする電子システムであって、従来から行われているように「ＤＮＡ」（ただし、本発明の場合には、有機「ＤＮＡ」によってではなく電子回路によって具現化されるため、無機「ＤＮＡ」である）によって演算の問題を解くことを可能にし、「ＤＮＡ」における有機の性質の特徴を無機の「ＤＮＡ」から利用する電子システムを提供するという目的を有している。
【０００２】
本発明は、「ＧＰＳ」（全地球測位システム）における軌跡の計算と、陸海空のナビゲータにおける経路の計算と、製造における工業用制御および、工業フローまたは作業における最適化プロセスの問題と、において使用される軌跡、ネットワーク、およびフローの問題を解くことを可能にする電子「ＤＮＡ」構造を提供するハードウェアシステムで構成される。
【０００３】
一般に、本発明は、後述されるように、「ＤＮＡ」構造の鎖に関連付けられたグラフによって表すことができるあらゆる問題を解くことに適用可能である。
【背景技術】
【０００４】
数学およびコンピューティングは、グラフ理論として知られる科学の分野に密接に関係している。グラフは、ノードまたは頂点と呼ばれるエレメントの集まりであり、ノードまたは頂点が、辺（エッジ）または弧によって連結され、これらの辺が、指定の方向または向きを有することができる。この分野における最初の先駆者の一人は、ケーニヒスベルク（７つの橋を有するプロシアの都市）の橋問題として知られる問題を１７３６年に提起したレオンハルト・オイラー（Ｌｅｏｎａｒｄ  Ｅｕｌｅｒ）である。オイラーは、それぞれの橋を１回だけ渡って都市全体を巡ることができるかどうかという問題を提起した。この都市の概略表示において、橋が４つの陸地部分を連結していることを観察することができる。このことは、試行錯誤の探索が結果につながらず、そのため、この問題をグラフによって表現できる場合、グラフ理論の技術、方法、およびアルゴリズムを適用し、解を見つける可能性があることを意味する。この問題ゆえに、最初のステップは、グラフ理論に向かって踏み出している。グラフ理論は長い年月をかけて発展しており、この研究領域または分野で働く多数の研究グループが存在している。数年後に、アイルランド人の数学者、物理学者、および天文学者であるウィリアム・ローワン・ハミルトン（Ｗｉｌｌｉａｍ  Ｒｏｗａｎ  Ｈａｍｉｌｔｏｎ）が、グラフ理論に存在する最も複雑な問題の１つであり、各頂点を正確に１回だけ訪問する経路またはグラフを有することで構成されるハミルトン経路問題または巡回セールスマン問題を提起した。その複雑さゆえに、この問題は、コンピューティングにおいてＮＰ完全問題と考えられている。この時点で、数学的問題またはコンピューティング問題が、それらの複雑さによって種々のグループに分類されることを示しておく必要がある。
−  Ｐの複雑さ。これは、問題を決定性機械によって多項式時間で解くことができる場合である。
−  ＮＰの複雑さ。これは、問題を非決定性機械によって多項式時間で解くことができる場合である。
−  ＮＰ完全の複雑さ。これは、ＮＰの複雑さの問題であるが、非決定性機械によって多項式時間で解くことが難しい。
【０００５】
また、ハミルトン経路問題を解くための並列的実装が存在するが、それらは、大量のリソースおよび接続されたノード間の通信を必要とする。その誘因のため、アドルマン（Ａｄｌｅｍａｎ）が、有機ＤＮＡによりプログラミングする新規な代案を提示した。これは、演算性能においてしたがって最終結果の取得において大規模な並列処理を有するが、前記限界を伴う。彼は、有機ＤＮＡでのプログラミングによってハミルトン経路問題を解くシステムを設計し、したがって、ＮＰ完全問題を多項式に近い計算時間で解くことができることを実証した。
【０００６】
この意味では、特許文献：米国特許第７１６７８４７号明細書を引用することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第７１６７８４７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
２０世紀において、科学者のエドガー・ダイクストラ（Ｅｄｓｇｅｒ  Ｄｉｊｋｓｔｒａ）は、或る点から別の点へとどのように進むべきかを確立するだけでなく、それを可能な限り最短時間で行うことも確立する経路計算の新たなシステムを提案した。ダイクストラは、計算機科学に基づいて研究を行い、その結果が、ダイクストラのアルゴリズムとなった。このアルゴリズムは、有向グラフにおける出発頂点の付与のもとで辺の正の重み付けを有する最短経路の判断に基づいている。この考え方は、出発頂点から現れて他のすべての頂点に達するすべての最短経路を探索することにある。ひとたび出発頂点から、グラフを構成する残りの頂点までの最短経路が割り出されると、アルゴリズムは停止する。このアルゴリズムは、負のコストの辺を有するグラフでは機能しない、大食アルゴリズムとして知られるストラテジーに基づいている。後に、ロバート・Ｗ・フロイド（Ｒｏｂｅｒｔ  Ｗ．Ｆｌｏｙｄ）が、ワーシャル（Ｗｈａｒｓｈａｌｌ）とともに、ダイクストラのアルゴリズムを修正した。修正は適切であったが、それらは依然として、工業ネットワークまたは経路計算には適用できなかった。ある科学における問題および別の科学における利点を眺め、本発明は、電子工学および遺伝学というこれまでは別々であった２つの領域を組み合わせる技術を確立する。この技術は、集積回路、電子工学、ならびに「ＤＮＡ」または遺伝学に基づき、電子回路による最初の無機「ＤＮＡ」を生み出し、それゆえに、本発明は、この技術をＩｎＣｈｒｏＳｉｌ（シリコン基盤の無機染色体）と呼んでいる。
【０００９】
本発明のシステムは、電子回路によって具現化されているため、ユーザがユーザの所望のとおりに多数回使用することができるため、再使用可能であるという大きな利点を有している。
【課題を解決するための手段】
【００１０】
このような欠点を解消し、上述の目的を達成するために、本発明は、無機「ＤＮＡ」の製造を実現する新規なシステムを開発した。
【００１１】
本発明を理解するために、「ＤＮＡ」およびたんぱく質によって形成される染色体の遺伝学的な紹介を行う必要がある。次に、「ＤＮＡ」は、セントロメアによって連結された２本の縦長の繊維で構成される。これらの繊維は染色分体と呼ばれ、複製された「ＤＮＡ」の２つの同一なストランドを表す。
【００１２】
したがって、「ＤＮＡ］は、以下に挙げられる４つの種類に分類されるヌクレオチドのストランドまたは鎖で構成される。
‐アデニン。文字Ａによって表される。
‐グアニン。文字Ｇによって表される。
‐シトシン。文字Ｃによって表される。
‐チミン。文字Ｔによって表される。
【００１３】
結果として、「ＤＮＡ」は、リンクした２本のストランドで構成されており、各ストランドが、無数のヌクレオチドを含んでいる。同じストランドにおいては、相補的なヌクレオチドは存在せず、すなわち、いかなる制限もなく連結することができる。しかしながら、２本のストランドのリンクについては、相補性の制約が存在し、１つのストランドのアデニン（Ａ）は、相補的なストランドのチミン（Ｔ）とだけ連結することができ、同様に、グアニン（Ｇ）はシトシン（Ｃ）とだけリンクすることができる。
【００１４】
本発明のシステムは、ストランドを構成する４つの異なる種類のヌクレオチドを２進エンコーディングする手段を有し、相補的なリンクを形成するヌクレオチドが、一方を反転させることによる相補的なコードを割り当てられることを特徴とする。さらに、本発明は、ヌクレオチドのコードを保存し、その相補的なコードから選択されたコードを保存し、またはコードを保存しないストレージユニットを含み、すべて、ヌクレオチドおよびその相補体またはヌクレオチドだけを生成する。前記ストレージユニットを直列に接続し、「ＤＮＡ」鎖の各ストランドを構成するヌクレオチドの鎖を形成する。結果として、ストレージユニットにおいて保存される前記エンコーディングを使用し、所望の結果に応じて種々のストレージユニットの選択を行う公知の電子回路によって、ヌクレオチドおよび／またはその相補体へのアクセス、必要に応じて１つのストランドおよび「ＤＮＡ」鎖の２つのストランドへのアクセスを可能にする電子構造が生成される。
【００１５】
本発明は、ストレージユニットをグループ化することによって構成される種々のモジュールを提供し、各モジュールには「ＤＮＡ」鎖が保存され、モジュールが行および列において接続され、行または列を選択することによって各「ＤＮＡ」鎖にアクセスすることができる。
【００１６】
なされた説明から、本発明の第１の用途が、「ＤＮＡ」データベースとしての使用で構成されることが、導き出される。
【００１７】
本発明の好ましい実施の形態においては、各ヌクレオチドに割り当てられたコードが、２つのビットを含み、その保存が、電子手段によって各ストレージユニットへと加えられる入力に依存し、各ストレージユニットを、所望のヌクレオチドおよびその相補体に応じてエンコードすることができる。
【００１８】
本発明は、染色体の４つのヌクレオチド（Ａ、Ｇ、Ｃ、およびＴ）で構成される底４での命数法のエンコーディング手段の組み込みを提供する。
【００１９】
さらに、各ヌクレオチドに対応する２つのビットが、０〜３の１０進法の量をとり、２つのビットの位置および各位置が受ける値によって決定される複数の数値表現を形成できる。このエンコーディングは、本発明の命数法およびエンコーディングシステムによって、１０進法または２進法との対応を有する任意のエンコーディングシステムをエンコードできることを可能にする。
【００２０】
上述のエンコーディングは、本発明が、加算、減算、乗算、および／または除算などといった演算の実行、ならびに補数Ａ１および補数Ａ２におけるエンコーディングを使用する任意の単精度および倍精度の固定数または浮動小数点数のエンコーディング手段を組み込むことを可能にする。
【００２１】
最先端のメモリと同様に、本発明のストレージユニットは、揮発性であってもよく、その場合には、本発明は、それらをＩｎＣｈｒｏＳｉｌアクセスメモリ（ＩＡＭ）と呼ぶが、本発明がＩｎＣｈｒｏｓｉｌ読み出し専用メモリ（ＩＲＯＭ）と呼ぶ、読み出し専用不揮発性メモリも可能である。本発明は、「ＤＮＡ」鎖の位置の特定と、続くストランドの位置の特定と、その後のヌクレオチドまたはヌクレオチドグループの指定とによって、モジュールおよびストレージユニットへのアクセスの構造化された手段を組み込み、したがって鎖の全体または鎖の一部へのアクセスが可能となる。結果として、本発明のモジュールおよびストレージユニットを使用し、それは従来からのメモリにおいて生じるように行または列によってアクセスされることはないが、すでに述べたように３つの異なるアクセスを可能にし、三次元アクセスと呼ぶことができる３つの選択からのアクセスを可能にする。
【００２２】
さらに、すでに述べたように、「ＤＮＡ」鎖を行および列と考えることができ、すなわち、ＩＡＭメモリを管理するシステムが、行または列のいずれかによって、どのように「ＤＮＡ」鎖がメモリに保存されるかを規定することができる。
【００２３】
上述の全体構造に基づいて理解されるように、本発明は、頂点および辺によって構成されるエレメントであって、辺の重みまたは方向を任意で組み込んでもよいエレメントを含むグラフによる問題の表現を、ストランドを形成するストレージユニットにおいてエンコードする手段を組み込んでもよく、したがって、本発明のシステムは、最後のエレメントを含まない最初のエレメントに対応する頂点および辺を含む第１集合であって、その重みを含まない第１集合においてストランドをエンコードし、最後のエレメントに対応する頂点および辺ならびに最後のエレメントを含まないエレメントに対応する頂点および辺よって同様に構成されるグラフのエレメントを含む第２集合を、相補的なストランドにおいてエンコードする。両方のストランドの各ストレージユニットが、行列を形成する比較器によって互いに接続され、したがって両方のストランドの処理が、両方の集合におけるすべてのエレメント間の比較と同様に、並行して実行され、グラフによって表すことができる問題を解くことを可能にする。
【００２４】
比較器は行列を形成し、バッファへと接続され、バッファに多項式次数の回復手段が加えられ、グラフの２点間の最適ルートを割り出す。
【００２５】
すでに示したように、グラフの辺が、重みまたは方向を有することができ、その場合、本発明は、辺の重みのさらなるストレージ手段、各辺に重みを加え、各辺の総重みを得る手段、およびあらかじめ確立された基準に従って各辺の総重みを並べ替える手段を組み込み、ダイクストラ、フロイド−ワーシャル、ベルマン−フォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）、およびフォード−フルカーソン（Ｆｏｒｄ−Ｆｕｌｋｅｎｓｏｎ）などのアルゴリズム問題を解くことを可能にする。
【００２６】
上述の構造は、フロー問題への適用を可能にし、フロー問題は、車両の集団、工業プロセスの最適化、ワークフロー、カップリング問題、および通信ネットワークであってもよく、これらの問題がグラフとして表される。したがって、例えば、工業プラントの機械類の情報およびインストラクションがグラフとして表され、提示された問題を解くことができる。
【００２７】
同様に、本発明は、ストランドを構成するメモリユニットへのハミルトン経路問題のエンコーディングを提供し、ストランドの一方において、既知の制限を有する完全グラフがエンコードされる。この場合、ストランドは、両方のグラフの辺を２対２の並列形式で比較する行列を形成する比較器へと接続され、各比較結果のビットがすべて同じでかつ同じ辺を指し、結果として両方のグラフに属するかどうかを示す。
【００２８】
辺が経路であるかどうかを示すウォレス（Ｗａｌｌａｃｅ）ツリーレベルを生成する手段が、比較結果に適用され、ハミルトン経路問題が解決される。
【００２９】
この場合、両方のグラフの辺を２対２で比較する比較器は、論理的桁上げ保存半加算器で構成され、比較器の出力が、すでに示したように、比較結果の単一ビットを検出する論理ポートへと接続され、単一データを得、各比較結果のビットが、エンコードされた集合の両方のグラフに属するかどうかを示す。
【００３０】
ウォレスツリーレベルを生成する手段は、完全グラフを表す比較器の行列における各列用の第１論理ポートを有し、該ポートは該比較器の出力へと接続され、制限を有するグラフの辺の集合への前記辺の所属を確認し、経路であるかどうかを示す。
【００３１】
第１論理ポートの出力は、すべての辺が経路であるかどうかを検出する第２論理ポートへと接続され、本発明は、ハミルトン経路を決定する。さらに本発明は、得られた結果のストレージ手段を組み込む。
【００３２】
この場合、さらに本発明は、辺の重みが考慮に入れられる可能性をもたらし、その理由で、見つけられた経路を受け、重みと辺との間の対応を確立し、各経路の重みを得る手段を有する。この場合、最良経路の選択のためにあらかじめ確立された基準に従って経路の重みを並べ替える手段をさらに有する。
【００３３】
本発明の別の実施の形態においては、頂点がエンコードされ、したがってそれらを接続する辺の値が確立される場合に、システムが、そのメモリアドレスにおいて、グラフのその辺の重みの値を保存する。この場合、システムはメモリ内の辺の値を探す。なぜならば、そのアドレスが既知であるときその値は既知であり、すなわちシステムはメモリへの参照をエンコードし、それはアドレスであって辺の値ではないからである。得られた重みが、アドレスによってメモリに保存される各経路の合計を得るために加算され、あらかじめ確立された基準に従って経路の重みを並べ替えることによって、最良の経路の選択が行われる。
【００３４】
さらに、この構成は、グラフの出力頂点が目的地頂点に等しい表示的エンコーディングによって、ハミルトン閉路問題の解決への本発明の適用を可能にする。
【００３５】
さらに示されるべきことは、本発明が、頂点が辺を表し、その逆も然りであるように、グラフをエンコーディングする手段を組み込み、すべての辺を通過するために辿らなければならない頂点の並びを得、オイラー経路の問題を解くことを可能にすることである。
【００３６】
最初の頂点が最後の頂点と同じであることを、ストランドにおいてエンコーディングする手段を組み込むことによって、オイラー閉路を解くサイクルへの本発明の適用が可能となる。
【００３７】
さらに本発明は、オイラー経路または閉路の解法において辺の重みにおけるエンコーディングの確立を可能にし、したがってオイラー経路の新たな最適化問題の提案を可能にする。
【図面の簡単な説明】
【００３８】
【図１】有機「ＤＮＡ」鎖の図を示す。
【図２】さまざまな種類の「ＤＮＡ」鎖の構造およびヌクレオチド間のリンクを示す。
【図３】ヌクレオチドおよびその相補体のストレージユニットにおける実装の実施の形態について、考えられる例を示す。
【図４】本発明の底４のエンコーディングと比較して種々の命数法間の対応表を示す。
【図５】本発明のエンコーディングによる２つのヌクレオチドの加算の演算に対応する表を示す。
【図６】先の図と同等であるが、減算についての表を示す。
【図７】減算について考えられる例の代表を示す。
【図８】図５および図６と同等であるが、乗算についての表を示す。
【図９】乗算について考えられる例を示す。
【図１０】本発明のエンコーディングによる単精度浮動小数点を表す表を示す。
【図１１】指数の種々の組み合わせの表を示す（固定、補数Ａ１、Ａ２、およびイクセス４４として）。
【図１２】倍精度浮動小数点の表現の表を示す。
【図１３】図３に示した基本的なストレージユニットの概略図を示す。
【図１４】先の図と同等であるが、より詳細な構成による概略図を示す。
【図１５】図１３および１４に示した揮発性および不揮発性メモリについて考えられるグループ化の構造の図を示す。
【図１６】グラフについて考えられる例の図を示す。
【図１７】経路の計算について考えられる実装を示す。
【図１８】有向および非重み付けのハミルトングラフの図を示す。
【図１９】ハミルトン経路のグラフの図を示す。
【図２０】ハミルトン経路問題を解く辺および頂点について考えられるグループ化に関する本発明の無機「ＤＮＡ」鎖を示す。
【図２１】先の図による頂点および辺のエンコーディングを示す。
【図２２】先の図の頂点および辺の詳細なエンコーディングを示す。
【図２３】考えられるすべての経路の解を有する本発明の無機「ＤＮＡ」鎖の集合を示す。
【図２４】本発明のシステムに適用される論理的半加算器の図を示す。
【図２５】ハミルトン問題を解くために並列的に辺の比較を行う、考えられる実装の図を示す。
【図２６】ハミルトン問題を解く本発明の実装の機能ブロック図を示す。
【図２７】ハミルトン経路を解く全回路を示す。
【図２８】重み付けハミルトン経路問題を解く第１の実装の機能ブロック図を示す。
【図２９】重み付けハミルトン経路問題を解く第２の実装の機能ブロック図を示す。
【発明を実施するための形態】
【００３９】
以下に、この明細書のよりよい理解を助けるとともに、この明細書の一体部分を形成する一連の図面が添付され、そこには、例示であって本発明を限定するものではない性質で、本発明の対象が示されている。
【００４０】
以下で、上述の図面に基づいて本発明を説明する。
【００４１】
これまでにすでに述べたように、染色体は、「ＤＮＡ」およびたんぱく質によって形成される。次に、「ＤＮＡ」は、４つの種類に分類されるヌクレオチドのストランドまたは鎖で構成される。４つの種類は、アデニン（Ａ）、グアニン（Ｇ）、シトシン（Ｃ）、およびチミン（Ｔ）である。
【００４２】
「ＤＮＡ」は、リンクした２本のストランドで構成されており、各ストランドが、無数のヌクレオチドを含んでいる。同じストランドにおいては、相補的なヌクレオチドは存在せず、すなわち、いかなる制限もなくリンクすることができる。一方で、２本のストランドのリンクにおいては、相補性の制約が存在し、１つのストランドのアデニン（Ａ）は、相補的なストランドのチミン（Ｔ）とだけリンクすることができ、もう１つの可能なリンクであるグアニン（Ｇ）およびシトシン（Ｃ）についても同じである。このストランドの構成ゆえに、ＤＮＡのエンコーディングは、無作為であることはできず、あらかじめ定められた構造をとらなければならない（図１を参照）。
【００４３】
エンコーディングが、各ヌクレオチドについて、後のセクションで詳しく説明される染色体の有機的挙動をモデル化するように設計され、以下に、このエンコーディングの列挙部分が提示される。
・アデニン（Ａ）に、「００」という値が割り当てられる。
・グアニン（Ｇ）に、「０１」という値が割り当てられる。
・シトシン（Ｃ）に、「１０」という値が割り当てられる。
・チミン（Ｔ）に、「１１」という値が割り当てられる。
【００４４】
ひとたびヌクレオチドがエンコードされると、実行されたエンコーディングに続いて、次の段階は、電子回路（例えば、ヌクレオチドまたは状態を保存する、双安定のまたは他のデバイス）による物理的なレベルでの実装、ならびにストランド内のそれらの物理的構造およびストランド内のそれらと相補的なストランドとの関係および複数の相補的なストランドとのそれらの関係の確立である。最初に提案されたアイデアは、４つの等しい部分に分割された回路であった。回路の各部分が、そこに保存された異なるコンポーネント間の干渉を引き起こすことがないように、絶縁材料によって他の部分から分離されている。他方で、回路の各部分に、特定の無機ヌクレオチドをエンコードするコンポーネントが配置される。これにより、異なるヌクレオチド間に許される接続によって、人工ストランドの位置に所定のヌクレオチドを自由に選択することができる。
【００４５】
ストランドの長さは、スタックの形態に配置され、有機構造（染色体）のエミュレーションを可能にする三次元のチップを生み出す回路の数に依存する。また、平面のレベルにおいても実行することができ、１つの技術別の技術の選択は、既存のリソースおよびプロジェクトの最終的なニーズに依存する。
【００４６】
ひとたび回路が４つのヌクレオチドでエンコードされると、各回路は、その上位の回路に直列の接続によって接続されなければならず、このようにして、ヌクレオチドのストランドまたは鎖が生成される。他方で、並列接続または相補的なストランドとのリンクは、異なるヌクレオチドの相補性の関係を念頭に置く必要があり、すでに述べた関係が考慮される。これらのリンクが、回路において論理コンポーネントによってエンコードされる。
【００４７】
このシステムが、ストランドのヌクレオチドを定め、組み合わせ回路または反転法によって、他方のストランドの相補的なヌクレオチドが速やかに得られる。これがスタックされた回路の各々に適用される場合、ストランド全体の定義を可能にする連鎖反応が生じる。これは、相補的でない２つのヌクレオチドがリンクすることができないため、平行リンク間の不一致を回避する。
【００４８】
他方で、直列または同じストランドのヌクレオチド間のリンクは、特定の位置によって実行され、すなわち隣接して実行され、すなわちシーケンシャルおよびランダムアクセスの両方を、特定のストランドへと行うことができる。このアクセスシステムおよび並列接続によって、ヌクレオチドの特定のペアをいつでもアクティブにすることができ、無数の組み合わせおよびさまざまな染色体を実現することができる。
【００４９】
この初期の手法は、回路の半分だけしか利用されず、使用されない回路の部分が存在するため、各操作において多くの情報を無駄にしており、すなわち、初期の手法は、静的な形態の４つのヌクレオチドで回路を形成しており、このような方法で所定のヌクレオチドが選択される場合、相補的なストランドのヌクレオチドが同じ回路においてアクティブにされる。この初期の手法において、同じレベルのヌクレオチドが同じ回路に存在し、それらが２つのうち、一方のアクティブ化によってアクティブにされることを、示しておかなければならない。したがって、１対のヌクレオチドが構成されるとき、回路リソースの半分が無駄になり、この理由で、より動的な手法が考案され、ヌクレオチドが回路においてあらかじめ定められず、所定の入力に基づいて、１つの所定のヌクレオチドまたは別のヌクレオチドが得られる。
【００５０】
この新しい手法によれば、回路のヌクレオチドが２つになり、動的になり、すなわち所定の入力に依存することに加えて、ヌクレオチドの所定の種類が生成される。この低減は、４つの部分からなる回路から２つの部分からなる回路への移行であるため、回路リソースがより有効に使用されることを意味する。この全体の簡単化は、ヌクレオチドの構造に影響しない。なぜならば、動的でなければならないがゆえに保存される値は加えられる入力に依存するが、依然として２つの双安定または同等の電子コンポーネントで構成されるからである。
【００５１】
この新しい設計によれば、スタック構造が図１に見られるような完全ならせん形構造になる。したがって、この手法は、回路および回路の使用を簡単にし、さらには、製造段階において、製造コストならびにデジタルおよび電子リソースの使用が大幅に削減され、空間およびコンポーネントがより有効に使用される。
【００５２】
染色体の無機の接続が、２つのきわめて重要な部分に分割される。すなわち、所定のヌクレオチドが同じ種類または別の種類の別のヌクレオチドとつながることができる直列接続と、他方では、ストランドの所定のヌクレオチドがその相補体にだけつながることができ、または何ものにもつながらない並列接続である。したがって、ストランドが、その接続またはリンクをすべて有する場合、ストランドが完全であると称される一方で、ヌクレオチドのうちの１つが、その相補体との対応を有さない場合、ストランドは不完全である。この特徴が、相補的なストランドのヌクレオチド間の並列接続を設計するときに考慮される。なぜならば、一方のヌクレオチドのアクティブ化において、それが、相補的なヌクレオチドのアクティブ化が生じるかどうかをそこへ示すからである。この手順によって、すべてが同じ特徴およびヌクレオチドのすべてのペアを有するのではないため、任意の染色体構造がエミュレートされる。
【００５３】
ＤＮＡの鎖について考えられる組み合わせを説明するために、図２が、生じうる組み合わせを示す。これらの構造が、ＮＰまたはＮＰ完全などの複雑な問題を実行できるよう、ＤＮＡ鎖による操作の実行を可能にする。上述したように、本発明は、ヌクレオチドペア間に存在する関係ならびに同じストランドのヌクレオチド間および相補的なストランドのヌクレオチド間に存在しうるすべてのリンクに基づいている。
【００５４】
図３は、上述の説明に合わせて調節された実装の例を表しており、ストレージユニット１が、４つのＤ型の双安定回路２によって具体化されており、上方の２つの双安定回路が、ヌクレオチドのエンコーディング用として設けられており、下方の２つの双安定回路が、その相補体のエンコーディング用として設けられている。
【００５５】
例えば、図３のような実装を仮定すると、上方のヌクレオチド（不完全なストランド）の使用だけを望む場合に、図３のＳＥＬ０信号がアクティブにされ、この方法で、入力／出力（Ｉ／Ｏ）信号が、上方のヌクレオチドの双安定回路２への保存が望まれる値の確立を可能にする。代わりに、上方のヌクレオチドだけがアクティブにされる場合、図３のＳＥＬ１信号および（Ｉ／Ｏ）信号が、同じ方法で、下方のヌクレオチドの双安定回路における値の確立を可能にする。
【００５６】
対照的に、２つのヌクレオチドがアクティブにされること（完全なストランド）が望まれる場合、ＳＥＬ０およびＳＥＬ１信号がアクティブにされ、（Ｉ／Ｏ）信号によって、一方のヌクレオチドの値が確立される一方で、他方のヌクレオチドは、ＸＯＲポートの使用によってアクティブにされる。このヌクレオチドのペアの設計によれば、相補的なストランドのヌクレオチド間の考えられるすべての組み合わせを実現することができ、したがって、有機染色体の考えられる組み合わせの挙動をエミュレートすることができる。
【００５７】
ストレージユニット１の論理ポートによって、実際の回路内のリンクをエンコードすることができ、同様に、書き込み／読み出し信号（Ｗ／Ｒ）によってそれらの値を確立することができる。
【００５８】
このストレージユニット１の概略図が、後述されるとおり図１３および１４に示されている。
【００５９】
「ＤＮＡ」ストランドを形成する２つのヌクレオチドで構成されるベース４における計算システムのエンコーディングも提供される。この新たなシステムは、本発明においてＣｏｄ−ＩｎＣｈｒｏＳｉｌ（シリコン基盤の無機染色体の成文化）と称され、動作においてＤＮＡストランドの固有の特性を使用できることに加えて、現在の数値システムの精度を高める可能性を提供する。
【００６０】
本発明のベース４の計算システムは、「ＤＮＡ」ストランドのヌクレオチドＡ、Ｇ、Ｃ、およびＴをシンボルとして使用する。従来は、有機「ＤＮＡ」のエンコーディングは、ストランドまたは部分をエンコーディングすることか、または動作をそのオペランドでエンコーディングするか、巨視的に知られている。これらのエンコーディングは、実行することができる組み合わせの数を制限するため、あまり柔軟性を可能にしない。この理由で、本発明は、ＤＮＡが微視的に、すなわちＤＮＡストランドを形成するヌクレオチドレベルで、エンコードされる計算システムで構成される。このアトミック性の特徴が、数量の表現に必要な可能性およびスケーラビリティを有する計算システムを生成する組み合わせの実行を可能にする。ヌクレオチドのエンコーディングが、０〜３という１０進法の量をとる２ビットのシーケンスとして定義される。我々の提示するこの計算システムは、数値の鎖におけるシンボルの位置および値によって形成される多数の数値表現の形成を可能にし、この数値システムが位置的であるとともに、シンボルが２つの意味を有しており、それらが、一方では数値の鎖における位置であり、他方ではシンボルが受ける値であることを強調することができる。両方の情報の組み合わせにより、表現が望まれる数値量の最終値の一部を生成することができる。図４が、本発明の我々の計算システムと、現在使用されている残りの計算システムとの間の対応を示す。
【００６１】
例が、常に一式の言葉よりも明確であり、その理由で、１０進法ベースの４５６７１０という数を考える場合、対応する２進法表現は０００１０００１１１０１０１１１２であり、８進法では０１０７２７８であり、１６進法では１１Ｄ７１６であり、最後に、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌエンコーディングではＡＧＡＧＴＧＧＴ４である。数字の数が２つの値を有しており、一方では数字としての固有の値を有し、次いで位置の値を有する数字の多項式展開（計算の基本定理）を使用する数値システムからの変更も可能であり、この方法で変更方程式が以下のように決定される。
ｎｏ（Ｘｎ−１．．．．Ｘ２Ｘ１Ｘ０）ｂ＝Ｘｎ−１ｂｎ−１＋．．．．．＋Ｘ２ｂ２＋Ｘ１ｂ１＋Ｘ０ｂ０
【００６２】
例えば、我々は、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌでエンコードされた以下の数ＡＧＡＧＴＧＧＴ４を有し、１０進数は以下のとおりである。
ＡＧＡＧＴＧＧＴ４＝Ａ・４７＋Ｇ・４６＋Ａ・４５＋Ｇ・４４＋Ｔ・４３＋Ｇ・４２＋Ｇ・４１＋Ｔ・４０＝０・４７＋１・４６＋０・４５＋１・４４＋３・４３＋１・４２＋１・４１＋３・４０＝４５６７１０
【００６３】
１０進数のＣｏｄ−ＩｎＣｈｒｏＳｉｌエンコーディングへの逆演算。１０進数が１８９１０であるとすると、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌ数は、以下のとおりである。
１８９  ｄｉｖ  ４＝４７→ｍｉｎｕｓ（１８９．４）＝１→Ｇ
４７  ｄｉｖ  ４＝１１→ｍｉｎｕｓ（４７．４）＝３→Ｔ
１１  ｄｉｖ  ４＝２→ｍｉｎｕｓ（１１．４）＝３→Ｔ
２  ｄｉｖ  ４＝２→ｍｉｎｕｓ（２．４）＝２→Ｃ
１８９１０＝ＣＴＴＧ４
【００６４】
例を示す。数字８７３．８７５１０を、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌに変更したいと仮定すると、メカニズムは次のとおりである。
・整数が、先の例のようにＴＧＣＣＧと計算される。
・０．８７５×４＝３．５→整数は３であり、したがってＴである。
・０．５×４＝２→整数は２であり、したがってＣである。
・最後に、小数部はゼロであり、したがって最終的な数字は、ＴＧＣＣＧ，ＴＣ４である。
【００６５】
一般的にいうと、命数法において、数値量を以下の方法、すなわちＮｂ＝［ａｎ−１ａｎ−２ａｎ−３．．．ａ３ａ２ａ１ａ０，ａ−１ａ−２ａ−３．．．ａｋ］ｂであらわすことができ、ここで、ｎ＋ｋは、数字の桁の量を示しており、次いで、ｎが、整数の桁数を示す一方で、ｋは、小数を表す。最後に、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌ命数法の使用が、現在の命数法と互換であることを示しておかなければならず、この証明は、１０進法からＣｏｄ−ＩｎＣｈｒｏＳｉｌへの移行およびＣｏｄ−ＩｎＣｈｒｏＳｉｌから１０進法への移行を有する先の段落に見つけることができる。
【００６６】
すべての命数法は、そのオペランド間の計算を可能にするために、ルールおよび演算を必要とする。この理由で、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌにおいては、通常のそれ、すなわち加算、減算、乗算、除算、などが考慮される。最初に、多数の数学的計算において非常によく使用される演算であるという事実ゆえに、加算が定義される。加算は、一式の数字およびその構造（ベクトル、集合、など）について定められる算術演算である。本発明において、加算は、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌにエンコードされた数についての演算として定義される。周知のとおり、加算は、本発明において適用できる特徴的な種々の特性を有している。それらは、オペランドの順序によって結果が変わることがないスイッチング特性、連合特性、中立エレメント、ならびに反対エレメントである。図５は、２つのヌクレオチドの加算についてのガイドラインを提示している。ベースが上回られたときに我々がそのフレーズを述べて１を繰り上げる１０進法の加算と同様に、この加算の演算においては、オーバーフローによって引き起こされる繰り上がりがやはり考慮され、このことを、表に２つのシンボル（そのうちの最初の１つが、生じたオーバーフローを表し、２番目が演算の結果を表す）を有するセルが存在している図５に見ることができ、すなわち、２つの数ＡＴＣＧＡＴＡおよびＴＡＧＣＣＡＡの加算が望まれると仮定した場合、繰り上がりは生じない。
計算または繰り上がり
ＡＴＣＧＡＴＡ    数１（１０進法では３６６０）
＋  ＴＡＧＣＣＡＡ    数２（１０進法では１２７０４）
−−−−−−−−−−−−−−−−−−−−−−−−−−
ＴＴＴＴＣＴＡ    結果（１０進法では１６３６４）
【００６７】
この他の例では、以下の数ＡＴＣＧＡＴＡおよびＡＴＣＴＴＴＣを有しており、この場合には、繰り上がりが生じる。
ＧＧＧＧＧ        計算または繰り上がり
ＡＴＣＧＡＴＡ    数１（１０進法では３６６０）
＋  ＡＴＣＴＴＴＣ    数２（１０進法では３８３８）
−−−−−−−−−−−−−−−−−−−−−−−−−−
Ｇ↑Ｔ↑Ｇ↑Ｇ↑Ａ↑ＣＣ結果（１０進法では７４９８またはＧＴＧＧＡＣＣ）
【００６８】
以下に定められる演算は、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌエンコーディングにおける減算である。減算は、加算と反対の算術演算として知られており、本発明の特定の場合には、２つのヌクレオチド間の減算が、下記の図６のガイドラインに従って定義される。
【００６９】
図６に見られるように、２つのヌクレオチドの減算において引き起こされる繰り上がりが考慮に入れられており、その動機のために、加算の演算において行われたように、表（図６を参照）の同じセルに２つのシンボルが記入されており、第１のシンボルがオーバーフローまたは繰り上がりを指しており、第２のシンボルが結果を指している。このエンコーディングによって減算がどのように機能するかを見るために、この演算について明確な例が示されている。Ｃｏｄ−ＩｎＣｈｒｏＳｉｌにおける以下の数ＴＧＡＴ４（１０進法では２１１）およびＧＣＣＣ４（１０進法では１０６）について、減算の結果は、１０進法においては１０５であり、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌにおいてはＧＣＣＧ４であり、計算が、図７に定められている減算によって実行される。
【００７０】
図７に見られるように、Ｔ−Ｃ＝Ｇが減算されるとき、繰り上がりは生じないが、Ａ−Ｃ＝ＧＣが減算される（数の次の数字）とき、結果はＣである。しかし、繰り上がりはＧであり、この量を次の数字に加えなければならず、この場合には、それはＣである。Ｔは、この加算の演算から得られる。次に、Ｇが、新たな結果（Ｔ）からの数１から減算され、ＧＣという値が生み出され、再び値Ｇによって繰り上がりが生じる。この繰り上がりが、数２の次の数字に加えられ、結果が、その数１の位置相同物と減算され、Ｇがもたらされる。観察されるとおり、メカニズムは１０進法における減算と同じであり、数１の数字が数２の数字よりも大きいとき、減算が実行されて、オーバーフローは生じず、しかしながら反対の場合には、数２の数字から数１の数字に向かっていくつ繰り上がりされるかが計算され、これが結果となる。次に、１単位が次の数字に加算され、両方の数字が同じ位置から減算される。また、減算を、一方が反対（この場合には、補数）を使用し、ヌクレオチドＧ（この表現形式は、後のセクションで説明される）の追加が加えられる２つの数の加算として確立することもできる。ＩｎＣｈｒｏＳｉｌにおいて述べたように、ＤＮＡ鎖は、相補性によって支配される２つのストランドによって形成され、すなわち、ストランドのヌクレオチドは、相補的なストランドの任意のヌクレオチドとリンクすることができるわけではなく、確立された相補体とだけ結び付くことができる。これにより、或る数がＤＮＡ鎖においてＣｏｄ−ＩｎＣｈｒｏＳｉｌでエンコードされる場合、それは、相補的なストランドにその相補体を自動的にエンコードする。このＤＮＡ鎖の固有の特性ゆえに、加算の演算をきわめて容易に適用することができる。なぜならば、この数の反対または補数をすでに有しており、この数がヌクレオチドＧによって加えられることだけが必要であるからである（２の補数と称され、この文書の後の行で詳しく説明される表現形式）。再び例に頼り、この命数法における減算の演算のさらに明確なビジョンを提示する。数字がＴＧＣＧ（１０進法では２１７）であり、これをＣＣＣＴ（１０進法では１７１）で減算したい場合、１０進法の減算は、以下の結果、すなわち４６（ＡＣＴＣ）をもたらす。この命数法において、以下の段階が加えられる。
・最初のオペランドは変更されない（ＴＧＣＧ）。
・第２のオペランドの補数がとられ、すなわち、ＡがＴへと変換され、その逆も然りであり、ＣがＧへと変換され、その逆も然りであり、この場合には、特にはＧＧＧＡである。
・Ｇが、点２からもたらされる数に加算される（ＧＧＧＧ）。
・第１のオペランドおよび点３の数が加算される。
・２つのオペランドからのヌクレオチドの最大数が選択され、これが演算の結果であり、この例ではＡＣＴＣである。
【００７１】
方程式の形態において、以下の形態が得られる。すなわち、Ｒｅｓｏｌ  Ｓｕｂｔｒａｃｔｉｏｎ＝Ｏｐｅｒａｎｄ１４＋Ｃｏｍｐｌｅｍｅｎｔ（Ｏｐｅｒａｎｄ２４）＋Ｇ４）であり、ここで、Ｒｅｓｏｌ  Ｓｕｂｔｒａｃｔｉｏｎは、減算の結果であり、Ｏｐｅｒａｎｄ１４は、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌエンコーディングにおける第１のオペランドであり、Ｏｐｅｒａｎｄ２４は、Ｏｐｅｒａｎｄ１４と同じエンコーディングにおける第２のオペランドであり、最後に、Ｇ４は、ＤＮＡストランドのヌクレオチドＧの文字を表す。他方で、それは、相補関数を、∀ｘ，ｙ∈｛Ａ，Ｇ，Ｃ，Ｔ｝であり、∃１つのｆ、相補間数、ｆ：｛Ａ，Ｇ，Ｃ，Ｔ｝→｛Ａ，Ｇ，Ｃ，Ｔ｝であるように、単射関数として定め、ここでｆ（ｘ）＝ｙ，ｘ≠ｙ，ｙは、ｘの相補的なヌクレオチドである。
【００７２】
以下に定められる演算が、乗算である。乗算または積は、連続する加算が実行される算術演算として定められる。先の演算と同様に、ヌクレオチドレベルでの乗算について、ガイドラインが提示され、これらの積が、図８に観察される。
【００７３】
以下の数ＧＴＴＧ（１０進法の１２５）およびＧＧＡ（１０進法の２０）を有する場合、両者の積は、図９に示されるとおりである。観察されるとおり、ヌクレオチドの積が鎖全体について実行され、１０進法の積において生じるような連続する加算が生成される。先の演算は、部分加算における繰り上がりを考慮に入れているが、それらは表されておらず、理由は、先の積の表現における情報のグラフィックの過負荷であることが、強調されなければならない。さらに、オーバーフローまたは繰り上がりを引き起こす２つのヌクレオチドの加算ゆえに、繰り上がりの量が次のヌクレオチドに加えられることが、加算の定義において説明されていた。
【００７４】
最後に、さらに除算の算術演算を定義しなければならない。除算は、１０進法の場合と同じに実行される（同じメカニズムを有する）が、１０進法のそれと異なり、減算および乗算が、この文書において定義された減算および乗算操作のそれぞれによって実行される。例えば、以下のＣｏｄ−ＩｎＣｈｒｏＳｉｌの数、すなわち割られる数としてのＡＧＡＡＣＧＡ（１０進法では１０６０）、および割る数としてのＴＧＡ（１０進法では５２）を仮定する。演算の実行後に、除算の商は、１０進法では２０（Ｃｏｄ−ＩｎＣｈｒｏＳｉｌではＧＧＡ）であり、余りは、やはり１０進法の２０（Ｃｏｄ−ＩｎＣｈｒｏＳｉｌではＧＧＡ）であり、この方法で、ＡＧＡＡＣＧＡ＝ＴＧＡ・ＧＣＡ＋ＧＣＡ（割られる数＝割る数×商＋余り）である。
【００７５】
最後に、この命数法Ｃｏｄ−ＩｎＣｈｒｏＳｉｌにおいて、あらゆる種類の演算を、既存のシステム（２進法、８進法、１６進法、など）と同様に実行できることを、示しておく必要がある。この特徴が、他の数値システムへの移行の大きな可能性とともに、より容易にＤＮＡストランド上の情報によって働くことを可能にし、それらによって演算を実行することを可能にするが、そのようなことは、これまでには考えられなかった。この理由で、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌ命数法は、ＩｎＣｈｒｏＳｉｌに関連するすべての技術および本発明へのサポートとして機能することに加え、ＤＮＡストランドに含まれる情報の操作および使用のための選択肢として提示される。
【００７６】
他方で、浮動小数点表示が実数の表現方法であり、特性が、整数を実数の小数部（分数）から分離するエレメントである小数点の浮動または移動であることが、述べられなければならない。反対に、小数部に属する桁の数および整数に属する桁の数があらかじめ定められている固定小数点表示法が存在する。これらの浮動小数点表示法は、命数法が大きな数量を表すことを可能にする。これが、この浮動小数点形式が大きな数を表すために広く使用されている理由である。わかりやすい例が、ＩＴの分野に見つけられ、この形式の表現が、後に数学的に取り扱うことができるきわめて大きな数値表現の保存に使用されている。他方で、すべての浮動小数点の数は、以下の式に要約することができる確立されたパターンに従う。すなわち、ｒ＝ｍ・ｂｅであり、ここで、ｒは、実数であり、ｍは、仮数であり、ｂは、底であり、最後にｅは、底のべき乗を可能にする指数である。例えば、固定小数点における０．０００１２３１０という数（１０進法を使用）は、浮動小数点において、以下の表現を有することができる。すなわち、１．２３  １０−４、０．１２３  １０−３、０．０１２３  １０−２、０．００１２３  １０−１、などである。先の表現において観察されたとおり、すべては同じ数を、浮動小数点において異なる表現で指している。この理由、および数量の表現における曖昧さを避けるために、浮動小数点数の同種の表現を可能にする基準が確立されている。この基準は、先の世紀（より具体的には、１９８０年代）に、ＩＥＥＥ７４５という規格名でＩＥＥＥへと提示されている。この基準は、ゼロおよび非正規化値（無限大およびＮＡＮ）など、数量について幅広い範囲の表現形式を定めることを可能にする。他方で、浮動小数点演算と呼ばれるこの形式において実行することができる一式の演算も定められている。この基準において、使用することができるビットの数は、数の表現によって得ることができる精度に関係しており、より多くのビットが使用される場合、精度がより高くなり、表現の範囲がより広くなる。これは、２つの大きなグループの区別を可能にするが、両方の拡張が、文献に存在している。その第１は、表現に３２個のビットを使用する単精度のそれである。これら３２個のビットが、数字を特定する３つの部分に分配される。他方で、表現においてより大きな容量を呈し、２倍の６４個のビットで構成されているこの基準の別の形式もあり、その名前は、倍精度である。その弟分と同様に、この形式におけるビットは、数を特徴付けおよび特定する３つの部分またはフィールドに分配される。以下の行で、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌ命数法における浮動小数点表示法を説明する。すでに述べたように、それは、数量をわずか４つのシンボル、すなわちＤＮＡストランドを構成するヌクレオチドで表現することを可能にする命数法である。しかしながら、現在の命数法と同様、大きな数量を表すためには、多数のシンボルが必要とされる。すでに観察されたとおり、浮動小数点形式の柔軟性はきわめて重要であり、その理由で、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌでのエンコーディングによってきわめて大きい数を表すことを可能にする浮動小数点形式を確立することが考慮されている。ＩｎＣ���ｒｏＳｉｌシステムにおいてこのエンコーディングを使用する場合、一方では、きわめて大きい数を表す可能性が存在し、他方では、保存されるこの数についての情報が増加することが見つけられる。なぜならば、或る数がこの形式で表されるとき、それと相補的または反対の数も保存されるからである。これは、両方の数を必要とする数学的演算の大幅な簡単化を可能にする。以下の段階は、どのようにしてこの形式をＩｎＣｈｒｏＳｉｌシステム、要するにＤＮＡによって提供されるこの特性を使用できるように確立できるかであり、どのように浮動小数点表現形式がＣｏｄ−ＩｎＣｈｒｏＳｉｌでエンコードされた数について定められているかを説明する応答が以下の行に見つけられる。本発明は、浮動小数点表現について２つの大きな精度を定義することができ、一方では、その表現に２０のヌクレオチドを有しているとして定義されている単精度形式が存在し、文書のこの部分において小さな余談を形成し、読者が先の行においてよく理解しているとおり、ビットの表現の長さの定量化については述べず、ヌクレオチドの表現の長さの定量化について述べる。フォーマットの説明を続けると、２０のヌクレオチドが、単精度フォーマットを確立するために使用される。このフォーマットにおいて、２０のヌクレオチドは、後述される６つの部分またはフィールドにシェアまたは分配され、６つのうちの２つの部分が、２つのストランドのうちのどちらが指数および仮数をそれぞれ表現または定義するために使用されるかを確立するために投入される。異なる部分が、ヌクレオチドの長さ、どの部分を選択すべきかを決定することができるために十分な情報を有している。例えば我々が、ヌクレオチドＡが指数の前の部分に現れる表現を見つける場合、それは、必要とされる指数が上側のストランドにあることを示しており、対照的に、Ｔのヌクレオチドが見つけられる場合、それは、指数が下方のストランドによって表されることを示す。位置のこの集合によって、種々の組み合わせを、同じ数の表現において実行することができ、大幅に簡単化された数学的演算が可能である。指数および仮数で表現されるエンコーディングの種類の指定の機能を有する浮動小数点表現フォーマット内の別の２つの部分が存在する。４つの種類のエンコーディングを、このフォーマットについて考慮することができ、それらは、以下の列挙に提示されるそれらである。
・マグニチュードサイン（この部分においてＡの値をとる）。整数の我々の手書きを模倣するマグニチュードサインと呼ばれる符号を有する整数の表現フォーマット、１つの部分に符号、次いで数の大きさ。例えば、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌではＧＡＡＣ４である数−３４１０、負の符号がＣとしてエンコードされると考えられ、対照的に、Ａによって正の符号であると考えられる場合、我々の例の数は、以下のＣＧＡＡＣである。
・１の補数（セクションにおいてＧの値をとる）。それは、以下の式ＮｂＣａ１＝ｂｎ−Ｎｂで１の補数を定め、ここで、ＮｂＣａ１は、数の１の補数における数であり、Ｎｂが、Ｎ４＝ＣＣＴＡＡＡＧである場合、その１の補数は、Ｎ４Ｃａ１＝４７−ＣＣＴＡＡＡＧ＝ＧＡＡＡＡＡＡＡ−ＣＣＴＡＡＡＧ＝ＧＧＡＴＴＴＣである。
・２の補数（セクションにおいてＣの値をとる）。ひとたび１の補数が計算されると、２の補数を得ることは容易であり、したがって、２の補数の計算は、以下の式ＮｂＣａ２＝ｂｎ−Ｎｂ＋１によると考えられ、したがって、先の例に従い、２の補数における数は、以下のＮ４Ｃａ２＝４７−Ｎ４＋Ｇ＝ＧＡＡＡＡＡＡＡ−ＣＣＴＡＡＡＧ＋Ｇ＝ＧＧＡＴＴＴＴである。
・イクセスＮ（Ｔの値をとる）。イクセスｎは、以下の形態ＮＥｘｃｅｓｓ４＝Ｎ４＋（Ｎ−１）の式である。
【００７７】
要約すると、これらのセクションが、エレメント（指数または仮数のそれぞれ）がどこにあるか、エンコーディングを指定し、すなわち、指数または仮数の前のヌクレオチドが例えばＧという値を有する場合、このことは、指数または仮数が補数Ａ１にエンコードされていることを示す。最後に、これらのセクションの長さが、使用すべきストランドを決定するセクションと同じく、ヌクレオチドの長さであることが示されなければならない。単精度浮動小数点フォーマットを形成するセクションの説明を完結できるために、それは、１ヌクレオチドの長さを有し、それが表す数の符号を知ることを可能にする符号セクションに言及し、すなわち、このセクションにヌクレオチドＡを有することが、数が正であることを意味し、対照的に、ヌクレオチドＴを有する場合には、数が負である。さらに、４ヌクレオチドの長さを有する指数のセクションが存在する。最後に、１１のヌクレオチドの長さによって表現フォーマットを形成する２０のヌクレオチドを完結させる仮数のセクションが存在する。図１０が、２０のヌクレオチドを有する単精度浮動小数点フォーマットが分割される種々のセクションを、一般的かつ図式的に示す。
【００７８】
先のフォーマットにおいて、指数を、以下の列挙に提示される以下の値の範囲において実現できる。
・符号を有する固定小数点、ｘが指数である場合、ｘ∈［−１２７，０］∪［０，＋１２７］。
・補数Ａ１、ｘが指数である場合、ｘ∈［−１２７，０］∪［０，＋１２７］。
・補数Ａ２、ｘが指数である場合、ｘ∈［−１２８，０］∪［０，＋１２８］。
・イクセス４４、ｘが指数である場合、ｘ∈［−１２８，０］∪［０，＋１２８］。
【００７９】
図１１が、指数が引き受けることができる種々のエンコーディングを示す。その種々の関係も、同意された演算または目的に応じて使用することができる二重ストランド特性に加えて、種々のエンコーディングシステムにおいて観察することができる。
【００８０】
他方で、仮数は、１１のヌクレオチドで構成されると解され、この方法で、以下の成文化によって得ることができる範囲は、以下のとおりである。
・符号を有さない固定小数点、ｍが仮数の場合、ｍ∈［−４１１−１，０］∪［０，４１１−１］。
・補数Ａ１、ｍが仮数の場合、ｍ∈［−４１１−１，０］∪［０，４１１−１］。
・補数Ａ２、ｍが仮数の場合、ｍ∈［−４１１，０］∪［０，４１１］。
・イクセス４１１。ｍが仮数の場合、ｍ∈［−４１１，０］∪［０，４１１］。
【００８１】
全体として、以下の数の範囲［−１７５９２１８６０４４４１６・１０１２７，０］∪［０，１７５９２１８６０４４４１６・１０１２７］に含まれる数を、この単精度浮動小数点表示フォーマットによって達成することができる。我々は、ＩＥＥＥ７４５フォーマットについてすでに使用した例によって、単精度フォーマットの説明を完了させる。数が−１１８，６２５１０で、その単精度のＩＥＥＥ７４５でのエンコーディングが、３２ビットの２進数１１００００１０１１１０１１０１０１００００００００００００００であることを思い出されたい。したがって、本発明の我々の単精度浮動小数点システムを使用し、以下のエンコーディングが得られる。
ストランド１：Ｔ  ＡＴ  ＣＡＧＧ  ＡＡ  ＡＧＣＣＣＡＡＡＡＡＡ
ストランド２：Ａ  ＴＡ  ＧＴＣＣ  ＴＴ  ＴＣＧＧＧＴＴ  Ｔ  ＴＴＴ
【００８２】
観察できるとおり、第１の数は負であり、その理由で、最初のヌクレオチドがＴとしてエンコードされており、次のヌクレオチドが、指数がストランド１において表現されており、そのエンコーディングが１２８を超えることを示す。仮数に関しては、符号を有さない固定小数点において表されており、ストランド１に対応する。
【００８３】
以下の浮動小数点表示フォーマットが、４０のヌクレオチドまたは２０のヌクレオチドからなる２つのストランドを使用した倍精度である。倍精度表示フォーマットは、指数および仮数のセクションにおいてヌクレオチドの数が増やされている点を除き、単精度のそれと同じである。図１２が、４０のヌクレオチドについて、倍精度表示フォーマットを図式的に示す。
【００８４】
指数が許すことができる値の範囲は、以下の列挙によって定められるであろう。
・符号を有する固定小数点、ｘが指数である場合、ｘ∈［−４７−１，０］∪［０，４７−１］。
・補数Ａ１、ｘが指数である場合、ｘ∈［−４７−１，０］∪［０，４７−１］。
・補数Ａ２、ｘが指数である場合、ｘ∈［−４７，０］∪［０，４７］。
・イクセス４７、ｘが指数である場合、ｘ∈［−４７，０］∪［０，４７］。
【００８５】
仮数の場合には、この倍精度浮動小数点フォーマットで表すことができる値の範囲は、以下の列挙に示されているそれらである。
・符号を有さない固定小数点、ｍが仮数の場合、ｍ∈［−４２８−１，０］∪［０，４２８−１］。
・補数Ａ１、ｍが仮数の場合、ｍ∈［−４２８−１，０］∪［０，４２８−１］。
・補数Ａ２、ｍが仮数の場合、ｍ∈［−４２８，０］∪［０，４２８］。
・イクセス４２８、ｍが仮数である場合、ｍ∈［−４２８，０］∪［０，４２８］。
【００８６】
指数と仮数との間のさまざまな組み合わせを形成することによって、この数値範囲∈［−７２０５７５９４０３７９２７９３６・１０６５５３６，０］∪［０，７２０５７５９４０３７９２７９３６・１０６５５３６］に含まれるこの倍精度浮動小数点フォーマットを有する数を得ることができる。
【００８７】
上述のストレージシステム１は、本発明がＭｅｍ−ＩｎＣｈｒｏＳｉｌ（シリコンに基づくメモリ無機染色体）と呼んでいる２つの種類であってもよい。本発明は、揮発性および不揮発性メモリを使用することができる。実現された揮発性メモリは、ＩｎＣｈｒｏＳｉｌアクセスメモリ（ＩＡＭ）と呼ばれている。この種類のメモリは、揮発性であるという特徴を有する他に、構造化されたアクセスという特性を有しており、この方法で、我々は、後にヌクレオチドを指定するために、ストランドにおけるあらかじめの位置の特定によってヌクレオチドにアクセスする。本発明の揮発性メモリは、それに保存された情報の書き込みおよび読み出しを可能にする。このメモリは、揮発性であり、すなわち、電気エネルギーから切り離されると、情報が失われる。この理由のため、この種類の一時メモリは、通常は、恒久的でない中間結果またはデータを保存するために使用される。この種類のメモリのために設計されたアクセスは、構造化されており、すなわち、このメモリのデータの取得が望まれる場合、機能は以下のとおりである。メモリの無機ＤＮＡ鎖（または、ＩｎＣｈｒｏＳｉｌとも称される）が選択される。ひとたび無機ＤＮＡ鎖が決定されると、探している情報を含んでいるストランドが選択されるが、メモリのために開発された無機ＤＮＡ鎖が、それらの有機同族体と同様に２つのストランドで構成されていることを示しておかねばならない。これら２つの位置が特定された前提によって、以下の点が、どのヌクレオチドまたはヌクレオチドグループにアクセスしたいかを判断するためのものであるが、ユーザが、あらかじめ位置が特定された無機ＤＮＡ鎖の一部分または全体に同時にアクセスを望む場合も生じうる。我々が揮発性メモリシステムのために実現したこの三次元のシステムにおいて、この文書において説明される基本的な技術（ＩｎＣｈｒｏＳｉｌ）が使用されており、それは、揮発性メモリの製造のために、既存の技術に容易に組み込むことが可能である。他方で、この構造化の特徴は、本発明のメモリシステムを、進歩的かつ新規にする。なぜならば、主および相補のいずれかのストランドというさらなる次元が考慮されており、揮発性メモリのこれまでのシステムでは、行および列という二次元しか考慮されていないからである。本発明の他の特徴は、行または列として無機ＤＮＡ鎖を考えることができる点にあり、すなわち、メモリを管理するシステム（ＩＡＭ）が、ＤＮＡ鎖がどのようにメモリに保存されるかを行または列によって規定できる点にある。このメモリシステム（ＩＡＭ）は、無機材料によって情報を有機ＤＮＡに保存できるという事実ゆえに、その遺伝的特徴によって区別される。したがって、既存の揮発性メモリまたはＲＡＭは、アクセスの形式ゆえに相違することに加えて、さらに、基本的なストレージユニットゆえに異なる。すなわち、ＲＡＭの場合には、ビットまたはビットグループであり、われわれのＩＡＭメモリの場合には、ヌクレオチドまたはヌクレオチドグループである。これらのメモリを、半導体と一緒に製造することができ、マイクロテクノロジまたはナノテクノロジによって回路に一体化できるという単純な理由で、メモリを必要とする現在のシステムまたはデバイスに統合することができる。これゆえに、これらのメモリを、種々のコネクタを有するモジュール２１にまとめることもできる。これらのコネクタは、メモリが接続された電子デバイスまたは基板に関してさまざまである。この方法で、無機遺伝的メモリが、同じ性質を有する構造に基づくこの構造によって生成され、この理由で、メモリアクセスは、有機ＤＮＡの実際の性質のリンク、分離、などの形態に本質的に起因して、ストランド全体にアクセスすることが、特定のヌクレオチドのペアよりもはるかに興味深い。図１５において観察できるとおり、メモリシステムは、無機ＤＮＡ１２の鎖によって形成され、次いで、無機ＤＮＡ１２は、主たるストランドおよびもう１つの相補ストランドという２つのストランドによって形成されている。メモリのこれらのストランドが、これらのメモリの基本ストレージユニット１を表すヌクレオチドに分割される。したがって、この方法で、ヌクレオチドまたはヌクレオチドグループの位置の特定を望む場合、最初に無機ＤＮＡ鎖の位置を特定しなければならず、次いで、どのストランドに情報があるかが判断され、後に、各ストランドのどのヌクレオチドへのアクセスが望まれるかが確立される。図１３において、相補的である２つのヌクレオチドを含むこれらのＩｎＣｈｒｏＳｉｌユニットのうちの１つの仕組みが示されている。最後に、それらの遺伝的性質ゆえに、これらのメモリ（ＩＡＭ）を、軌跡の計算または重み付けグラフ（ハミルトン経路、ダイクストラ経路、オイラー経路、など）の解明の場合などのように、中間または最終演算を計算するために使用できると考えられるが、常に一時的な性格であることを示さなければならない。しかしながら、遺伝的エンコーディング、すなわちＤＮＡ鎖の表現による情報を必要とする任意の種類の情報へと拡張することも可能である。本発明のために実現されている第２のメモリは、本発明においてＩｎＣｈｒｏＳｉｌ読み出し専用メモリ（ＩＲＯＭ）と呼ばれる不揮発性メモリである。この種類の不揮発性メモリが含む情報は、読み出し専用であり、すでに述べたＩＡＭメモリと同様に、その基本ストレージユニットは、ヌクレオチドであり、したがって、それらのアクセスは、ＩＡＭと同様に構造化されている。
【００８８】
不揮発性メモリは、それらが読み出し専用メモリであるという特殊性を有している。ＩＲＯＭまたはすでに説明したＩＡＭメモリと同様のＩｎＣｈｒｏＳｉｌによる読み出し専用メモリは、図１５のような同じ構造を有しており、さらに、ＩＡＭメモリについて先に説明した同じアクセス構造を有しており、同様にこれが、現存のＲＯＭまたは不揮発性メモリから区別される因子である。しかしながら、このメモリは、その情報が読み出し専用であるという特性を有しており、したがって、静的な情報の生成を可能にするヒューズまたは他のシステムによって実現することが可能であり、ヌクレオチドがこのシステムにおいて焼かれ、または生成される場合、先のセクションで述べた反転法が、相補的なヌクレオチドを焼くこと、または生成することを可能にし、この方法で、図１４に示された機能に従うことができる。この図において、参照符号５は、一次情報を表しており、参照符号６は、この一次情報の反転であり、参照符号７は、得られる二次情報であり、参照符号８は、正しい機能を達成するために加えられる制御である。
【００８９】
最後に、我々は、この種類のメモリが、例えば我々の有機ＤＮＡの配列など、静的なままであることが望まれる情報を保存できるという事実ゆえに、多数の用途を有していることを、示さなければならない。すなわち、有機ＤＮＡをチューブまたはデバイスに保存しようと試みる研究が存在しているが、有機材料であるため、保存が困難であり、本発明の不揮発性メモリによれば、情報を恒久的に保存することができ、コンピュータまたは情報システムからのアクセスさえ可能である。他の用途は、ＩＲＯＭメモリによるＤＮＡデータベースの形成でありうる。ＤＮＡをソフトウェアによって従来の方法で保存するデータベースが存在するが、本発明のメモリによれば、この遺伝的情報の直接的な保存が可能である。要約すると、このＩＲＯＭメモリの用途または機能は、その使用が所望される用途に応じて、きわめて変化し、かつさまざまな目的のためのものであることができる。
【００９０】
上述の構成は、経路、フロー、およびネットワークの問題を、それらにグラフ理論の観点から取り組んで解くことを可能にする。
【００９１】
経路問題は、通常は、決定論アルゴリズム（妥当な時間）によって、ハードウェアの代わりにソフトウェアを使用して解かれる。このことは、システムが、考えられる近似解について現実ではなく予測のモデルを形成するデバイスを選択することを意味し、すなわち、市場において、例えば飲料配達人に、都市の各バーまたはレストランを１回で最適な形式で通る経路がどれかを伝えることができるデバイスは存在しない。この問題は、現在存在するデバイス、経路、経路ソフトウェア、などでは解くことができない。対照的に、解くことができれば、飲料メーカおよび配達人にとって、利益および時間の節約がそれぞれ存在するであろう。他の例は、ガス、電気、水、および電話会社による故障または異常の検出である。市場には、ＰＬＣ、センサ、ＧＩＳ、ＧＰＳ、などを使用する位置特定デバイスが存在するが、位置の特定および経路付けのレベルにおいて、それが、いくつかの場合にはソフトウェアによって実行され、他の場合には、完全に手動によって実行され、オペレータが、地理的領域の位置基準を使用して、考えられる故障を見つけなければならない。この理由で、位置を割り出して故障地点へと達する可能な最短経路を計算するデバイスのリアルタイムでの使用が、問題をより短時間で解決することができるため、会社の利害にとって決定的である。また、工業組織において、情報および工業プラントの機械類の分布をグラフに表すことができるため、機械類またはいくつかのプロセスおよび工業用機械を製造レベルにおいて最適化することができる。要約すると、技術および方法論を、現場における問題を解決するためにグラフ形式での表現へと軽減または概略化できるすべてのシステムへと適用でき、グラフのＤＮＡへのエンコーディングおよびＩｎＣｈｒｏＳｉｌ技術の使用が考慮される場合、先のセクションで述べたとおり、現在のシステムへと一体化でき、その再使用が完全であるデバイスを手にすることに加えて、これまでは解くことができていなかった問題を最適に解くことができる。以下で、上述の問題の多くの計算の要石である３つの問題を取り扱う。
・２点間の最短または最適ルートの見つけること
・巡回セールスマン問題を解くこと
・オイラー経路を達成すること
【００９２】
２点間の最短または最適ルートを見つける
グラフ理論の典型的な問題は、初期地点から最終地点までの最短または最適ルートを見つけることである。この問題に対して提示される手法は、有向グラフ、重み付け（正または負）、およびＩｎＣｈｒｏＳｉｌ技術によるＤＮＡの特徴の使用を考慮することである。この方法で、ＩｎＣｈｒｏＳｉｌ技術に基づくデバイスを使用して、最短または最適経路を見つけることが可能である。例を挙げると、隣接性のリストおよび集合論によって図１６の問題を解くことを考える。
【００９３】
図１６のグラフにおいて、（出発点、辺、到達点）という表現方法である隣接性のリストとして表すことが可能であり、したがって、グラフは以下のとおりになる。
ノード（ｓ）：｛（ｓ，ｘ１，ｕ），（ｓ，ｘ２，ｖ）｝
ノード（ｕ）：｛（ｕ，ｘ３，ｗ），（ｕ，ｘ７，ｖ）｝
ノード（ｖ）：｛（ｖ，ｘ５，ｔ）｝
ノード（ｗ）：｛（ｗ，ｘ４，ｖ），（ｗ，ｘ６，ｔ）｝
【００９４】
グラフ理論において、データ構造、隣接性のリストが、それに隣接するそれらすべての頂点ｊを含むリストを各頂点ｉへと関連付けることを可能にする構造として定められることを、強調しておかなければならない。このようにして、その上限において空間が節約され、加えて、グラフを、各成分がグラフの頂点の各々に対応する隣接性のリストになるｎ成分のベクトル（｜Ｖ｜＝ｎの場合）によって表現することができる。さらに、リストの各エレメントが、隣接する頂点を示すフィールドで構成される。他方で、グラフがラベル付けされている場合、ラベルの値を示す第２のフィールドの追加が必要であろう。
【００９５】
集合論を使用し、隣接性リストのすべてのエレメント、すなわちエレメント（頂点、辺、頂点）を有する集合を形成することができる。形成されたこの集合は、以下に列挙される前提を有するであろう。
・ｅ１およびｅ２など、その集合に属する２つのエレメントが存在する場合、ｅ１の最終成分がｅ２の最初の成分に等しいことが観察され、両方のエレメントが反応して、集合に属する新たなエレメントが生じる。
・最初および最後である成分を含む集合に属するエレメントが存在する場合、それらは今や解であるため、残りのエレメントと反応しない。
・反応する２つのエレメントが、正の比または１を有する一方で、反応しない２つのエレメントは、負の比または０を有する。
・最初の成分を有し、隣接性リストに属するエレメントは、ひとたび反応したならば、再び反応することはない。
【００９６】
Ｅがエレメントの集合であり、Ｃが成分の集合であることが既知である場合、反応が以下の演算であることを見ることができる。
∀ｘ∈Ｃ｜∃ｙａｘ，ｘｂｚ∈Ｅ、したがってｙａｘ∧ｘｂｚ≡ｙａｘｂｚ
ここで、ｙ，ａ，ｘ，ｂ∈Ｃおよびｙａｘｂｚ∈Ｅ
【００９７】
この場合、我々は、エレメント［ｉ］と称される隣接性リストに属するエレメントの集合を有し、したがって、集合は、最初は以下の形態のとおりである。
エレメント１：｛（ｓ，ｘ１，ｕ）｝
エレメント２：｛（ｓ，ｘ２，ｖ）｝
エレメント３：｛（ｕ，ｘ３，ｗ）｝
エレメント４：｛（ｕ，ｘ７，ｖ）｝
エレメント５：｛（ｗ，ｘ４，ｖ）｝
エレメント６：｛（ｗ，ｘ６，ｔ）｝
エレメント７：｛（ｖ，ｘ５，ｔ）｝
【００９８】
この初期の集合において、そのエレメントを分析することができ、集合に関連付けられたこれらの前提がどのように満足され、新たなエレメントが生成されるのかを見ることができる。この場合、エレメント１がエレメント３およびエレメント４と反応し、エレメント８およびエレメント９がそれぞれ形成されることを、見ることができる。また、エレメント２がエレメント７と反応し、今や解であるエレメント１０が形成されることを、見て取ることができる。この後で、集合は、以下のようになるであろう。
エレメント１：｛（ｓ，ｘ１，ｕ）｝［反応せず］前提４
エレメント２：｛（ｓ，ｘ２，ｖ）｝［反応せず］前提４
エレメント３：｛（ｕ，ｘ３，ｗ）｝
エレメント４：｛（ｕ，ｘ７，ｖ）｝
エレメント５：｛（ｗ，ｘ４，ｖ）｝
エレメント６：｛（ｗ，ｘ６，ｔ）｝
エレメント７：｛（ｖ，ｘ５，ｔ）｝
エレメント８：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ）｝
エレメント９：｛（ｓ，ｘ１，ｕ，ｘ７，ｖ）｝
エレメント１０：｛（ｓ，ｘ２，ｖ，ｘ５，ｔ）｝
【００９９】
続くラウンドにおいて、エレメント８がエレメント５と反応してエレメント１１を形成でき、エレメント８がエレメント６と反応してエレメント１２を形成でき、最期にエレメント９がエレメント７と反応してエレメント１３を形成することが、観察される。このラウンドにおいて、集合は以下のようになるであろう。
エレメント１：｛（ｓ，ｘ１，ｕ）｝［反応せず］前提４
エレメント２：｛（ｓ，ｘ２，ｖ）｝［反応せず］前提４
エレメント３：｛（ｕ，ｘ３，ｗ）｝
エレメント４：｛（ｕ，ｘ７，ｖ）｝
エレメント５：｛（ｗ，ｘ４，ｖ）｝
エレメント６：｛（ｗ，ｘ６，ｔ）｝
エレメント７：｛（ｖ，ｘ５，ｔ）｝
エレメント８：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ）｝
エレメント９：｛（ｓ，ｘ１，ｕ，ｘ７，ｖ）｝
エレメント１０：｛（ｓ，ｘ２，ｖ，ｘ５，ｔ）｝
エレメント１１：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ，ｘ４，ｖ）｝
エレメント１２：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ，ｘ６，ｔ）｝
エレメント１３：｛（ｓ，ｘ１，ｕ，ｘ７，ｖ，ｘ５，ｔ）｝
【０１００】
集合を観察すると、エレメント７と反応してエレメント１４を形成するエレメント１１のただ１つの反応だけが存在することを、見て取ることができる。この最期の理由で、集合は以下のようになる。
エレメント１：｛（ｓ，ｘ１，ｕ）｝［反応せず］前提４
エレメント２：｛（ｓ，ｘ２，ｖ）｝［反応せず］前提４
エレメント３：｛（ｕ，ｘ３，ｗ）｝
エレメント４：｛（ｕ，ｘ７，ｖ）｝
エレメント５：｛（ｗ，ｘ４，ｖ）｝
エレメント６：｛（ｗ，ｘ６，ｔ）｝
エレメント７：｛（ｖ，ｘ５，ｔ）｝
エレメント８：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ）｝
エレメント９：｛（ｓ，ｘ１，ｕ，ｘ７，ｖ）｝
エレメント１０：｛（ｓ，ｘ２，ｖ，ｘ５，ｔ）｝
エレメント１１：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ，ｘ４，ｖ）｝
エレメント１２：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ，ｘ６，ｔ）｝
エレメント１３：｛（ｓ，ｘ１，ｕ，ｘ７，ｖ，ｘ５，ｔ）｝
エレメント１４：｛（ｓ，ｘ１，ｕ，ｘ３，ｗ，ｘ４，ｖ，ｘ５，ｔ）｝
【０１０１】
結果が、エレメント１０、エレメント１２、エレメント１３、およびエレメント１４であることを、見て取ることができる。なぜならば、これらが最初および最期の成分を有しているからである。解または経路を見つけるこの先の手法の演算は、順次的に実行される。しかしながら、本発明の回路においては、並列形式で実行され、すなわち、本発明は２つの集合を考慮しており、第１集合Ｃ１が、最初の成分を含んでいるエレメントおよび最期の成分を含んでいないエレメントによって形成される。第２集合Ｃ２は、最期の成分を含んでいるエレメントおよび最初の成分を含んでいないエレメントによって形成される。両方の集合が、Ｃｏｄ−ＩｎＣｈｒｏＳｉｌによってエンコードされ、それぞれ別々のストランド１０に保存される。これらのストランドが、それらの成分を、比較器９を含む回路によってリンクして、図１７に観察されるような行列を形成し、この方法で、それらが並列形式で反応し、正（１）または負（０）としてエンコードされた反応の集合が得られる。これらの反応が、０および１からなる行列を形成する。したがって、２つの上述の集合を表しており、ＩｎＣｈｒｏＳｉｌストランドにエンコードされている２つの集合Ｃ１およびＣ２が存在する。他方で、我々は、集合Ｃ１およびＣ２のエレメント間の反応によって形成されるＣｒを有し、この方法で、反応が、ｅ２∈Ｃ２およびｅ１∈Ｃ１であり、
【数１】
2010535370.tif 000003
であり、
【数２】
2010535370.tif 000004
は反応であり、それがとることができる値が０または１である演算として再定義される。観察されるとおり、反応しなければならない新たなエレメントが反応において生成されることがなく、すべてが同時に反応し、行列において、反応が存在した場合または反応が正である場合が１によって示され、対照的に、反応が存在しなかった場合または反応が負であった場合がゼロによって示される。
【０１０２】
ひとたびすべてのエレメントの他のすべてのエレメントとの反応によって行列が得られると、この情報がバッファへと渡され、ソフトウェアまたは回路によって経路回復アルゴリズムが加えられるが、これはそれほど高コストではなく、多項式次数である。重み付けグラフが考慮される場合、重み付けをメモリ（Ｍｅｍ−ＩｎＣｈｒｏＳｉｌまたは他の種類のメモリ）に保存することができ、先のグラフの辺が、方向を含み、重みの値、なぜ大きな量を重み付けに使用できるのかの動機を含まず、方向が所定の長さを有する。ひとたび経路の辺が見つけられると、経路の総コストを得るためには、各辺のコストを足すことだけが必要である。次いで、総コストによって、経路を並べ替え基準に従って並べ替えることができ、これのすべてを、デバイスに接続される回路またはソフトウェアモジュールによって実行できる。この回路は、ダイクストラ、フロイド−ワーシャルおよびベルマン−フォード、ならびにフォード−フルカーソンのアルゴリズムにおいて提示される問題を、それらが負のコストなどを考慮できるため解決する。
【０１０３】
これらのシステムの利点は、既存のハードウェアシステムに容易に組み込むことができる点にある。なぜならば、どちらも電子および集積回路に基づいているからである。他方で、それは、既存の計算システムのためのハードウェアによる代案である。なぜならば、ソフトウェアシステムにおいて、それらは、機能するために別の環境（オペレーティングシステム、仮想マシン、など）を必要とするが、この装置は、ホストデバイスの回路へと直接的に接続されるからである。
【０１０４】
ハミルトン経路問題（Ｈａｍｉｌｔｏｎｉａｎ  ｐａｔｈ  ｐｒｏｂｌｅｍ）の解法
現在のコンピューティングシステムは、先の世紀の中頃にジョン・フォン・ノイマン（Ｊｏｈｎ  Ｖｏｎ  Ｎｅｕｍａｎｎ）によって確立されたシーケンシャル技術に基づいている。これらのシーケンシャルコンピュータは、数学的問題を解くことに長けているが、正しい解が見つけられるまですべての可能な解を探さなければならないいわゆるターンキー問題については困難を抱えている。これは、問題の計算時間が、指数関数的または対数的になることを意味する。
【０１０５】
これらの問題を、計算時間を少なくすることができる並列コンピュータの構成によって軽減することが、試みられてきた。これらの解決策は、通信および互いに接続されるノードの数において、多くのリソースを消費する。その動機のため、１９９４年の中頃に、アドルマンが、有機ＤＮＡによるプログラミングのための新規な代案を提示し、この有機システムは、演算の性能において大規模な並列処理を有し、したがって最終結果を得るが、上述の限界を伴う。彼は、有機ＤＮＡでのプログラミングによってハミルトン経路問題を解くシステムを設計し、したがって、ＮＰ完全問題を多項式に近い計算時間で解くことができることを実証した。このときから、ＤＮＡまたは分子プログラミングによる計算と称される有機材料によるまったく新しいプログラミングの考え方が生じた。しかしながら、数年を通じ、主として壊れやすい材料の特性ゆえに、有機技術をビジネスの世界へと移転させる種々の実験は、不毛に終わっていた。これらの問題を解決するために、この文書は、電子技術、特にはＩｎＣｈｒｏＳｉｌ技術による解決策、有機システムの挙動をエミュレートする人工的な提案を提示する。
【０１０６】
ハミルトン経路問題の解決のための並列的実装が存在するが、それらは、大量のリソースおよび接続されたノード間の通信を必要とする。無機ＤＮＡがシーケンシャル技術と比べて有する利点は、演算の実施の形態における大きな並列処理であり、その理由で、本発明は、ハミルトン経路問題を電子的に解く。上述の特性に基づき、各都市、経路、および経路をＤＮＡのストランドにリンクするように機能する相補的なシーケンスが、この文書において述べたエンコーディングによってエンコードされ（図１９を参照）、図１９に、頂点が０から６まで番号付けされたハミルトン問題を表すグラフ１１を見て取ることができる。
【０１０７】
この問題は、ＮＰ完全問題であるため、多項式次数を有する決定論的問題においてきわめて難しいが、非決定論的なアルゴリズムを、この問題の解決のため考案することができる。非決定論的なアルゴリズムが、以下の行に提示される。
入力：グラフ、Ｖｉｎ、およびＶｏｕｔ
・グラフに存在するすべての経路は、無作為に生成される。
・入力に適合するすべての経路は、除かれる。
・必要とされる頂点を有さないすべての経路も、除かれる。
・各頂点について、実際の頂点を含まない経路は拒絶される。
出力：ＹＥＳ（経路が存在する場合）  ＮＯ（そうでない場合）
【０１０８】
したがって、従来からのコンピュータにおいては、最初の都市Ｖｉｎから最後の都市Ｖｏｕｔまでの経路を見つけるためにすべての都市を１つずつ比較する必要があるため、計算時間が多項式であることができない。
【０１０９】
後述される電子デバイスが、図１９の７つの頂点を有するグラフ１１からアプローチされた。これは、特定の数の辺を有する有向グラフを表す。最初の段階は、図１９のグラフをエンコードすることであり、このためにＣｏｄ−ＩｎＣｈｒｏＳｉｌエンコーディング（この文書において説明済み）が使用され、各都市（頂点）が、所定の数のヌクレオチド（例えば、２０ヌクレオチド）を有することが確立され、辺が、頂点または出発都市の最後の１０個のヌクレオチドならびに頂点または目的都市の最初の１０個のヌクレオチドに相当する同じ数（２０）のヌクレオチドで構成されることが確立された。したがって、ＩｎＣｈｒｏＳｉｌ技術を使用し、前記グラフに表されたすべての辺が収容されるストランドが生成される。他方で、ストランドは、７つの頂点からなる完全グラフ１１のすべての辺をエンコードできなくてはならず、したがって、実験に融通性を与えるために、前記ストランドが、最悪の場合でも完全グラフに比肩（完全グラフは、グラフ理論において、その辺一式が考えられるすべての辺を含んでいるグラフＧ＝（Ｖ，ＶｘＶ）であり、Ｖはグラフのすべての頂点を含む集合である）し、最良の場合には例えば図１９に示したグラフに比肩する可能性を提供する。これは、エンコーディングを実行する電子回路のプログラマが、実際のグラフによって確立される範囲内で自身の望む数の辺を選択できるようにし、すなわち、この例のグラフにおいては、５０４０組（７つの都市を考慮する場合、７の階乗）のヌクレオチドからなるストランドが存在し、プログラマは、ストランドの相補的な部分をグラフの分析に必要な辺においてアクティブにするだけでよい。この場合、相補性が、図１９のグラフの辺を有する状態に対応するストランドの部分においてだけ必要とされる。他方で、図１９のグラフをエンコードする場合、それは、「Ｇ」１７（グラフ）と呼ばれ、図２０に見て取ることができ、Ａ０、Ａ１、・・・が、状態（Ｅｉ）へとリンクするグラフの辺を表し、Ｅ０、Ｅ１、・・・が、提示された問題の都市の状態である。
【０１１０】
図２１が、状態が辺によってどのように接続されるかを図式的に示しており、図２２が、ｃｏｄ−ｉｎｃｈｒｏｓｉｌを使用するこのエンコーディングを詳しく示している。図２１において、状態が、２０のヌクレオチドによって形成され、辺が、或る状態の最後の１０個のヌクレオチドおよび次の状態の最初の１０個のヌクレオチドで構成されている。
【０１１１】
次の段階は、７つの完全な頂点のグラフに存在しうるハミルトン経路のすべてを配置できることで構成され、これは、ＤＮＡの５０４０の鎖の集合が生成されることを意味し、当然ながら、ＩｎＣｈｒｏＳｉｌ技術によって、これらのストランドは、１４０組のヌクレオチドで構成される（７つの頂点が存在し、その各々を２０組のヌクレオチドによって表さなければならず、７×２０のストランド長が必要とされる）。これらのストランドは、三次元のチップにアプローチでき、有機の性質をエミュレートできるという線において継続できることがより好都合であるため、行列の形態に配置されている。このエンコーディングは、例のグラフと同様に、「ＣＧ」１８（グラフの集合）と呼ばれた。
【０１１２】
集合論が、提案の範囲を区切るために特に使用され、提案の対象を具体化された特定の基準にとどまるように強制する。これは、最初に少なくとも偽の真のレベルにおいて、最大で確立された提案のパラメータかがどのように対応するかに応じて、形成された提案における動作を可能にするために望ましく、すなわち、任意の対象αに鑑みて、それが集合に属するかどうかが確実に知られる場合に、集合Ｓが定められる。したがって、このプロジェクトに適用されるこの理論が、状態のすべての可能な組み合わせを表すストランドの集合の図２３の「ＣＧ」の各辺を、完全に平行かつ決定的である図２０のグラフ「Ｇ」に指定される各辺と比較することを可能にし、この方法で、グラフ「ＣＧ」の前記辺がグラフ「Ｇ」にエンコードされた辺の集合に属するかどうか、したがってグラフ「Ｇ」の辺が集合になり、次いでグラフ「ＣＧ」の辺がオブジェクトになり、それらについて、「ＣＧ」が可能な解のテンプレートであるため、それらがプログラマによって述べられた集合、すなわちグラフ「Ｇ」に属するかどうかが確実に知られるべきである。これらの比較を実行できるために、論理的半加算器、桁上げ保存加算器（ＣＳＡ）、およびウォレスツリーの考え方が使用される。これらの技術は、コンピュータ構造の分野において単純に受け入れられており、問題によって必要とされる並列処理を得る設計における変更を生む可能性を提供し、これにおいて所望の結果を得る。他方で、図２４に観察されるように、標準的な論理的半加算器の内部構造を見ることができる。
【０１１３】
この文献に存在する変更は、繰り上げの除去であり、２つの入力の直接的な加算だけが残され、ＸＯＲポートの真理値表を考慮に入れた場合、２つのビットが同じである場合に論理結果は０であることを観察でき、この理由で、このプロジェクトは、前記出力を拒絶することを選択し、この方法で、直接的かつ逆でない論理が連動される。この手法ゆえに、比較器１２は、問題を解くためにＸＮＯＲポート１２ａによって開発される。他方で、４０のＸＮＯＲポート１２ａ（辺が２０組のヌクレオチドからなり、このことが、２対２で比較されるため、辺ごとに４０ビット、したがって８０の入力を必要とするため）を互いに連結するという事実が、ＣＳＡ（データおよび桁上げの加算を結果として得る加算の実行を可能にする桁上げ保存加算器）を生成できるという考え方から生じ、すなわちＸＮＯＲポート１２ａをリンクすることで、４０ビットの一意の結果が与えられる。
【０１１４】
しかしながら、これらのポートは、最適でない４０ビットの結果を提供し、この理由で、すべてのビットが同じであるか、およびそれらが同じ辺であるかという疑問が生じ、このために、４０入力のＡＮＤポート１２ｂおよび１つの応答ビットが使用され、我々の疑問への応答をただ１つのデータにおいて得る。このＡＮＤポート１２ｂが論理結果として「１」を与える場合、このことは辺が同じであることを意味すると考えられるため、したがって前記辺がグラフ「ＣＧ」に属し、グラフ「Ｇ」に属する辺の集合に属すると考えられる。対照的に、値が「０」である場合、それは、言及された辺が同じでないことを意味すると考えられるが、それらは、それらが解くデータであったプログラムされた集合に属さないことを保証するわけではない。したがって、ＣＳＡと同じ回路のカプセル化が生成され、この方法で、図２５に示した比較器１２が生成された。
【０１１５】
この問題を解くことができるために、比較器１２が確立され、行列を生み出し、並列形式で両方のグラフ（「Ｇ」および「ＣＧ］）の辺１３および１４を２対２で比較する。しかしながら、これが経路であるかどうかをどのように確立するかという新たな疑問が生じ、この疑問に応答できるために、すでに公知のウォレスツリーが考慮されるが、完全に並列な形式で必要とされる結果を見つけることができるために別のレベルの要件を生じさせているそれらの構造および動作の考え方は使用されない。
【０１１６】
したがって、比較器の前記行列の列の各々比較器について、その等しい結果１２がＯＲポート１５へと向けられたことが必要とされる場合、比較器のいずれかが論理「１」へと応答した場合に、その列に対応する前記論理ポート１５が、前記辺がプログラムされた辺の集合に属することを並列に確認すると考えられた。この方法で、ウォレスツリーの前記レベルが生成される。
【０１１７】
最後に、これらすべてのＯＲ論理ポート１５は、この場合には、グラフ「ＣＧ」に属するＩｎＣｈｒｏＳｉｌのＤＮＡストランドに存在する列または辺と同じ数であり、すなわち６つのＯＲ論理ポート１５である。この方法で、すべての辺が集合への所属を確認する場合、それらはハミルトン経路を表しており、これは、すべての出力をＡＮＤ論理ポート１６へと案内することによって実現され、この方法で、望まれる応答が最終的に得られ、したがって要件の最終レベルが生成される。
【０１１８】
最後に、ＡＮＤポート１６の結果が、図示されていない結果ベクトルに保存され、このベクトルは、５０４０を有すると考えられ、すなわち、エンコードされたＩｎＣｈｒｏＳｉｌのストランドと同数であり、この理由で、論理「１」が反映されている位置が、ベクトルの前記位置においてエンコードされたストランドが提示されたグラフのハミルトン経路であることを反映していると考えられ、図２６に、回路の概略図が示されており、図２７に、全回路を見て取ることができる。
【０１１９】
巡回セールスマン問題の解法
巡回セールスマン問題（ＴＳＰ）は、計算最適化の分野において最も有名かつ最も研究された問題である。その手法の明らかな単純さにもかかわらず、この問題は、ＮＰ完全な複雑鎖であると考えられるため、解くことが最も難しい問題の１つである。本発明は、多項式次数の一時的コストで、電子システム（先のセクション）で巡回セールスマンの問題を解く。このシステムは、グラフに存在するすべてのハミルトン経路が得られる重み付けおよび有向グラフを有する。したがって、最も有利な場合においては、経路が１つしか存在しないが、逆の場合または反対極において、不利な場合、すなわち完全なグラフが存在する場合には、すべてのハミルトン経路を有することができる。すでに述べたように、すべての経路の計算が並列に実行されるが、先のセクションの回路が考慮していなかった内容は、重み付きハミルトン問題を解く辺の重み付けである。重み付けハミルトン問題への解を与えるためにこの文書において到達される考え方は、単純である。ハミルトン経路の計算のために設けられた同じ電子インフラストラクチャが使用されるが、２つの実装も考慮に入れられ、図２８における第１の実装は、この情報（見つけられた経路）を、重みと辺との間の対応を判断するソフトウェアシステム２３、２６へと伝達することである。このシステムは、ひとたび個々のコストが得られたならば、各経路の総コストを計算する。最後に、すべてのハミルトン経路のコストが計算されると、それらが所定の基準（最小から最大へ、または最大から最小へ、など）に従って並べられる。これらの演算のすべては、情報がＣｏｄ−ＩｎＣｈｒｏＳｉｌでエンコードされており、辺への重みの割り当ておよびその後のコスト計算が、多項式時間を有するため計算レベルにおいて高くつく作業でないことを、忘れてはならない。最後に、ユーザまたはシステムは、並べられた経路の集まりを有し、次いで、それに頼って最良の経路を選択することができる。この図２８において、参照符号２１は、ハミルトン経路を得る回路を表しており、参照符号２２は、データ処理モジュール２３のインターフェイス２５との接続インターフェイスを表しており、参照符号２４は、データベースであり、参照符号２６は、コストおよび並べ替え計算モジュールである。参照符号２７は、外部データ要求装置を表す。
【０１２０】
他方で、中間データ、すなわち辺の重み付けなどが、本発明のデータベースに保存されている。この理由で、それは、行われようとしている計算または行われた計算の支えとして機能している。
【０１２１】
図２９に示されている別の実装は、メモリ２８（Ｍｅｍ−ＩｎＣｈｒｏＳｉｌまたは他の種類のメモリ）の使用であり、その考え方は、すべてのＩｎＣｈｒｏＳｉｌ頂点、したがって辺の値がエンコードされ、リンクが確立されたとき、システムがそのメモリアドレス（辺の値）に、グラフ内のその辺の重みの値を保存し、すなわち、その値または重みは辺に保存されず、その値が位置するメモリアドレスが保存される。なぜならば、この値はきわめて大きい数になる可能性がある一方で、アドレスは所定のサイズを有するからである。ハミルトン経路が先の回路２１によって割り出されたとき、それはメモリ２８内の辺の値を探し、そのアドレスを知っているため、その値を知るであろう。これらのコストが、加えられ、連続したアドレスを有するメモリ２８に保存することができる各経路の総コストを得る回路、すなわちバス３２および加算器３０の仲介によって探される。先の実装と同様に、この情報を入力として受けるユーザまたはシステムが、この文献に記載される装置の外部の選択基準によって、どの経路を残すかを選択する。この例では、参照符号２２が、データ処理モジュール２３ａのインターフェイス２５ａとの接続インターフェイスを表しており、参照符号２９が、並べ替えモジュールであり、参照符号３１が、データ読み出しデバイス２７とのモジュール２３ａの接続インターフェイスである。
【０１２２】
最後に、我々は、ハミルトン閉路の問題を解くこともでき、その目的のために、出力頂点が目的地頂点と同じであるという前提を考慮する必要があると考えられることを、示しておかなければならない。
【０１２３】
オイラー経路の達成
オイラー経路は、グラフのすべての頂点を、グラフの各辺を１回だけ通過して通る経路であり、主たる条件の１つは、それが最初または出力頂点へと戻ることであり、したがってオイラー経路は、グラフのすべての辺を１回だけ含む閉路である。この問題は、ケーニヒスベルク市の７つの橋という名前を有する問題において、１７３６年にレオンハルト・オイラー（Ｌｅｏｎｈａｒｄ  Ｅｕｌｅｒ）によって提示され、彼自身によって解かれた。この問題は、以下の形式において公表されている。ケーニヒスベルク市のプレーゲル川にある２つの島が、７つの橋によって、互いに連結されるとともに陸地と接続されている。４つの陸地部分のいずれかから出発し、各橋をちょうど１回だけ渡って散歩をすることは可能であるか。
【０１２４】
オイラーは、各陸地部分を１つの点によって表し、各橋を該当する点を連結する線によって表して、この問題にアプローチした。その結果、先の問題を、以下の質問へと変換することができる。線を繰り返すことなくこの表現を巡って移動することは可能か。オイラーは、各点に作用する線の数が奇数（各点に進入および出発できる必要条件）であるため、不可能であることを証明した。したがって、この問題は、以下のような質問を提起する。この電気網のケーブルを、網のセクションを繰り返すことなくどのようにカバーすることが可能か。特定の通りを通ってどのようにこの経路を実行できるか、などである。
【０１２５】
すでに理解されるように、これらの問題の解決には複雑さが存在し、その理由で、この問題を逆に考えることができ、すなわち頂点が辺になり、辺が頂点になるものと考えることができる。この変換によって、今や頂点が辺を表し、すべての辺を通過することができるためにどのような頂点の順序を辿るべきかを知ることが必要であるため、ハミルトン経路の適用または計算が可能になる。マルチグラフ、すなわち非決定性オートマトンであると考えられる図１８の有向および重み付けなしのグラフを仮定する。
【０１２６】
図１８のグラフは、以下のようにも表すことができ、ここでＶ１は、頂点の集合であり、Ｅ１は、辺の集合である。
Ｇ１＝（Ｖ１，Ｅ１）
ここで、Ｖ１＝（ｖ１，ｖ２，ｖ３）およびＥ１＝（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）
【０１２７】
さらに、我々は、辺による以下の頂点のリンクを有する。
Ｕ＝｛（ｖ１，ｖ２，ａ１），（ｖ１，ｖ２，ａ２），（ｖ１，ｖ２，ａ３），（ｖ２，ｖ３，ａ４），（ｖ２，ｖ３，ａ５），（ｖ２，ｖ３，ａ６），（ｖ３，ｖ１，ａ６）｝
【０１２８】
ここで、これらのリンクに用いた表記法は、（出発頂点、目的頂点、辺）である。前記の反転が行われる場合、辺が頂点として考えられ、頂点は辺として考えられる場合に、我々は、以下のグラフを得るであろう。
Ｇ２＝（Ｖ２，Ｅ２）ここで、Ｖ２＝（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）およびＥ２＝（（ｖ１，ｖ２），（ｖ２，ｖ３），（ｖ３，ｖ１））
【０１２９】
さらに、我々は、辺による以下の頂点のリンクを有する。
Ｗ＝｛（ａ１，ｖ１，ｖ２，ｖ２，ｖ３，ａ４）．．．．．｝
【０１３０】
したがって、グラフは、図１８に示した形態を有する。結果として、先のグラフＧ２のハミルトン経路が示される場合、解またはオイラー経路Ｇ１が存在すると言うことができる。また、グラフが重み付けされ、各経路の総コストを計算することができ、したがってコストによる並べ替えが可能であるが、オイラー経路は重み付けを有さず、オイラー経路における最適化という新規な問題が提起されうることを考慮できる。結論として、ハミルトン経路がグラフＧ２に存在する場合、グラフＧ１にオイラー経路が存在すると言うことができる。最後に、オイラー閉路を解くことができ、この目的のために、ストランドの底またはストランドのバンクをエンコードするときに、最初のノードが最後のノードと同じであるという設定がなされることを、述べておくことができる。このようにして、閉路問題を、本発明を使用して解くことができる。
【図１】
2010535370.tif 000005
【図２】
2010535370.tif 000006
【図３】
2010535370.tif 000007
【図４】
2010535370.tif 000008
【図５】
2010535370.tif 000009
【図６】
2010535370.tif 000010
【図７】
2010535370.tif 000011
【図８】
2010535370.tif 000012
【図９】
2010535370.tif 000013
【図１０】
2010535370.tif 000014
【図１１】
2010535370.tif 000015
【図１２】
2010535370.tif 000016
【図１３】
2010535370.tif 000017
【図１４】
2010535370.tif 000018
【図１５】
2010535370.tif 000019
【図１６】
2010535370.tif 000020
【図１７】
2010535370.tif 000021
【図１８】
2010535370.tif 000022
【図１９】
2010535370.tif 000023
【図２０】
2010535370.tif 000024
【図２１】
2010535370.tif 000025
【図２２】
2010535370.tif 000026
【図２３】
2010535370.tif 000027
【図２４】
2010535370.tif 000028
【図２５】
2010535370.tif 000029
【図２６】
2010535370.tif 000030
【図２７】
2010535370.tif 000031
【図２８】
2010535370.tif 000032
【図２９】
2010535370.tif 000033
【国際調査報告】
2010535370.tif 000034
2010535370.tif 000035
2010535370.tif 000036
2010535370.tif 000037
2010535370.tif 000038
2010535370.tif 000039