基于DNA折纸术求解图的顶点着色问题的方法

麻晶晶; 许进

doi:10.11999/JEIT200203

基于DNA折纸术求解图的顶点着色问题的方法

doi: 10.11999/JEIT200203

麻晶晶^1, ,,
许进²

1.
山西财经大学统计学院太原 030000
2.
北京大学信息科学技术学院北京 100871

基金项目: 国家自然科学基金(61801279)

详细信息

作者简介:
麻晶晶：女，1983年生，讲师，从事生物计算等研究

许进：男，1959年生，教授，从事生物计算等研究

通讯作者:
麻晶晶　casy@pku.edu.cn

中图分类号: O157.6
计量
- 文章访问数: 1218
- HTML全文浏览量: 587
- PDF下载量: 54
- 被引次数: 0
出版历程
- 收稿日期: 2020-03-24
- 修回日期: 2020-08-20
- 网络出版日期: 2020-08-27
- 刊出日期: 2021-06-18

A Method for the Graph Vertex Coloring Problem Based on DNA Origami

Jingjing MA^{1
, ,},
Jin XU²

1.
School of Statistics, Shanxi University of Finance and Economy, Taiyuan 030000, China
2.
School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

Funds: The National Natural Science Foundation of China (61801279)

摘要

摘要: 该文基于DNA折纸术，设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边，由于这些结构具有粘性末端，因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法，可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法，可以极大地降低求解图的顶点着色问题的复杂度。
- DNA计算 /
- DNA折纸术 /
- DNA-纳米颗粒共聚体 /
- 自组装 /
- 顶点着色问题
Abstract: Based on the DNA origami technique, a method for the graph vertex coloring problem is proposed via the self-assembly of DNA origami structures. Utilizing the DNA origami technique different DNA origami structures with specific shapes are constructed. These structures are utilized to encode the information of a graph’s vertices and edges, and because these structures have sticky ends, so they can assemble to advanced structures which stands for different answers of the graph vertex coloring problem via specific molecular hybridization. Utilizing the property of DNA nanoparticle conjugation and electrophoresis as well as other experimental methods, the correct answer of the graph vertex coloring problem can be detected. This method is highly parallel, and can greatly reduce the complexity of the graph vertex coloring problem.
- DNA computing /
- DNA origami /
- DNA-nanoparticle conjugation /
- Self-assembly /
- Graph vertex coloring problem

HTML全文

图 1 一个简单无向图G

下载: 全尺寸图片幻灯片

图 2 编码顶点和边的DNA折纸结构

下载: 全尺寸图片幻灯片

图 3 DNA折纸结构的退火方式

下载: 全尺寸图片幻灯片

图 4 DNA-纳米颗粒共聚体与退火结构的杂交

下载: 全尺寸图片幻灯片

图 5 图G的顶点三着色方案的正确解

下载: 全尺寸图片幻灯片

参考文献(31)

