Using sticker to solve the 3-dimensional matching problem in molecular supercomputers Online publication date: Fri, 05-Aug-2005
by Minyi Guo, Weng-Long Chang, Jiannong Cao
International Journal of High Performance Computing and Networking (IJHPCN), Vol. 1, No. 1/2/3, 2004
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of High Performance Computing and Networking (IJHPCN):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com