DNA Computing Scale

DNA can try many routes in parallel, but n! candidates still require n! physical molecules.

Worked example — DNA Computing Scale

Candidate routes, n!	5.11 × 10¹⁹
Length of each strand	420 nt
Required ssDNA mass	1.18 × 10¹ g
Comparable scale	grams

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Parallelism does not cancel complexity 🖖

Adleman's experiment proved that molecular reactions can filter candidate paths. It did not make factorial growth disappear. Giving every route its own molecule merely converts computation time into material: the number of strands, and therefore their mass, still grows as n!.

No encoding is worth one city 🖖

Multiply the bases per city by ten and the mass required multiplies by exactly ten — and the point where it passes the mass of the Earth does not move at all: 39 cities at 20 bases each, 39 at 200. Even an impossible single base per city only pushes it to 40. The encoding is a constant factor. n! is not.

Each extra city costs more than the last one did 🖖

Adding a city multiplies the requirement by (n+1)²/n — the new permutations, plus a longer strand for every one of them. That is 22× at twenty cities, 32× at thirty, and 41× going from thirty-nine to forty. One gram covers 21 cities and a tonne covers 25: four more cities for a factor of a million.

Problem solved in full

The 20-city tour that fits in half a gram, and the 39-city one that does not fit on Earth 6 steps
A travelling-salesman tour of 20 cities is encoded the way Adleman did it: one DNA strand per candidate route, 20 nucleotides per city. Work out how much DNA the library weighs. Then add cities until it stops being possible, and say what the limit actually is.
1. Count the candidates first. With the starting city fixed, a tour is an ordering of the remaining cities, so there are 20! of them. That is 2,432,902,008,176,640,000 — call it 2.43 × 10¹⁸.
  
  $20! = 2, 432, 902, 008, 176, 640, 000 \approx 2.43 \times 1 0^{18}$
2. Now weigh one candidate. Each of the 20 cities contributes 20 nucleotides, so a strand is 400 nt long, and single-stranded DNA runs about 330 g per mole of nucleotide.
  
  $L = 20 \times 20 nt = 400 nt$
3. One mole is Avogadro's number of strands, so divide by it to get the mass of a single molecule: 400 × 330 ÷ 6.022 × 10²³, which is 2.19 × 10⁻¹⁹ g.
  
  $m_{1} = \frac{400 \times 330}{6.022 \times 1 0 ^{23}} = 2.19 \times 1 0^{- 19} g$
4. Multiply the two. 2.43 × 10¹⁸ strands at 2.19 × 10⁻¹⁹ g each comes to 0.533 g — half a gram, in a test tube, and this is the number that makes DNA computing sound like it works.
  
  $M = 2.43 \times 1 0^{18} \times 2.19 \times 1 0^{- 19} = 0.533 g$
5. Add one city. The count multiplies by 21 and the strand grows to 420 nt, so the mass multiplies by 21 × (420/400) = 22.05, giving 11.8 g. The extra city cost twenty-two times the entire previous library.
  
  $\frac{M _{21}}{M _{20}} = 21 \times \frac{420}{400} = 22.05 \Rightarrow 11.8 g$
6. Keep going and the multiplier itself grows, because it is (n+1) × (1 + 1/n). At 38 cities the library weighs 2.18 × 10²⁶ g, which is 3.65% of the Earth. At 39 it weighs 8.72 × 10²⁷ g, and the Earth weighs 5.97 × 10²⁷.
  
  $M_{39} = 8.72 \times 1 0^{27} g > M_{\oplus} = 5.97 \times 1 0^{27} g$
Answer

Half a gram at 20 cities, and 1.46 Earths at 39. The jump from 38 to 39 is a factor of 40.0, and it takes the requirement from 3.65% of the planet to 1.46 times the whole of it — for one city. That is the whole argument against molecular brute force, and notice what it is not: it is not that DNA is slow, or that the chemistry is unreliable, or that we cannot build the strands. Every one of those could be fixed. What cannot be fixed is that n! molecules weigh n! molecules. Massive parallelism divides the TIME by the number of processors and leaves the count of processors exactly where it was, so a problem that needs more processors than there are atoms available is not waiting on better engineering. The tool draws the mass curve against the Earth line; what it cannot draw is that multiplier growing, because it prints a mass and never a ratio.

Learning path

Computing with molecules

Leads to Levinthal’s paradox why more molecules stop helping.

References (2)

The seven-vertex directed Hamiltonian-path experiment this scaling argument starts from: L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems.” Science 266(5187), 1021–1024, 1994.
The molecular-weight approximation used to turn nucleotide count into ssDNA mass: MIT OpenCourseWare, 5.36 Biochemistry Laboratory manual, 2009.

By the 42Math team · Updated 2026-08-22

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Bio, Geo, Chem lessons →

Example problems

Adleman: 7 vertices - Adleman’s seven cities need 3.87 × 10⁻¹⁶ g of DNA. The hard part was the filtering, not the material.
One-gram crossing - Twenty-one cities is where one strand per route first outweighs a gram: 1.18 × 10¹ g.
One-kilogram crossing - Two more cities and the gram has become 6.52 × 10³ g — a factor of 550 for two cities.
Earth-mass crossing - Thirty-nine cities: 8.72 × 10²⁷ g, heavier than the Earth.