DNA分子の自己会合による Horn節の計算

DNA分子の自己会合による
Horn節の計算
萩谷研究室
上嶋裕樹
新しい計算パラダイムの提案
電子計算機の限界
新しい計算パラダイム
分子計算
量子計算
膜計算
アモルファス計算
DNA分子を用いた超並列分子計算の提案
→ DNA計算
これまでの研究
（SIMD型の並列計算）
Adlemanの有向ハミルトン経路問題の解法
(1994)
7頂点14辺の有向グラフに対して
Adleman-Liptonパラダイム(1995)
assembly-graphに従って解の候補を生成する。
実験操作を通じて真の解を抽出する。
データを分子に書きこみ，それに対して同一
の実験操作を行う。
これまでの研究
（計算能力・計算モデル）
DNA分子の形状と言語の生成能力の対応の
研究
さまざまな計算モデルの提案
Branching program
Turing machine
Boolean circuit
Random Access Memory
Horn clause computation (Kobayashi)
Kobayashiによる
DNA計算のHorn節計算モデル
分子をHorn節に対応させる。
1回の実験操作を1段階の導出に対応させる。
SIMD型の計算である。
問題のサイズにしたがって実験操作の回数
が増加する。
これまでの研究
（分子による自律的計算）
DNAのself-assemblyにより自律的に計算が
進行する。
実験操作回数の低減
DNA tileを用いた計算
1次元オートマトンのシミュレーション
string tileの提案
DNA tile構造
Z
X
Y
W
X
Z
Y
W
X
Z
Y
W
cf. Winfree’s DNA Tile
本研究の位置付け
DNAを用いた新しい計算モデルの提案と解
析。
Horn節計算に基づく計算モデル
DNA分子のself-assemblyにより自律的に進行す
る計算
モデルの計算量・計算能力の解析
分子による計算の1つの可能性の理論的な
探求。
計算の実現方法の概要
Horn節の変数代入で基礎節を生成
string tileを用いる。
DNAのself-assemblyにより網羅的に基礎節が生
成される。
DNAのself-assemblyにより自律的に進む。
基礎節に対して演繹推論
DNAのself-assemblyにより自律的に進む。
対象とするHorn節
ruleのatomの引数はXもしくはf1(…fn(X)…)
述語のarityは最大2
関数のarityは1
atomの第1引数はX，第2引数はY
factは引数がないか定数が引数
DNAによるHorn節の実現
Horn programの各Horn節に対応するDNA
分子
sticky end
rule分子
fact分子
P
P
Q
~Q
~R
~Q
P ← Q, R.
P ← Q.
Q.
DNAの自己会合による
融合原理の実現
P
P ← Q, R.
Q ← S, T.
P ← Q, R.
P ← S, T, R.
~Q
Q ← S, T.
Q
~S
~T
~R
結果の検出
query分子の投入
ligation
環状分子の検出
~P
P
計算量
時間計算量
（実験操作の回数）：定数
領域計算量
 （あるfactの導出に必要な最小の分子数）：O(2n)
String tileとは
Winfree et al. (2000)が提案。
tileの複数の層を1つのtileに圧縮。
内部に有向グラフを持ち，各枝がDNA
strandに対応する。
tileが辺で接続することによりグラフがつなが
る。
String tileによる
変数代入の実現
P(f(X), Y) ← Q(X, g(Y)).
a/Y
g(X) / X
P(f(g(b)), a) ← Q(g(b), g(a)).
b/X
Horn節計算による
NTMのシミュレーション
b
t(-2) t(-1) t(0) t(1)
b
b
s
TM・テープの状態をfactで表す。
Ss(ft(-1)(ft(-2)(fb(a1))), ft(0)(ft(1)(fb(fb(a2))))).
状態遷移規則をruleで表す。
Ss’(X, ft(-1)(ft’(0)(Y))) ← Ss(ft(-1)(X), ft(0)(Y)).
Ss’(ft’(0)(X), Y) ← Ss(X, ft(0)(Y)).
本モデルの特徴
自律的計算を行うので，実験操作回数が問
題の大きさに依存せず定数回ですむ。
非決定性Turing machineと同等の計算能力
を持つ。
変数代入と演繹推論の操作の段階が完全に
分かれている。
本モデルの利点
高級プログラミング言語PROLOGと深い関係
を持つ。（Horn節計算）
他のモデルより扱いやすく，アルゴリズム設
計がしやすい。
実験操作の回数が少なくてすむ。（自律的計
算）
本モデルの問題点
計算量の見積もりが不完全である。
時間計算量：実験操作回数でなく，平衡に達する
までの時間が重要。
領域計算量：証明木の分子の生成は超並列に
行われている。
導出に偏りが生じる可能性がある。
効率的な変数代入が行えない。
今後の課題
自律的DNA計算の熱力学的・動力学的解析
それに基づく最適パラメータの決定
温度
塩濃度
DNA計算の確率アルゴリズムとしての解析

Download Report