chemart / dna-hpp

View on GitHub

Adleman's DNA Hamiltonian Path computation — The experiment that started DNA computing. Each vertex of a graph gets a random 20-base code word and each edge an oligo spanning the two halves of the vertices it joins, so when everything is mixed the strands ligate in…

chemistry official · built in wet fidelity: reconstructed constructive #banzhaf-yamamoto

How it works

The experiment that started DNA computing. Each vertex of a graph gets a random 20-base code word and each edge an oligo spanning the two halves of the vertices it joins, so when everything is mixed the strands ligate into every path through the graph at once - massive parallelism from a spoonful of chemistry. The computation is then five filtering steps: amplify paths with the right endpoints, keep the right length, check each vertex is present, and read off what survives.

S: single-stranded DNA oligonucleotides, Species.structure carrying the sequence written 5' -> 3': the code word O_i of each vertex (a random 20-mer), its Watson-Crick complement Obar_i (the splint), the edge oligonucleotide O_{i->j} = 3' half of O_i + 5' half of O_j (all of O_i when i = v_in, all of O_j when j = v_out), and the partial and complete path duplexes P<v0>-<v1>-..., whose structure is the ligated sense strand · implicit
R: hybridisation and ligation of step 1: P(v0..vk) + Obar_vk + E_vk-v -> P(v0..vk,v). The splint Obar_vk bridges the junction, its 5' half pairing with the 3' 10-mer of the growing strand and its 3' half with the 5' 10-mer of the incoming edge oligonucleotide, so T4 ligase extends the path by one vertex. Ligation conserves nucleotides. · arity 3
A: well-stirred-multiset · none inside the tube; the closure is cut off at max_path_vertices vertex slots per path, because a graph with a cycle has infinitely many walks

Parameters

name	default	meaning
graph list · structural	[[0, 1], [0, 3], [0, 6], [1, 2], [1, 3], [2, 1], [2, 3], [3, 2], [3, 4], [4, 1], [4, 5], [5, 1], [5, 2], [5, 6]]	the directed HPP instance as a list of [u, v] edges default: the 14 edges of Adleman's fig. 1
vertices int · structural	7	number of vertices; they are numbered 0..vertices-1 and every endpoint of graph must be one of them [2, 14]; Adleman: 7; Hartmanis' 200-city instance would need more than the weight of the Earth in DNA
v_in int · structural	0	the start vertex; its code word O_v_in is one PCR primer and edges leaving it carry the whole code word [0, 13]
v_out int · structural	6	the end vertex; its complement Obar_v_out is the other PCR primer and edges entering it carry the whole code word [0, 13]
oligo_length int · structural	20	length of each vertex code word, split into two halves, so it must be even; it also fixes the gel band at oligo_length x vertices bp [4, 60]; Adleman: 20-mers, chosen so that a splint binds each edge over 10 base pairs and is stable at room temperature
sequences dict · structural	{"2": "TATCGGATCGGTATATCCGA", "3": "GCTATTCGAGCTTAAAGCTA", "4": "GGCTAGGTACCAGCATGCTT"}	vertex code words given explicitly, keyed by vertex id as a string; the default holds the three 20-mers printed in fig. 2 of the paper, and every other vertex gets a random code word drawn from rng, as the paper did
max_path_vertices int · structural	7	longest path, in vertex slots, that the ligation closure keeps; the walk set of a cyclic graph is infinite, so the network is reported as truncated whenever a kept path could still be extended [2, 12]; the gel of step 3 discards everything but the paths of exactly `vertices` slots, so the default equals `vertices`
pmol float · population	50.0	amount of each edge oligonucleotide and of each splint in the ligation reaction; the initial state is given in pmol [0, ∞]; Adleman: 50 pmol of each, about 3e13 copies

Adleman's DNA Hamiltonian Path computation

One of the artificial chemistries of Banzhaf & Yamamoto, Artificial Chemistries (MIT Press, 2015), §19.3.1; first proposed by Adleman, 1994.

