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

Minyi Guo, Weng Long Chang, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

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 languageEnglish
Pages (from-to)128-139
Number of pages12
JournalInternational Journal of High Performance Computing and Networking
Volume1
Issue number1-3
Publication statusPublished - 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

Cite this