An Unenumerative DNA Computing Model for Vertex Coloring Problem

Author

Xu, Jin ; Qiang, Xiaoli ; Yang, Yan ; Wang, Baoju ; Yang, Dongliang ; Luo, Liang ; Pan, Linqiang ; Wang, Shudong

Author_Institution

Key Lab. of High Confidence Software Technol. of Minist. of Educ., Peking Univ., Beijing, China

Volume

10

Issue

2

fYear

2011

fDate

6/1/2011 12:00:00 AM

Firstpage

94

Lastpage

98

Abstract

The solution space exponential explosion caused by the enumeration of the candidate solutions maybe is the biggest obstacle in DNA computing. In the paper, a new unenumerative DNA computing model for graph vertex coloring problem is presented based on two techniques: 1) ordering the vertex sequence for a given graph in such a way that any two consecutive labeled vertices i and i+1 should be adjacent in the graph as much as possible; 2) reducing the number of encodings representing colors according to the construture of the given graph. A graph with 12 vertices without triangles is solved and its initial solution space includes only 283 DNA strands, which is 0.0532 of 3¹² (the worst complexity).

Keywords

DNA; biocomputing; graph colouring; molecular biophysics; vertex functions; DNA strands; graph vertex coloring problem; solution space exponential explosion; two-consecutive labeled vertices; unenumerative DNA computing model; vertex sequence; worst complexity; Biological system modeling; Color; Computational modeling; DNA; DNA computing; Libraries; Probes; DNA computing; polymerase chain reaction; vertex coloring; Base Sequence; Color; Computational Biology; Computer Simulation; Computers, Molecular; DNA; DNA Probes; Electrophoresis, Agar Gel; Molecular Sequence Data; Polymerase Chain Reaction;

fLanguage

English

Journal_Title

NanoBioscience, IEEE Transactions on

Publisher

ieee

ISSN

1536-1241

Type

jour

DOI

10.1109/TNB.2011.2160996

Filename

5942174