理論とシミュレーション

Adleman の計算モデル

有限アルファベット ${\Sigma}$ 上の文字列を DNA 分子を用いて符号化し、文字列の多重集合に対する演算を DNA 分子に対する実験操作を用いて実現する。

分離（Separate）：
- 集合 ${T}$ を文字列 ${s}$ を部分文字列として含む文字列の集合 ${+(T,s)}$ と含まない文字列の集合 ${-(T,s)}$ に分割する。
- DNA 分子の抽出実験を試験管 ${T}$ に対して行うことに対応する。
混合（Merge）：
- 集合 ${T_1}$ と ${T_2}$ に対して、和 ${T_1 \cup T_2}$ をとる。
- 試験管 ${T_1}$ と ${T_2}$ の内容物を混合させる操作に対応する。
検出（Detect）：
- ${\mathrm{Detect}(T)}$ は ${T}$ が空集合でないならば YES を返し、 ${T}$ が空集合ならば NO を返す。
- 電気泳動法などを使って、DNA 分子の存在の有無を確認する実験操作に対応する。
増幅（Amplify）：
- ${T}$ に対して、内容が ${T}$ と等しい多重集合 ${T_1}$ と ${T_2}$ を生成する。
- PCR を用いて DNA 分子の量を増幅する実験操作に対応する。