Using sticker to solve the 3-dimensional matching problem in molecular supercomputers. (8th August 2005)

• Record Type: Journal Article
• Authors: Guo, Minyi; Chang, Weng-Long; Cao, Jiannong
• Is Part Of: International journal of high performance computing and networking. Volume 1:Number 1/2/3(2004)
• Page Start: 128
• Page End: 139
• Publication Date: 2005-08-08
• Subjects: 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; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

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.