Biological Computation

Molecular Computation    ◾    225

3. e DNA molecules are separated based on their length, and only the

molecules of length 140 (20n, where n is the number of vertices in the

graph) are kept. As each edge is represented by a molecule of length

20 and a Hamiltonian path has to traverse each vertex exactly once, a

Hamiltonian path will contain n – 1 edges. But as the edge starting at

v

in

and the edge ending at v

out

are of length 30, the total length of the

representation of the Hamiltonian path is 20n. e molecules that

were kept are amplied again so that enough copies exist to continue

with the algorithm.

4. e paths that visit every vertex in the graph are selected. is is

achieved by rst selecting from the solution all the molecules ...