基于微流控技术图顶点着色问题的DNA计算模型

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

基于微流控技术图顶点着色问题的DNA计算模型

张勋才^1,2, 牛莹², 郗方¹

1. 北京大学信息科学技术学院, 北京 100871;
2. 郑州轻工业学院电气信息工程学院, 郑州 450002

收稿日期:2011-10-12 出版日期:2013-01-01 发布日期:2013-01-01
作者简介:张勋才(1981-),男,博士.研究方向:智能信息处理与优化控制,系统工程.E-mail:zhangxuncai@pku.edu.cn
基金资助:
国家自然科学基金项目(61076103,60910002,60971085);"863"国家高技术研究发展计划项目(2009AA012413);中国博士后科学基金项目(20100470163).

DNA computing model of graph vertex coloring problem based on microfluidics

ZHANG Xun-cai^1,2, NIU Ying², XI Fang¹

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

摘要/Abstract

摘要： 为减少DNA计算中的人为操作,实现对生化操作的精确控制,设计了一种基于微流控技术求解图顶点着色问题的微流控DNA计算模型。通过温度来控制微反应器中DNA链库与磁珠探针的杂交与变性,并利用不同电极间的电位差来驱动DNA分子在微通道内移动以实现整个计算过程。分析表明,采用本文模型可以自动化地求解任意一个图顶点着色问题,提高了DNA计算的可靠性。

关键词: 计算机应用, DNA计算机, 图顶点着色问题, 微流控技术

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

中图分类号:

TP384

张勋才, 牛莹, 郗方. 基于微流控技术图顶点着色问题的DNA计算模型[J]. 吉林大学学报(工学版), 2013, 43(01): 206-211.

ZHANG Xun-cai, NIU Ying, XI Fang. DNA computing model of graph vertex coloring problem based on microfluidics[J]. 吉林大学学报(工学版), 2013, 43(01): 206-211.

参考文献

[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.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed