DNA計算の規模

20都市の巡回セールスマン問題をアドルマンの手法にならって符号化する。候補ルート1本につきDNA1本、1都市につき20ヌクレオチドとする。このライブラリのDNAの質量を求めよ。次に、実行不可能になるまで都市を追加し、その実際の限界を示せ。

1. まず候補の数を数える。出発都市を固定すると、巡回ルートは残りの都市の順列となるため、候補は 20! 通り存在する。これは 2,432,902,008,176,640,000 通り、すなわち約 2.43 × 10¹⁸ 通りである。

   $$20!=2,432,902,008,176,640,000\approx 2.43\times 10^{18}$$

2. 次に、候補1つの質量を求める。20の都市それぞれが20ヌクレオチドずつ占めるため、DNA鎖の長さは 400 nt となり、1本鎖DNAはヌクレオチド1モルあたり約 330 g である。

   $$L=20\times 20\mathrm{nt}=400\mathrm{nt}$$

3. 1モルはアボガドロ数個のDNA鎖に相当するため、アボガドロ数で割ることで単一分子の質量が求まる。400 × 330 ÷ 6.022 × 10²³、すなわち 2.19 × 10⁻¹⁹ g である。

   $$m_1=\frac{400\times 330}{6.022\times 10^{23}}=2.19\times 10^{-19}\mathrm{g}$$

4. この2つを掛け合わせる。1本あたり 2.19 × 10⁻¹⁹ g のDNA鎖が 2.43 × 10¹⁸ 本集まると、計 0.533 g となる。試験管に収まるわずか半グラムであり、これこそがDNAコンピューティングが実用に耐えると思わせる数値である。

   $$M=2.43\times 10^{18}\times 2.19\times 10^{-19}=0.533\mathrm{g}$$

5. 都市を1つ増やす。候補数は21倍になり、DNA鎖の長さは 420 nt に伸びるため、質量は 21 × (420/400) = 22.05 倍に増えて 11.8 g となる。たった1都市の追加で、前のライブラリ全体の22倍の質量を費やすことになる。

   $$\frac{M_{21}}{M_{20}}=21\times \frac{420}{400}=22.05\Rightarrow 11.8\mathrm{g}$$

6. さらに都市を増やすと、倍率そのものが大きくなっていく。倍率は (n+1) × (1 + 1/n) で表されるためである。38都市ではライブラリの質量は 2.18 × 10²⁶ g となり、これは地球の 3.65% にあたる。39都市になると 8.72 × 10²⁷ g に達するが、地球自体の質量は 5.97 × 10²⁷ である。

   $$M_{39}=8.72\times 10^{27}\mathrm{g}>M_{\oplus }=5.97\times 10^{27}\mathrm{g}$$