DocumentCode
2640024
Title
Towards a DNA solution to the shortest common superstring problem
Author
Gloor, Greg ; Kari, Lila ; Gaasenbeek, Michelle ; Yu, Sheng
Author_Institution
Dept. of Biochem., Univ. of Western Ontario, London, Ont., Canada
fYear
1998
fDate
21-23 May 1998
Firstpage
140
Lastpage
145
Abstract
This paper proposes a DNA algorithm for solving an NP-complete problem (the shortest common superstring problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay
Keywords
DNA; biocomputers; encoding; parallel algorithms; simulated annealing; string matching; DNA algorithm; DNA annealing; DNA computing; NP-complete problem; coding; shortest common superstring problem; Biochemistry; Biology computing; Computational biology; Computer science; Control systems; DNA computing; Molecular biophysics; Molecular computing; NP-complete problem; Power supplies;
fLanguage
English
Publisher
ieee
Conference_Titel
Intelligence and Systems, 1998. Proceedings., IEEE International Joint Symposia on
Conference_Location
Rockville, MD
Print_ISBN
0-8186-8548-4
Type
conf
DOI
10.1109/IJSIS.1998.685431
Filename
685431
Link To Document