Title: Biomolecular autonomous solution of the Hamiltonian path problem via hairpin formation

Authors: Israel M. Martinez-Perez, Gong Zhang, Zoya Ignatova, Karl-Heinz Zimmermann

Addresses: Department of Computer Engineering, Hamburg University of Technology, 21071 Hamburg, Germany. ' Biotechnology II, Hamburg University of Technology, 21071 Hamburg, Germany. ' Biotechnology II, Hamburg University of Technology, 21071 Hamburg, Germany ' Department of Computer Engineering, Hamburg University of Technology, 21071 Hamburg, Germany

Abstract: The Hamiltonian path problem is one of the famous hard combinatorial problems. We provide the first molecular-scale autonomous solution of the decision Hamiltonian path problem. It is based on the formation of secondary structures of DNA molecules.

Keywords: Hamiltonian path problem; autonomous biomolecular computation; DNA hairpin formation; bioinformatics; molecular scale; secondary structures; DNA molecules; self-annealing; palindromic encoding sequences; sequence design.

DOI: 10.1504/IJBRA.2005.008442

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.4, pp.389 - 398

Published online: 20 Dec 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article