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.
| Original language | English |
|---|---|
| Pages (from-to) | 128-139 |
| Number of pages | 12 |
| Journal | International Journal of High Performance Computing and Networking |
| Volume | 1 |
| Issue number | 1-3 |
| Publication status | Published - 1 Jan 2004 |
Keywords
- DNA-based parallel algorithms
- molecular supercomputing
- parallel computing
- the NP-complete problem
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications