Hamiltonian path problem
There is a Hamiltonian path if, and only if, there is a path that starts at a start vertex, ends at an end vertex and passes through each remaining vertex exactly once
The Hamiltonian Path Problem is to decide, for any given graph with specified start and end vertices, whether a Hamiltonian path exists or not
Hamiltonian algorithm
For a graph with n vertices:
- Generate a set of random paths through the graph
- Keep only those paths that begin with the start vertex and end with the end vertex
- For a graph with n vertices, keep only those paths that pass through n vertices
- Keep only the paths that pass through each vertex once
- If any paths remain, there is a Hamiltonian path. If no paths remain, there is no Hamiltonian path
Steps in DNA computing
- Each vertex of the graph is assigned a random DNA sequence
- Each edge of the graph is assigned a DNA sequence that is the ‘last name’ of the vertex of origin and the ‘first name’ of the vertex of destination (these are called the “flight numbers”)
- The complementary DNA sequence of each vertex and the flight numbers in aqueous solution are added to a common test tube, followed by DNA ligase
- This process creates random paths through vertices simultaneously - the DNA ‘flight numbers’ are splinted together by the complementary DNA vertex names; the ligase then permanently concatenates the chains of flight numbers
The creation of many random paths simultaneously represents enormous parallel processing (approx. 10^14 flight numbers concatenated in 1 second) - Use PCR to select only the paths that begin with the start vertex and end with the end vertex. This is done by using 2 primers - one that is the start vertex (forward) and one that is the complement of the first name of the end vertex (backward). This leads to an exponential increase in DNA molecules that contain both the right start and end vertices
- DNA products of the correct length can then be isolated by agarose gel electrophoresis
- Affinity separation to identify the remaining sequences that contain each intermediary vertex
Affinity separation
Uses a DNA probe with a complementary sequence to that of a particular vertex
The probes are attached to paramagnetic iron beads (“biotin-avidin magnetic beads system”)
- The products of correct length isolated using agarose gel electrophoresis are made single stranded
- Under conditions that encourage Watson-Crick base pairing, only the molecules that contain the desired vertex’s name will anneal to the probe
- A magnet is held against the test tube wall to hold the magnetic beads (and their attached DNA sequences) to the side while the supernatant is poured away
- The magnet is removed and new solvent added
- The temperature is increased, which breaks the H bonds between the probes and DNA sequences, allowing the DNA sequences to re-dissolve in the solvent
- The magnet is re-applied to attract the free probes to the side of the test tube, allowing the liquid containing the desired DNA strands to be poured into a new tube for further screening
- The process can then be repeated for the remaining vertices
How can the products of desired length be excised from the agarose gel after performing electrophoresis?
By ‘cutting’ out the desired section of gel and soaking it in doubly-distilled H2O to extract the DNA
How might the labour required for affinity separation of even larger graphs be reduced?
Use of alternative procedures
Automation
Less labour-intensive molecular algorithms
“Pseudopaths”
= formed from the occasional ligation of incompatible edge oligonucleotides
Such molecules may be amplified during PCR and may be of the correct length, but are unlikely to survive affinity separation
Reasons for choosing 20mer oligonucleotides
- If oligonucleotide sequences associated with different vertices share long common subsequences it could lead to unintended binding during the ligation step - this is unlikely in 20-mers, given 4^20 different 20-mers can exist
- Severe hairpin loops, that are potentially deleterious to the process, are not likely to arise
- 20-mers ensure that binding between ‘splint’ and ‘edge’ oligonucleotides involves 10 base pairs and is thus stable at room temperature
Energy efficiency of DNA computing
1 J of energy is sufficient for approx. 2 x 10^19 operations
The second law of thermodynamics dictates a theoretical maximum of 34 x 10^19 irreversible operations per 1 J !
Supercomputers are far less efficient - approx 10^9 operations per joule
