In this paper, a DNA based computing model for solving the star coloring problem is proposed. This model shows how to use DNA strands to construct solution space of molecules for the star coloring problem and how to apply the DNA algorithm to solve the star coloring problem using biological operations. The algorithm is highly parallel and has satisfactory fidelity. The time complexity of the algorithm is O (n2), where n is the number of vertices of the graph.
AdlemanL.: Molecular solutions to combinatorial problems. Science.266, 1021–1024, (1994).
2.
SindenR.R.: DNA structure and Function.Academic Press. New York. 1994.
3.
FeynmanR.P. in: GilbertD.H.(Ed.), Minaturization.Reinhold Publishing Corporation. New York. 282–296, (1961).
4.
LiptonR.J.: DNA solution of hard computational problems. Science.268, 542–545, (1995).
5.
RoweisS.WinfreeE.BurgoyneR.ChelyapovN.V.GoodmanM.F.MundRothe P.W.K.AdlemanL.M.: A Sticker based model for DNA computation, in: LandweberL.BaumE. (Eds.), 2nd Annual Workshop on DNA Computing, DIMACS: Series in Discrete Mathematics and theoretical Computer science, American Mathematical Society, Princeton University. 1–29 (1999).
6.
BonehD.DunworthC.LiptonR.J.SgallJ.: On the computational power of DNA, in: Discrete Applied Mathematics. Special Issue on Computational Molecular Biology.71, 79–94 (1996).
7.
PaunG.RozenbergG.SalomaaA.: DNA Computing: New Computing Paradigm.Springer-Verlag. New York. ISBN: 3-540-64196-3 (1998).
8.
AdlemanL.M.: On constructing a molecular computer, DNA Based Computers, in: LiptonR.BaumE. (Eds.), DIMACS series in Discrete Mathematics and Theoretical Computer Science.American Mathematical Society. 1–21 (1996).
9.
GareyM.R.JohnsonD.S.: Computer and intractability.Freeman, San Fransico, CA, 1979.
10.
LiuQinghua: DNA computing on surfaces, Nature.403, 175–179 (2000).
11.
CheeM.: Accessing genetic information with high-density DNA arrays. Science276, 610–614 (1996).
12.
YangYu-XingWangAi-MinMaJi-Ian: Multi-separation based DNA algorithm of graph vertex coloring problem. ICNC7, 547–550 (2008).
13.
LiuYa Chun: DNA solution of graph coloring problem. Journal of chemical information and modeling42(3), 524–528 (2002).
14.
GuoYMiniyi: Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing. Bio systems.80(1), 71–82 (2005).
15.
XingpengJiang: A new DNA algorithm to solve graph coloring problem. Progress in natural science17(6), 733–738 (2007).
16.
WangSYuanJ: DNA computing of directed line-graphs. Communication in mathematical and in computer chemistry56(3), 479–484 (2006).
17.
MarckIsraelZimmermannK. H.: Parallel bioinspired algorithms for NP-complete graph problems. Journal of parallel and distributed computing69(3), 221–229 (2009).
18.
ChengWeng-Long: Towards solution of the set-splitting problem on gel based DNA computing. Future generation computer systems20(5), 875–885 (2004).
19.
JinXu: A DNA computer model for solving vertex coloring problem. Chinesescience bulletin51(20), 2541–2549 (2006).
20.
QiuZhiquan FrankLuMi: A new approach to advance the DNA computing. Applied soft computing3(2), 177–189 (2003).
