Title: Using sticker to solve the 3-dimensional matching problem in molecular supercomputers

Authors: Minyi Guo, Weng-Long Chang, Jiannong Cao

Addresses: Department of Computer Software, University of Aizu, Aizu-Wakamatsu City, Fukushima 965 8580, Japan. ' Department of Information Management, Southern Taiwan University of Technology, Tainan County, Taiwan, 710, ROC. ' Department of Computing, Hong Kong Polytechnic University, Hong Kong

Abstract: Adleman demonstrated that DNA (Deoxyribonucleic acid) strands could be applied for dealing with solutions to an instance of the NP-complete Hamiltonian path problem (HPP) (Adleman, 1994). The Adleman techniques could also be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem) (Lipton, 1995). Furthermore, sticker is used for enhancing the Adleman-Lipton model (Roweis et al., 1999). In this paper, we first use sticker to construct solution space of DNA library sequences for the 3-dimensional matching problem. Then, in the Adleman-Lipton model, we propose an algorithm to remove illegal solution and find legal solution for the 3-dimensional matching problem from solution space of sticker. Finally, a simulation result for our algorithm is generated.

Keywords: molecular supercomputing; DNA-based parallel algorithms; NP-complete Hamiltonian path problem; parallel computing; three-dimensional matching; 3D matching; NP-complete satisfiability; sticker; simulation; high performance computing.

DOI: 10.1504/IJHPCN.2004.007572

International Journal of High Performance Computing and Networking, 2004 Vol.1 No.1/2/3, pp.128 - 139

Published online: 05 Aug 2005 *

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