Its generator ships with the chemart library, so loading it runs no code from the hub and needs no trust_remote_code.

import chemart

net = chemart.generate_network("chemart/dna-hpp", seed=0)   # same as "dna-hpp"
print(net.summary())

What to look for

on Adleman's fig. 1 graph the five steps leave exactly one molecule, the published Hamiltonian path 0->1->2->3->4->5->6
length selection keeps the 140 bp band: 7 vertices x 20-mer code words
graduated PCR prints a path: a vertex in slot k gives a band at 20 (k+1) bp, so the Hamiltonian path gives 40, 60, 80, 100, 120, 140 bp in successive lanes
paths that miss a vertex (0->1->3->4->5->6, 120 bp) or enter one twice (0->3->2->3->4->5->6, 140 bp) survive the earlier steps; the gel should remove the first and affinity purification removes the second. Both were seen in the graduated PCR of the paper's fig. 3B, where the 120 bp path had leaked through the gel as contamination and was then removed by step 4 (p. 1022)
removing the edge 2->3 leaves the graph without a Hamiltonian path, and so does moving the designated vertices to v_in = 3, v_out = 5
the number of oligonucleotides grows linearly with the edges, but the number of copies needed grows exponentially with the vertices (Hartmanis: 200 cities would need more than the weight of the Earth in DNA)

Implementation decisions

