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

Jingjing MA; Jin XU

doi:10.11999/JEIT200203

Volume 43 Issue 6

Jun. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(6): 1750-1755

Jingjing MA, Jin XU. A Method for the Graph Vertex Coloring Problem Based on DNA Origami[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1750-1755. doi: 10.11999/JEIT200203

Citation:

Jingjing MA, Jin XU. A Method for the Graph Vertex Coloring Problem Based on DNA Origami[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1750-1755. doi: 10.11999/JEIT200203

Jingjing MA, Jin XU. A Method for the Graph Vertex Coloring Problem Based on DNA Origami[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1750-1755. doi: 10.11999/JEIT200203

Citation:

Jingjing MA, Jin XU. A Method for the Graph Vertex Coloring Problem Based on DNA Origami[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1750-1755. doi: 10.11999/JEIT200203

PDF( 892 KB)

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

doi: 10.11999/JEIT200203

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)

Received Date: 2020-03-24
Rev Recd Date: 2020-08-20

Available Online: 2020-08-27

Publish Date: 2021-06-18

Abstract

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

FullText(HTML)

References(31)

References

[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