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 | 2018-03-01 |
| DOIs | |
| Publication status | Published - 2005 |
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
ASJC Scopus subject areas
- Computer Networks and Communications
- Hardware and Architecture
- Software