[1]	FEYNMAN R P. There’s plenty of Room at the Bottom[M]. GILBERT D H. Minaturization. New York: Reinhold Publishing Corporation, 1961: 282–296.
[2]	ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021–1024. doi: 10.1126/science.7973651
[3]	BRAICH R S, 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. doi: 10.1126/science.1069528
[4]	BENENSON Y, PAZ-ELIZUR T, ADAR R, et al. Programmable and autonomous computing machine made of biomolecules[J]. Nature, 2001, 414(6862): 430–434. doi: 10.1038/35106533
[5]	LIU Qinghua, WANG Liman, FRUTOS A G, et al. DNA computing on surfaces[J]. Nature, 2000, 403(6766): 175–179. doi: 10.1038/35003155
[6]	SAKAMOTO K, GOUZU H, KOMIYA K, et al. Molecular computation by DNA hairpin formation[J]. Science, 2000, 288(5469): 1223–1226. doi: 10.1126/science.288.5469.1223
[7]	HEAD T, ROZENBERG G, BLADERGROEN R S, et al. Computing with DNA by operating on plasmids[J]. Biosystems, 2000, 57(2): 87–93. doi: 10.1016/S0303-2647(00)00091-5
[8]	JONOSKA N, KARL S A, and SAITO M. Three dimensional DNA structures in computing[J]. Biosystems, 1999, 52(1/3): 143–153. doi: 10.1016/S0303-2647(99)00041-6
[9]	ADLEMAN L, CHENG QI, GOEL A, et al. Running time and program size for self-assembled squares[C]. ACM Symposium on Theory of Computing (STOC), New York, USA, 2001. 740–748. doi: 10.1145/380752.380881.
[10]	MARTIN-VIDE C, PĂUN G, and SALOMAA A. Characterizations of recursively enumerable languages by means of insertion grammars[J]. Theoretical Computer Science, 1998, 205(1/2): 195–205. doi: 10.1016/S0304-3975(97)00079-0
[11]	LIPTON R J. DNA solution of hard computational problems[J]. Science, 1995, 268(5210): 542–545. doi: 10.1126/science.7725098
[12]	ROTHEMUND P. A DNA and restriction enzyme implementation of Turing machines[C]. Proceedings of the DIMACS Workshop, Princeton, USA, 1995.
[13]	OGIHARA M and RAY A. Simulating Boolean circuits on a DNA computer[J]. Algorithmica, 1999, 25(2/3): 239–250. doi: 10.1007/PL00008276
[14]	BENENSON Y, GIL B, BEN-DOR U et al. An autonomous molecular computer for logical control of gene expression[J]. Nature, 2004, 429(6990): 423–429. doi: 10.1038/nature02551
[15]	XU Jin. Probe machine[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(7): 1405–1416. doi: 10.1109/TNNLS.2016.2555845
[16]	WINFREE E, LIU Furong, WENZLER L A, et al. Design and self-assembly of two-dimensional DNA crystals[J]. Nature, 1998, 394(6693): 539–544. doi: 10.1038/28998
[17]	YAN Hao, PARK S H, FINKELSTEIN G et al. DNA-templated self-assembly of protein arrays and highly conductive nanowires[J]. Science, 2003, 301(5641): 1882–1884. doi: 10.1126/science.1089389
[18]	ROTHEMUND P W K. Folding DNA to create nanoscale shapes and patterns[J]. Nature, 2006, 440(7082): 297–302. doi: 10.1038/nature04586
[19]	HAN Dongran, PAL S, NANGREAVE J, et al. DNA origami with complex curvatures in Three-Dimensional space[J]. Science, 2011, 332(6027): 342–346. doi: 10.1126/science.1202998
[20]	ISHIKAWA D, SUZUKI Y, KUROKAWA C, et al. DNA origami Nanoplate-based emulsion with Nanopore function[J]. Angewandte Chemie-International Edition, 2019, 58(43): 15299–15303. doi: 10.1002/anie.201908392
[21]	JOURNOT C M A, RAMAKRISHNA V, WALLACE M I, et al. Modifying membrane morphology and interactions with DNA origami clathrin-mimic networks[J]. ACS Nano, 2019, 13(9): 9973–9979. doi: 10.1021/acsnano.8b07734
[22]	LI Na, SHANG Yingxu, XU Rui et al. Precise organization of metal and metal Oxide Nanoclusters into arbitrary patterns on DNA origami[J]. Journal of the American Chemical Society, 2019, 141(45): 17968–17972. doi: 10.1021/jacs.9b09308
[23]	JOHNSON J A, DEHANKAR A, WINTER J O, et al. Reciprocal control of hierarchical DNA origami-Nanoparticle assemblies[J]. NANO Letters, 2019, 19(12): 8469–8475. doi: 10.1021/acs.nanolett.9b02786
[24]	KLEIN W P, THOMSEN R P, TURNER K B, et al. Enhanced catalysis from multienzyme cascades assembled on a DNA origami triangle[J]. ACS Nano, 2019, 13(12): 13677–13689. doi: 10.1021/acsnano.9b05746
[25]	BERENGUT J F, BERENGUT J C, DOYE J P K, et al. Design and synthesis of pleated DNA origami nanotubes with adjustable diameters[J]. Nucleic Acids Research, 2019, 47(22): 11963–11975. doi: 10.1093/nar/gkz1056
[26]	HAHN J, CHOU L Y T, SØRENSEN R S, et al. Extrusion of RNA from a DNA-origami-based Nanofactory[J]. ACS Nano, 2020, 14(2): 1550–1559. doi: 10.1021/acsnano.9b06466
[27]	ANASTASSACOS F M, ZHAO Zhao, ZENG Yang, et al. Glutaraldehyde cross-linking of Oligolysines coating DNA origami greatly reduces susceptibility to nuclease degradation[J]. Journal of the American Chemical Society, 2020, 142(7): 3311–3315. doi: 10.1021/jacs.9b11698
[28]	BARTNIK K, BARTH A, PILO-PAIS M, et al. A DNA origami platform for single-pair Förster resonance energy transfer investigation of DNA-DNA interactions and ligation[J]. Journal of the American Chemical Society, 2020, 142(2): 815–825. doi: 10.1021/jacs.9b09093
[29]	殷志祥, 唐震, 张强, 等. 基于DNA折纸基底的与非门计算模型[J]. 电子与信息学报, 2020, 42(6): 1355–1364. doi: 10.11999/JEIT190825 YIN Zhixiang, TANG Zhen, ZHANG Qiang, et al. NAND gate computational model based on the DNA origami template[J]. Journal of Electronics &Information Technology, 2020, 42(6): 1355–1364. doi: 10.11999/JEIT190825
[30]	王君珂, 印珏, 牛人杰, 等. DNA计算与DNA纳米技术[J]. 电子与信息学报, 2020, 42(6): 1313–1325. doi: 10.11999/JEIT190826 WANG Junke, YIN Jue, NIU Renjie, et al. DNA computing and DNA Nanotechnology[J]. Journal of Electronics &Information Technology, 2020, 42(6): 1313–1325. doi: 10.11999/JEIT190826
[31]	XU Jin, QIANG Xiaoli, ZHANG Kai, et al. A DNA computing model for the Graph Vertex Coloring problem based on a probe graph[J]. Engineering, 2018, 4(1): 61–77. doi: 10.1016/j.eng.2018.02.011