| and Problems (2008) | |||||||||||||
Abstract | |||||||||||||
| The tools of molecular biology are used to solve an instance of the directed Hamiltonian path problem. A small graph is encoded in molecules of DNA and the `operations ' of the computation are performed with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computations at the molecular level. Adleman 3 In 1959 Richard Feynman gave a visionary talk describing the possibility of building computers which were \sub-microscopic " (1). Despite remarkable progress in computer miniaturization this goal has yet to be achieved. In this report the possibility of computing directly with molecules is explored. A directed graph G with designated vertices v in and v out, issaidtohave a Hamiltonian path (2) if and only if there exists a sequence of compatible `one way ' edges e1�e2�:::�e z (that is, a `path') which begins at v in, endsat v out and enters every other vertex exactly once. Figure 1 shows a graph | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||