吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 206-211.

Previous Articles     Next Articles

DNA computing model of graph vertex coloring problem based on microfluidics

ZHANG Xun-cai1,2, NIU Ying2, XI Fang1   

  1. 1. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;
    2. College of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China
  • Received:2011-10-12 Online:2013-01-01 Published:2013-01-01

PDF (PC)

259

Abstract: A novel kind of DNA computing model for graph vertex coloring problem is proposed based on microfluidics. This model can not only improve the reliability of DNA computing, but also reduce the computing time and experiment operation. The hardware structure of the model is described. The operation steps are introduced using a case study. The simulation results show that this computing model can be used to solve any instances of graph coloring problem automatically.

Key words: computer application, DNA computing, graph vertex coloring problem, microfluidic

CLC Number: 

  • TP384
[1] Adleman L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021-1024.

[2] Lipton R J. DNA solution of hard computational problems[J]. Science, 1995, 268(5210): 542-544.

[3] Ouyang Q, Kaplan P D, Liu S, et al. DNA solution of the maximal clique problem[J]. Science, 1997, 278(5337): 446-449.

[4] Braich R, Chelyapov N, Johnson C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J]. Science, 2002, 296(5567): 499-502.

[5] Ignatova Z, Martinez-Perez I, Zimmerman K H. DNA Computing Models[M]. Berlin: Springer, 2008.

[6] Gehani A, Reif J. Micro-flow bio-molecular computation[J]. Biosystems, 1999, 52: 197-216.

[7] McCaskill J S. Optically programming DNA computing in microflow reactors[J]. Biosystems, 2001, 59(2): 125-138.

[8] Van Noort D, Gast F U, McCaskill J S. DNA computing in microreactors//Jonoska N, Seeman N. DNA Computing: 7th International Meeting on DNA-Based Computers, Berlin: Springer, 2002:33-45.

[9] Van Noort D. A programmable molecular computer in microreactors//Ferretti C, Mauri G, Zandron C, 10th International Workshop on DNA Computing, Berlin: Springer, 2005: 365-374.

[10] Van Noort D, Landweber L. Towards a reprogrammable DNA computer[J]. Natural Computing, 2005, 4(2):163-175.

[11] Van Noort D, Tang Z L, Landweber L F. Fully controllable microfluidics for molecular computers[J]. Journal of the Association for Laboratory Automation, 2004, 9(5):285-290.

[12] Grover W H, Mathies R A. An integrated microfluidic processor for single nucleotide polymorphism-based DNA computing[J]. Lab on a Chip, 2005, 5(10): 1033-1040.

[13] Livstone M S, Weiss R, Landweber L F. Automated design and programming of a microfluidic DNA computer[J]. Natural Computing, 2006,5(1): 1-13.

[14] Ran T, Kaplan S, Shapiro E. Molecular implementation of simple logic programs[J]. Nature Nanotechnology, 2009, 4(10):642-648.

[15] Thies W, Urbanski J P, Thorsen T, et al. Abstraction layers for scalable microfluidic biocomputing[J]. Natural Computing, 2008, 7(2): 255-275.

[16] Dutse S W, Yusof N A. Microfluidics-based lab-on-chip systems in DNA-based biosensing: an overview[J]. Sensors, 2011, 11(6): 5754-5768.

[17] Liu W, Xu J. A DNA algorithm for the graph coloring problem[J]. Journal of Chemical Information and Computers, 2002, 42(5): 1176-1178.

[18] Gao L, Xu J. A DNA algorithm for graph vertex coloring problem[J]. Acta Electronica Sinic, 2003, 31(4): 494-496.

[19] Xu J, Qiang X L, Fang G,et al. A DNA computer model for solving vertex coloring problem[J]. Chinese Science Bulletin, 2006, 51(20): 2541-2549.

[20] Shaikh F A, Ugaz V M. Collection, focusing and metering of DNA in microchannels using addressable electrode arrays for portable low-power bioanalysis[J]. PNAS, 2006, 103(13):4825-4830.
[1] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd