DNA計算機の実用化に向けたアルゴリズムの設計論に関する研究

DNA計算機の実用化に向けての基礎研究として,平成15年度は以下のことを行った.(1)Adlemanが用いた計算モデルは抽出モデルと呼ばれ,基本操作のエラー率が高いといわれている。Amosは基本操作に除去操作を用いた計算モデルを提案した.このモデルはエラー率が非常に低いが,使用DNA量が多くなるという欠点がある.本研究では,Amosの計算モデルをより実用的な観点から見直し,現実的なモデルを提案した.その計算モデルの上で,、DNA量を削減するための方法論として,(a)新しい解の符号化,(b)分割統治法の適用を提案し,NP完全問題であるハミルトン経路問題,グラフの三彩色問題,部分グラフ同型問題に適用した.いずれの問題に対しても新しい解の符号化については理論的にAmosの解法に比べて悪くはならないことを示した.また,新しい解の符号化と分割統治法を組み合わせることによって,100%近くDNA量を削減できることをシミュレーションにより示した(研究発表(1)〜(2)).(2)DNA計算機を実用化するためには,加算や論理演算などをDNA計算の枠組みで計算しなければならない.本研究では,従来加算や論理演算などの基本演算に関するDNA計算モデルにおける結果を整理し,新しい加算アルゴリズムを開発した.ここでは,2進数を1の桁を位置の集合により表す計算モデルを用いて,nビット2進数の加算を0(n^3)種類のDNA鎖を用いて,定数時間で計算できるアルゴリズムを示した.(研究発表(3)).これはnの多項式種類のDNA鎖を用いた初めての定数時間アルゴリズムである.(3)これまでのDNA計算モデルを見直し,DNA計算のより現実的なモデルを提案した.DNAの基本操作のうち,アニールと複製操作は決定的に行われないことに着目し,これらの操作に対して確率を導入したモデルを構築した.また,このモデルの下で従来のアルゴリズムがどの程度DNAが必要であるかを実験した(研究発表(4)).

DNA計算機の実用化に向けての基礎研究として,平成15年度は以下のことを行った.(1)Adlemanが用いた計算モデルは抽出モデルと呼ばれ,基本操作のエラー率が高いといわれている。Amosは基本操作に除去操作を用いた計算モデルを提案した.このモデルはエラー率が非常に低いが,使用DNA量が多くなるという欠点がある.本研究では,Amosの計算モデルをより実用的な観点から見直し,現実的なモデルを提案した.その計算モデルの上で,、DNA量を削減するための方法論として,(a)新しい解の符号化,(b)分割統治法の適用を提案し,NP完全問題であるハミルトン経路問題,グラフの三彩色問題,部分グラフ同型問題に適用した.いずれの問題に対しても新しい解の符号化については理論的にAmosの解法に比べて悪くはならないことを示した.また,新しい解の符号化と分割統治法を組み合わせることによって,100%近くDNA量を削減できることをシミュレーションにより示した(研究発表(1)〜(2)).(2)DNA計算機を実用化するためには,加算や論理演算などをDNA計算の枠組みで計算しなければならない.本研究では,従来加算や論理演算などの基本演算に関するDNA計算モデルにおける結果を整理し,新しい加算アルゴリズムを開発した.ここでは,2進数を1の桁を位置の集合により表す計算モデルを用いて,nビット2進数の加算を0(n^3)種類のDNA鎖を用いて,定数時間で計算できるアルゴリズムを示した.(研究発表(3)).これはnの多項式種類のDNA鎖を用いた初めての定数時間アルゴリズムである.(3)これまでのDNA計算モデルを見直し,DNA計算のより現実的なモデルを提案した.DNAの基本操作のうち,アニールと複製操作は決定的に行われないことに着目し,これらの操作に対して確率を導入したモデルを構築した.また,このモデルの下で従来のアルゴリズムがどの程度DNAが必要であるかを実験した(研究発表(4)).