The book (19.3.1) describes the experiment in prose and states the encoding as e_ij = complement(v_i,in) complement(v_j,out), i.e. edges as complemented strands. That is not Adleman's encoding and its halves are swapped even in the book's own notation (v_i,in is defined as the half for incoming links, yet it is the source of the edge). The paper's own scheme is implemented: the edge oligonucleotide is the uncomplemented 3' half of the source code word followed by the 5' half of the target code word, and the vertex complements are the splints (fig. 2). The book's variant is an equally workable but different code.
Only three code words are published (O2, O3, O4 in fig. 2). They are the default of the `sequences` parameter; the code words of the other vertices are drawn uniformly from ACGT with rng, which is what the paper did ('each vertex was associated with a random 20-mer'). The published fig. 2 strands O2->3, O3->4 and Obar3 are therefore reproduced exactly by the generator, and the rest of the encoding is seed-dependent.
Edges leaving v_in carry the whole code word of v_in and edges entering v_out the whole code word of v_out, as the paper specifies; this is what makes a Hamiltonian path of n vertices exactly oligo_length x n = 140 bp long and lets O_v_in and Obar_v_out prime it.
Step 1 is the only step that makes molecules, so it is the reaction set: path + splint + edge -> longer path, a termolecular hybridisation-and-ligation event. Steps 2-5 select molecules and are recorded in extras.analysis (counts kept after each step, the gel band in bp, the bead order, the surviving paths and their graduated-PCR bands).
A graph with a cycle has infinitely many walks, so the ligation closure is cut off at max_path_vertices vertex slots and the network's status is `truncated`. With the default (7 = the number of vertices) nothing that step 3 keeps is lost, since the gel band selects exactly the paths with 7 vertex slots.
No rate constants are published (the paper gives protocols: 50 pmol of each oligonucleotide, 5 units T4 ligase, 4 hours at room temperature), so every reaction carries rate None and the protocol is recorded as text in extras.analysis.experiment.
initial_state is in pmol, the unit the paper uses: 50 pmol of each edge oligonucleotide and of each splint Obar_i with i different from v_in and v_out. The vertex code words O_i and the complements Obar_v_in, Obar_v_out are listed as species because they are the code, but they are not in the ligation tube: O_v_in and Obar_v_out enter in step 2 as PCR primers and the other splints again in step 4 on beads.
v1 fields replaced: the `graph` matrix becomes an edge list, `copy_number` becomes `pmol` (the paper's unit; the exponential scaling it warned about is kept as prose in extras.analysis.experiment), and `constructive` becomes true, since the path species are assembled at run time and are unbounded for a cyclic graph.

Sources

Adleman, L.M. (1994). Molecular computation of solutions to combinatorial problems. Science 266(5187):1021-1024. https://doi.org/10.1126/science.7973651 - fig. 1 (the graph and its unique Hamiltonian path), fig. 2 (the code words O2, O3, O4, the edge oligonucleotides O2->3, O3->4 and the splint Obar3), the five-step algorithm and steps 1-5 as carried out, the graduated-PCR band arithmetic on p. 1022, and notes 4-9 (protocols). Scan used: https://courses.cs.duke.edu/cps296.4/spring04/papers/Adleman94.pdf
Adleman, L.M. (1994). Author's preprint of the same paper, https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf - same text, used for the wording of the algorithm and the notes.
Banzhaf, W. & Yamamoto, L. (2015). Artificial Chemistries, section 19.3.1 and fig. 19.12 (MIT Press) - the prose description this entry comes from.
Hartmanis, J. (1995). On the weight of computations. Bulletin of the EATCS 55:136-138 - the exponential scaling quoted in extras.analysis.experiment.

Banzhaf & Yamamoto, Artificial Chemistries (2015), §19.3.1

Preview at default parameters

797 species · 769 reactions · status truncated · seed 1

E0-1 + Obar1 + E1-2 -> P0-1-2
E0-1 + Obar1 + E1-3 -> P0-1-3
E0-3 + Obar3 + E3-2 -> P0-3-2
E0-3 + Obar3 + E3-4 -> P0-3-4
E1-2 + Obar2 + E2-1 -> P1-2-1
E1-2 + Obar2 + E2-3 -> P1-2-3
E1-3 + Obar3 + E3-2 -> P1-3-2
E1-3 + Obar3 + E3-4 -> P1-3-4
E2-1 + Obar1 + E1-2 -> P2-1-2
E2-1 + Obar1 + E1-3 -> P2-1-3
E2-3 + Obar3 + E3-2 -> P2-3-2
E2-3 + Obar3 + E3-4 -> P2-3-4
E3-2 + Obar2 + E2-1 -> P3-2-1
E3-2 + Obar2 + E2-3 -> P3-2-3
E3-4 + Obar4 + E4-1 -> P3-4-1
E3-4 + Obar4 + E4-5 -> P3-4-5
E4-1 + Obar1 + E1-2 -> P4-1-2
E4-1 + Obar1 + E1-3 -> P4-1-3
E4-5 + Obar5 + E5-1 -> P4-5-1
E4-5 + Obar5 + E5-2 -> P4-5-2
E4-5 + Obar5 + E5-6 -> P4-5-6
E5-1 + Obar1 + E1-2 -> P5-1-2
E5-1 + Obar1 + E1-3 -> P5-1-3
E5-2 + Obar2 + E2-1 -> P5-2-1
E5-2 + Obar2 + E2-3 -> P5-2-3
P0-1-2 + Obar2 + E2-1 -> P0-1-2-1
P0-1-2 + Obar2 + E2-3 -> P0-1-2-3
P0-1-3 + Obar3 + E3-2 -> P0-1-3-2
P0-1-3 + Obar3 + E3-4 -> P0-1-3-4
P0-3-2 + Obar2 + E2-1 -> P0-3-2-1
P0-3-2 + Obar2 + E2-3 -> P0-3-2-3
P0-3-4 + Obar4 + E4-1 -> P0-3-4-1
P0-3-4 + Obar4 + E4-5 -> P0-3-4-5
P1-2-1 + Obar1 + E1-2 -> P1-2-1-2
P1-2-1 + Obar1 + E1-3 -> P1-2-1-3
P1-2-3 + Obar3 + E3-2 -> P1-2-3-2
P1-2-3 + Obar3 + E3-4 -> P1-2-3-4
P1-3-2 + Obar2 + E2-1 -> P1-3-2-1
P1-3-2 + Obar2 + E2-3 -> P1-3-2-3
P1-3-4 + Obar4 + E4-1 -> P1-3-4-1
… 729 more

Generated by the uploader with chemart push; the hub never runs uploaded code.