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

M. Guo, W.L. Chang, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 number2018-03-01
DOIs
Publication statusPublished - 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

Cite this