Biomics

Three decades ago, in November 1994, L.Adleman's landmark article was published on molecular computings using synthetic DNA fragments, with which he awakened the dormant interest of a number of researchers in the non-biological application of this biopolymer. Adleman, using a set of oligonucleotides by ligating them with T4 DNA ligase and some other molecular biological operations, "found" a path in the Hamiltonian graph of seven vertices, which he himself paved. And it was a model experiment that showed the fundamental possibility of conducting DNA computations based on Boolean algebra using DNA molecules and solving super-heavy tasks with fuzzy logic, characterized by complexity O(N!), in polynomial time, which is often impossible for classical electronic computers. However, after his article was followed in part by a fair and powerful criticism, which boils down to the need to handle a huge amount of DNA, which, according to some values, exceeds the weight of our Planet for a number of tasks. Nevertheless, the stimulus for the development of DNA computing has been given, and over the past time a huge number of works have been published, which describe many fundamentally different approaches that allow to operate with nucleic acids, assigning them computer "0" and "1", using them as logical DNA gates with the formation of whole cascades from them, and it is also simple to encode certain circumstances with oligonucleotides and form complex nanoconstructions suitable for molecular computations. This review briefly examines the features of a unique natural biopolymer, which is DNA, making it possible to use it for molecular computations based on various principles. However, it should be recognized that the first very optimistic expectations from DNA computing have not yet been fulfilled, although noticeable progress in molecular biological technologies in recent years allows to hope for further improvement of DNA computing and opportunities for them to occupy their niche, including being realized in the form of a working DNA computers. Some attention has also been paid to their competitors in the form of quantum computers based on various physical principles, which it is possible that in the future they will be able to use DNA molecules in the form of their non-natural analogues, carrying the necessary modifications to ensure quantum entanglement and quantum supremacy.

DNA computing, DNA computer, L.Adleman, Hamiltonian graph, DNA gates, Boolean algebra, quantum vcomputer

1. Adar R, Benenson Y, Linshiz G, Rosner A, Tishby N, Shapiro E. Stochastic computing with biomolecular automata. Proc Natl Acad Sci USA. 2004. V.101(27). P.9960-9965. doi: 10.1073/pnas.0400731101

2. Adleman LM. Molecular computation of solutions to combinatorial problems. Science. 1994. V.266(5187). P.1021-1024. DOI: 10.1126/science.79736513. Adleman LM. Response. Science. 1995. V.268(5210). P.483-484. DOI: 10.1126/science.268.5210.483

4. Adleman L. Computing with DNA. Scientific American. 1998. V.279. P.34-41. doi: 10.1038/scientificamerican0898-54

5. Adleman LM, Rothemund PW, Roweis S, Winfree E. On applying molecular computation to the data encryption standard. J Comput Biol. 1999. V.6(1). P.53-63. doi: 10.1089/cmb.1999.6.53

6. Akin HE, Karabay DA, Kyle JR, Mills AP Jr, Ozkan CS, Ozkan M. Electronic microarrays in DNA computing. J Nanosci Nanotechnol. 2011. V.11(6). P.4717-4723. doi: 10.1166/jnn.2011.38844717

7. Alferov Zh.I., Aseev A.L., Gaponov S.V., Kop'ev P., Panov V.I., Poltorackij Je.A., Sibel'din N.N., Suris R.A. Nanomaterialy i nanotehnologii. Mikrosistemnaja tehnika. 2003. № 8. S. 3-13. [Nanomaterials and nanotechnologies] (In Russian)

8. Aoi Y, Yoshinobu T, Tanizawa K, Kinoshita K, Iwasaki H. Ligation errors in DNA computing. Biosystems. 1999. V.52(1-3). P.181-187. doi: 10.1016/s0303-2647(99)00045-3

9. Bancroft C., Bowler T., Bloom B., Clelland C.T. Long-term storage of information in DNA. Science. 2001. V.293(5536). P.1763-1765. DOI: 10.1126/science.293.5536.1763c

10. Beaver D. Computing with DNA. J Comput Biol. 1995. V.2(1). P.1-7. doi: 10.1089/cmb.1995.2.1

11. Benenson Y, Adar R, Paz-Elizur T, Livneh Z, Shapiro E. DNA molecule provides a computing machine with both data and fuel. Proc Natl Acad Sci USA. 2003. V.100(5). P.2191-2196. doi: 10.1073/pnas.0535624100

12. Benenson Y, Gil B, Ben-Dor U, Adar R, Shapiro E. An autonomous molecular computer for logical control of gene expression. Nature. 2004. V.429(6990). P.423-429. doi: 10.1038/nature02551

13. Benenson Y, Paz-Elizur T, Adar R, Keinan E, Livneh Z, Shapiro E. Programmable and autonomous computing machine made of biomolecules. Nature. 2001. V.414(6862). P.430-434. doi: 10.1038/35106533

14. Bikbulatova SM, Mingazetdinova SR, Chemeris AV, Vakhitov VA. In Vitro Evolution – Is There Any Limit for Methods of Gene Shuffling? Uspekhi sovremennoi Biologii. 2009. V.129(4). P.323-335. (In Russian)

15. Boneh D., Dunworth C., Lipton R.J. Breaking DES using a molecular computer. In: R. J. Lipton and E. B. Baum, Eds., DNA Based Computers: Proceedings of a DIMACS Workshop, Princeton, 1996. P.37-66.

16. Braich RS, Chelyapov N, Johnson C, Rothemund PW, Adleman L. Solution of a 20-variable 3-SAT problem on a DNA computer. Science. 2002. V.296(5567). P.499-502. doi: 10.1126/science.1069528

17. Braich RS, Johnson C, Rothemund PWK, Hwang D, Chelyapov N, Adleman LM. Solution of a satisfiability problem on a gel-based DNA computer. In: Condon E. (ed.). DNA2000. LNCS 2054. 2001. P.27-42.

18. Bui H, Shah S, Mokhtar R, Song T, Garg S, Reif J. Localized DNA Hybridization Chain Reactions on DNA Origami. ACS Nano. 2018. V.12(2). P.1146-1155. doi: 10.1021/acsnano.7b06699

19. Bunow B. On the potential of molecular computing. Science. 1995. V.268(5210). P.482-483. doi: 10.1126/science.7725087

20. Byrne J., Dahm R. Friedrich Miescher and the 150 th anniversary of the discovery of DNA. Biomics. 2019. V.11(3). P. 249-258. DOI: 10.31301/2221-6197.bmcs.2019-23

21. Cardelli L. Strand algebras for DNA computing. Nat. Comp. 2011. V.10. P.407-428.

22. Chang WL, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the AdlemanLipton model. Biosystems. 2003. V.72(3). P.263-275. doi: 10.1016/s0303-2647(03)00149-7

23. Chang WL, Ho MS, Guo M. Molecular solutions for the subset-sum problem on DNA-based supercomputing. Biosystems. 2004. V.73(2). P.117-130. doi: 10.1016/j.biosystems.2003.11.001

24. Chang WL, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the AdlemanLipton model. Biosystems. 2003. V.72(3). P.263-275. doi: 10.1016/s0303-2647(03)00149-7

25. Chatterjee G, Dalchau N, Muscat RA, Phillips A, Seelig G. A spatially localized architecture for fast and modular DNA computing. Nat Nanotechnol. 2017. V.12(9). P.920-927. doi: 10.1038/nnano.2017.127

26. Chemeris D.A., Kiryanova O.Yu., Gubaydullin I.M., Chemeris A.V. Design of primers for polymerase chain reaction (Brief review of software and databases). Biomics. 2016. V. 8(3). P.215-238. (In Russian)

27. Chemeris DA, Nikonorov YM, Vakhitov VA. Realtime hybridization chain reaction. Dokl Biochem Biophys. 2008. V.419. P.53-55. doi: 10.1134/s1607672908020014

28. Chemeris D.A., Kuluev B.R., Patrushev M.V., Garafutdinov R.R., Chemeris A.V. Progress in sequencing of the complete haplotype-resolved diploid genomes of plants. Biomics. 2023. V.15(4). P. 297-309. DOI: 10.31301/2221-6197.bmcs.2023-26

29. Chen RC, Yang SJ. Applying DNA computation to intractable problems in social network analysis. Biosystems. 2010. V.101(3). P.222-232. doi: 10.1016/j.biosystems.2010.05.006

30. Chen X, Ellington AD. Shaping up nucleic acid computation. Curr Opin Biotechnol. 2010. V.21(4). P.392-400. doi: 10.1016/j.copbio.2010.05.003

31. Chen X, Liu X, Wang F, Li S, Chen C, Qiang X, Shi X. Massively Parallel DNA Computing Based on Domino DNA Strand Displacement Logic Gates. ACS Synth Biol. 2022. V.11(7). P.2504-2512. doi: 10.1021/acssynbio.2c00270

32. Church G.M., Gao Y., Kosuri S. Next-generation digital information storage in DNA. Science. 2012.V.337(6102). P.1628. DOI: 10.1126/science.1226355

33. Clelland C.T., Risca V., Bancroft C. Hiding messages in DNA microdots. Nature. 1999. V.399(6736). P.533-534. DOI: 10.1038/21092

34. Conrad M. Molecular computing. Advances in Computers. 1990. V.31. P.235-324. doi: 10.1016/S0065-2458(08)60155-2

35. Davis J. Microvenus. Art Journal. 1996. V. 55(1). P. 70-74. DOI: 10.2307/777811

36. Dolenko T.A., Burikov S.A., Vervald E.N., Efitorov A.O., Laptinskiy K.A., Sarmanova O.E., Dolenko S.A. Improvement of reliability of molecular DNA computing: solution of inverse problem of Raman spectroscopy using artificial neural networks. Laser Physics. 2017. V.27(2). 025203. DOI 10.1088/1555-6611/aa51a7

37. Dunn KE, Trefzer MA, Johnson S, Tyrrell AM. Towards a Bioelectronic Computer: A Theoretical Study of a Multi-Layer Biomolecular Computing System That Can Process Electronic Inputs. Int J Mol Sci. 2018. V.19(9). 2620. doi: 10.3390/ijms19092620

38. Faulhammer D, Cukras AR, Lipton RJ, Landweber LF. Molecular computation: RNA solutions to chess problems. Proc Natl Acad Sci USA. 2000. V.97(4). P.1385-1389. doi: 10.1073/pnas.97.4.1385

39. Feng G, Hou S-Y, Zou H. et al. SpinQ Triangulum: a commercial three-qubit desktop quantum computer. arXiv. 2022. 2202.02983v1.

40. Feynman R.P. There's Plenty of Room at the Bottom: An Invitation to Enter a New Field of Physics. Engineering and Science (California Institute of Technology). 1960. V23. P.22-36.

41. Franco G, Manca V. Algorithmic applications of XPCR. Natural Computing. 2011. V.10(2). P. 805 – 819. doi: 10.1007/s11047-010-9199-8

42. Frezza BM, Cockroft SL, Ghadiri MR. Modular multi-level circuits from immobilized DNA-based logic gates. J Am Chem Soc. 2007. V.129(48). P.14875-14879. doi: 10.1021/ja0710149

43. Frutos AG, Liu Q, Thiel AJ, Sanner AM, Condon AE, Smith LM, Corn RM. Demonstration of a word design strategy for DNA computing on surfaces. Nucleic Acids Res. 1997. V.25(23). P.4748-4757. DOI: 10.1093/nar/25.23.4748

44. Frutos A.G., Smith, L.M., Corn R.M. Enzymatic ligation reactions of DNA "words" on surfaces for DNA computing. Journal of the American Chemical Society. 1998. V. 120. P. 10277-10282.

45. Fu R, Hou J, Wang Z, Xianyu Y. DNA Molecular Computation Using the CRISPR-Mediated Reaction and Surface Growth of Gold Nanoparticles. ACS Nano. 2024. V.18(22). P.14754-14763. doi: 10.1021/acsnano.4c04265

46. Garafutdinov R.R., Baymiev An.Kh., Maleev G.V., Alexeyev Ya.I., Zubov V.V., Chemeris D.A., Kiryanova J.Yu., Gubaydullin I.M., Matniyazov R.T., Sakhabutdinova A.R., Nikonorov Yu.M., Kuluev B.R., Baymiev Al.Kh., Chemeris A.V. Diversity of PCR primers and principles of their design. Biomics. 2019. V.11(1). P. 23 – 70. DOI: 10.31301/2221-
6197.bmcs.2019-04 (In Russian)

47. Garafutdinov RR, Chemeris DA, Sakhabutdinova AR, Kiryanova OY, Mikhaylenko CI, Chemeris AV. Encoding of non-biological information for its long-term storage in DNA. Biosystems. 2022. V.215-216. 104664. doi:
10.1016/j.biosystems.2022.104664

48. Garafutdinov RR, Sakhabutdinova AR, Slominsky PA, Aminev FG, Chemeris AV. A new digital approach
to SNP encoding for DNA identification. Forensic Sci Int. 2020. V. 317. 110520. doi: 10.1016/j.forsciint.2020.110520

49. Gehani A, Reif J. Micro flow bio-molecular computation. Biosystems. 1999. V.52(1-3). P.197-216.
doi: 10.1016/s0303-2647(99)00048-9
50. Geng H, Yin Z, Zhou C, Guo C. Construction of a simple and intelligent DNA-based computing system for multiplexing logic operations. Acta Biomater. 2020. V.118. P.44-53. doi: 10.1016/j.actbio.2020.09.054

51. Gerashchenkov G.A., Garafutdinov R.R., Baymiev An.Kh., Kuluev B.R., Baymiev Al.Kh., Chemeris A.V. The two greatest discoveries of two centuries - the nuclein and the double helix of DNA. Biomics. 2019. V.11(3). P. 259-265. DOI: 10.31301/2221-6197.bmcs.2019-24 (In Russian)

52. Gerasimova YV, Kolpashchikov DM. Connectable DNA logic gates: OR and XOR logics. Chem Asian J. 2012. 7(3). P.534-540. doi: 10.1002/asia.201100664

53. Gerasimova YV, Kolpashchikov DM. Divide and control: split design of multi-input DNA logic gates. Chem Commun (Camb). 2015. V.51(5). P.870-872. doi: 10.1039/c4cc08241a

54. Gerasimova YV, Kolpashchikov DM. Towards a DNA Nanoprocessor: Reusable Tile-Integrated DNA Circuits. Angew Chem Int Ed Engl. 2016. V.55(35). P.10244-10247. doi: 10.1002/anie.201603265

55. Gifford DK. On the path to computation with DNA. Science. 1994. V.266(5187). P.993-994. doi: 10.1126/science.7973681

56. Grover WH, Mathies RA. An integrated microfluidic processor for single nucleotide polymorphism-based DNA computing. Lab Chip. 2005. V.5(10). P.1033-1040. doi: 10.1039/b505840f

57. Guo Y., Wei B., Sun X., Yao D., Zhou X., Xiao S., Liang H. DNA and DNA computation based on toeholdmediated strand displacement reactions. International Journal of Modern Physics B. 2018. V.32(18). 1840014 (2018) doi: 10.1142/S0217979218400143

58. Harding BI, Pollak NM, Stefanovic D, Macdonald J. Repeated Reuse of Deoxyribozyme-Based Logic Gates.Nano Lett. 2019. V.19(11). P.7655-7661. doi: 10.1021/acs.nanolett.9b02326

59. Hartmanis J. On the weight of computation. EATCS Bulletin. 1995. No 55. P.136-138.

60. He S, Cui R, Zhang Y, Yang Y, Xu Z, Wang S, Dang P, Dang K, Ye Q, Liu Y. Design and Realization of Triple dsDNA Nanocomputing Circuits in Microfluidic Chips. ACS Appl Mater Interfaces. 2022. V.14(8). P.10721-10728. doi: 10.1021/acsami.1c24220

61. Hou S-Y, Feng G, Wu Z. et al. SpinQ Gemini: a desktop quantum computer for education and research. arXiv. 2021. 2101.10017v2.

62. James KD, Boles AR, Henckel D, Ellington AD. The fidelity of template-directed oligonucleotide ligation and its relevance to DNA computation. Nucleic Acids Res. 1998. V.26(22). P.5203-5211. doi: 10.1093/nar/26.22.5203

63. Jingjing MA. Three-input logic gate based on DNA strand displacement reaction. Sci Rep. 2023. V.13(1). 15210. doi: 10.1038/s41598-023-42383-9

64. Jonoska N, Karl SA, Saito M. Three dimensional DNA structures in computing. Biosystems. 1999. V.52(1-3). P.143-153. doi: 10.1016/s0303-2647(99)00041-6

65. Judy R.W, Clough R.W. Soviet Computing in the 1980s: A Survey of the Software and Its Applications. Advances in Computers. 1990. V.30, P.223-306. doi: 10.1016/S0065-2458(08)60301-0

66. Ibrahim Z, Tsuboi Y, Ono O. Hybridization-ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for directproportional length-based DNA computing. IEEE Trans Nanobioscience. 2006. V.5(2). P.103-109. doi: 10.1109/tnb.2006.875043

67. Interview. Machines smarter than men? U.S. News & World Report. 1964. Feb., 24. P.84-86.

68. Kaplan PD, Ouyang Q, Thaler DS, Libchaber A. Parallel overlap assembly for the construction of computational DNA libraries. J Theor Biol. 1997. V.188(3). P.333-341. doi: 10.1006/jtbi.1997.0475

69. Karavaeva O.V., Rostovtsev V.S. Apparatnaja realizacija DNK-processora. Perspektivy nauki. 2010. No.6. S.1-4. [Hardware implementation of DNA-based processor] (In Russian)

70. Kari, L., Păun, G., Rozenberg, G. et al. DNA computing, sticker systems, and universality. Acta Informatica. 1998. V. 35. P. 401–420. doi: 10.1007/s002360050125

71. Kiryanova O.Y., Garafutdinov R.R., Gubaydullin I.M., Chemeris A.V. A novel approach to encode melodies in DNA. Biosystems. 2024. V.237. 105136. doi: 10.1016/j.biosystems.2024.105136

72. Komiya K, Sakamoto K, Kameda A, Yamamoto M, Ohuchi A, Kiga D, Yokoyama S, Hagiya M. DNA polymerase programmed with a hairpin DNA incorporates a multiple-instruction architecture into molecular computing. Biosystems. 2006. V.83(1). P.18-25. doi: 10.1016/j.biosystems.2005.07.005

73. Kuluev B.R., Baymiev An.Kh., Gerashchenkov G.A., Yunusbaev U.B., Garafutdinov R.R., Alekseev Ya.I., Baymiev Al.Kh., Chemeris A.V. One hundred years of haploid genomes. Now time comes for diploid genomes. Biomics. 2020. Vol. 12(4). P. 411-434. DOI: 10.31301/2221-6197.bmcs.2020-33 (In Russian)

74. Lee JY, Shin SY, Park TH, Zhang BT. Solving traveling salesman problems with DNA molecules encoding numerical values. Biosystems. 2004. V.78(1-3). P.39-47. doi: 10.1016/j.biosystems.2004.06.005

75. Lee CM, Kim SW, Kim SM, Sohn U. DNA computing the Hamiltonian path problem. Mol Cells. 1999. V.9(5). P.464-469.

76. Lee W, Yu M, Lim D, Kang T, Song Y. Programmable DNA-Based Boolean Logic Microfluidic Processing Unit. ACS Nano. 2021. V.15(7). P.11644-11654. doi: 10.1021/acsnano.1c02153

77. Li D, Li X, Huang H, Li X. Scalability of the surfacebased DNA algorithm for 3-SAT. Biosystems. 2006.V.85(2). P.95-98. doi: 10.1016/j.biosystems.2005.12.002

78. Li D, Huang H, Li X, Li X. Hairpin formation in DNA computation presents limits for large NP-complete problems. Biosystems. 2003. V.72(3). P.203-207. doi: 10.1016/s0303-2647(03)00145-x

79. Li D, Li X, Huang H, Li X. The surface-based approach for DNA computation is unreliable for SAT. Biosystems. 2005. V.82(1). P.20-25. doi: 10.1016/j.biosystems.2005.05.007

80. Lin CH, Cheng HP, Yang CB, Yang CN. Solving satisfiability problems using a novel microarray-based DNA computer. Biosystems. 2007. V.90(1). P.242-252. doi: 10.1016/j.biosystems.2006.08.009

81. Linial M, Linial N. On the potential of molecular computing. Science. 1995. V.268(5210). P.481. DOI: 10.1126/science.7725085

82. Lipton RJ. DNA solution of hard computational problems. Science. 1995. V.268(5210). P.542-545. DOI: 10.1126/science.7725098

83. Liu Q, Frutos AG, Thiel AJ, Corn RM, Smith LM. DNA computing on surfaces: encoding information at the single base level. J Comput Biol. 1998. V.5(2). P.269-278. DOI: 10.1089/cmb.1998.5.269

84. Liu Q, Wang L, Frutos AG, Condon AE, Corn RM, Smith LM. DNA computing on surfaces. Nature. 2000. V.403(6766). P.175-179. DOI: 10.1038/35003155

85. Liu LS, Leung HM, Cai Y, Lo PK. Recent progress in stimuli-responsive DNA-based logic gates: Design, working principles and biological applications. Smart Molecules. 2024. V.2. e20230023. doi: 10.1002/smo.20230023

86. Lo YM, Yiu KF, Wong SL. On the potential of molecular computing. Science. 1995. V.268(5210). P.481-482. DOI: 10.1126/science.7725086

87. Lv H, Xie N, Li M, Dong M, Sun C, Zhang Q, Zhao L, Li J, Zuo X, Chen H, Wang F, Fan C. DNA-based programmable gate arrays for general-purpose DNA computing. Nature. 2023. V.622(7982). P.292-300. doi: 10.1038/s41586-023-06484-9

88. McCaskill JS. Optically programming DNA computing in microflow reactors. Biosystems. 2001. V.59(2). P.125-138. doi: 10.1016/s0303-2647(01)00099-5

89. Malinetsky G.G., Mitin N.A., Naumenko S.A. Nanobiologija i sinergetika. Problemy i idei. Nanotehnika. 2007. No.2. S.103-132. [Nanobiology and synergetics. Problems and ideas] (In Russian)

90. Malinetsky G.G., Naumenko S.A. Vychislenija na DNK. Eksperimenty. Modeli. Algoritmy. Instrumental'nye sredstva. Informacionnye tehnologii i vychislitel'nye sistemy. 2006. No. 1. S.5-27. [Calculations on DNA. Experiments. Models. Algorithms. Instrumental tools] (In Russian)

91. Malinetsky G.G., Naumenko S.A. Vychislenija na DNK. Jeksperimenty. Modeli. Algoritmy. Instrumental'nye sredstva. Preprinty IPM im. M.V. Keldysha. 2005. S.1-24. [Experiments. Models. Algorithms. Instrumental tools] (In Russian)

92. Manca V, Franco G. Computing by polymerase chain reaction. Math Biosci. 2008. V.211(2). P.282-298. doi: 10.1016/j.mbs.2007.08.010

93. Mao C, LaBean TH, Relf JH, Seeman NC. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature. 2000. V.407(6803).P.493-496. doi: 10.1038/35035038

94. Mao X, Liu M, Li Q, Fan C, Zuo X. DNA-Based Molecular Machines. JACS Au. 2022. V.2(11). P.2381-2399. doi: 10.1021/jacsau.2c00292

95. Montagud-Martinez R, Heras-Hernandez M, Goiriz L, Daros JA, Rodrigo G. CRISPR-Mediated Strand Displacement Logic Circuits with Toehold-Free DNA. ACS Synth Biol. 2021. V.10(5). P.950-956. doi: 10.1021/acssynbio.0c00649

96. Morton N.E. Parameters of the human genome. Proc.Natl. Acad. Sci. USA. 1991. V. 88. P. 7474-7476. doi: 10.1073/pnas.88.17.7474

97. Neiman M.S. Some fundamental issues of microminiaturisation. Radiotekhnika. 1964. V.19(1). P. 3-12. (In Russian)

98. Neiman M.S. On the relationships between the reliability, performance and degree of microminiaturisation at the molecular-atomic level. Radiotekhnika. 1965. V.20(1). P. 1-9. (In Russian)

99. Neiman M.S. On the molecular memory systems and the directed mutations. Radiotekhnika. 1965a. V.20(6). P.
1-8. (In Russian)

100.Nikitin MP. Non-complementary strand commutation as a fundamental alternative for information processing by DNA and gene regulation. Nat Chem. 2023. V.15(1). P.70-82. doi: 10.1038/s41557-022-01111-y

101.Nishikawa, A., Yamamura, M. & Hagiya, M. DNA computation simulator based on abstract bases. Soft Computing. 2001. V.5. P.25–38. doi: 10.1007/s005000000062

102.Ozhigov Yu.I. Quantum computer. Moscow. MAKS Press. 2020. 172 P.

103. Ozhigov, Yu.I. Kvantovyj komp'juter: uchebnoe posobie. 2-e izd., dop. i pererab. Moskva : Izdatel'stvo Moskovskogo universiteta. 2023. 326 S. [Quantum computer: a textbook] (In Russian)

104.Okamoto A, Tanaka K, Saito I. DNA logic gates. J Am Chem Soc. 2004. V.126(30). P.9458-9463. doi: 10.1021/ja047628k

105.O'Steen MR, Cornett EM, Kolpashchikov DM. Nuclease-containing media for resettable operation of DNA logic gates. Chem Commun (Camb). 2015. V.51(8). P.1429-1431. doi: 10.1039/c4cc09283j

106.Ouyang Q, Kaplan PD, Liu S, Libchaber A. DNA solution of the maximal clique problem. Science. 1997. V.278(5337). P.446-449. doi: 10.1126/science.278.5337.446

107.Paun G., Rozenberg G., Salomaa A. DNA computing. New computing paradigms. Springer. 1998

108.Pei Y, Bian T, Liu Y, Liu Y, Xie Y, Song J. SingleMolecule Resettable DNA Computing via Magnetic Tweezers. Nano Lett. 2022. V.22(7). P.3003-3010. doi: 10.1021/acs.nanolett.2c00183

109.Petoukhov SV, Petukhova ES, Svirin VI. Symmetries of DNA alphabets and quantum informational formalisms. Symmetry: Culture and Science. 2019. V.30(2). P.161-179. doi: 10.26830/symmetry_2019_2_161

110.Penchovsky R, Ackermann J. DNA library design for molecular computation. J Comput Biol. 2003. V.10(2). P.215-229. doi: 10.1089/106652703321825973

111.Pirrung M.C., Connors R.A., Odenbaugh A.L., Montague-Smith M.P., Walcott N.G., Tollett J.J. The Arrayed Primer Extension Method for DNA Microchip Analysis. Molecular Computation of Satisfaction Problems. J. Am. Chem. Soc. 2000. V.122(9). P. 1873–1882. doi: 10.1021/ja992392j

112.Polenov A.S. Arhitektura DNK-podsistemy gibridnogo komp'jutera na baze rasshirennoj stikernoj modeli DNK-vychislenij. Nauka i biznes: puti razitija. 2015. No. 8. S.49-51. [Architecture of hybrid computer DNA-subsystem based on extended sticker model of DNA-computation] (In Russian)

113.Polenov A.S. Programmnyj interfejs dlja DNKpodsistemy gibridnogo komp'jutera na baze rasshirennoj stikernoj modeli DNK-vychislenij. Global'nyj nauchnyj potencial. 2016. No. 12. S.133-135. [Software interface for the DNA subsystem of a hybrid computer based on an extended sticker model of DNA computing] (In Russian)

114.Polenov A.S., Krotov L.N. Rasshirennaja stikernaja model' dlja DNK-vychislenij. Estestvennye i tehnicheskie nauki. 2016. No.12. Sju269-272. [Extended sticker model for DNA computing] (In Russian)

115.Pool R. A boom in plans for DNA computing. Science. 1995. V.268(5210). P.498-499. doi: 10.1126/science.7725093

116.Porubsky D, Vollger MR, Harvey WT, Rozanski AN, Ebert P, Hickey G, Hasenfeld P, Sanders AD, Stober C; Human Pangenome Reference Consortium; Korbel JO, Paten B, Marschall T, Eichler EE. Gaps and complex structurally variant loci in phased genome assemblies. Genome Res. 2023. V.33(4). P.496-510. doi: 10.1101/gr.277334.122

117.Qian L, Winfree E. A simple DNA gate motif for synthesizing large-scale circuits. J R Soc Interface. 2011. V.8(62). P.1281-1297. doi: 10.1098/rsif.2010.0729

118.Qian L, Winfree E. Scaling up digital circuit computation with DNA strand displacement cascades. Science. 2011a. V.332(6034). P.1196-1201. doi: 10.1126/science.1200520

119.Rakitin A.G. Interpretator DNK-vychislenij na funkcional'nom jazyke programmirovanija. Izvestija Rossijskogo gosudarstvennogo pedagogicheskogo universitete im. A.I. Gercena. 2014. No. 170. S. 34-37. [Interpreter of DNA-computing in a functional programming language] (In Russian)

120.Riera Aroche R, Ortiz Garcia YM, Martinez Arellano MA, Riera Leal A. DNA as a perfect quantum computer based on the quantum physics principles. Sci Rep. 2024. V.14(1). 11636. doi: 10.1038/s41598-024-62539-5

121.Rose J, Komiya K, Yaegashi S, Hagiya M. Displacement whiplash PCR: Optimized architecture and experimental validation. In: Mao C, Yokomori T. (eds). DNA12. LNCS 4287. 2006. P.393-403.

122.Rose J, Deaton RJ, Hagiya M, Suyama A. Equilibrium analysis of the efficiency of an autonomous molecular computer. Physical Rev. E. 2002. V.65.021910.

123.Rothemund PW. Folding DNA to create nanoscale shapes and patterns. Nature. 2006. V.440(7082). P.297-
302. doi: 10.1038/nature04586

124.Rothemund PW, Papadakis N, Winfree E. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2004. V.2(12). e424. doi: 10.1371/journal.pbio.0020424

125.Roweis S, Winfree E, Burgoyne R, Chelyapov NV, Goodman MF, Rothemund PW, Adleman LM. A stickerbased model for DNA computation. J Comput Biol. 1998. V.5(4). P.615-629. doi: 10.1089/cmb.1998.5.615

126.Sakamoto K, Gouzu H, Komiya K, Kiga D, Yokoyama S, Yokomori T, Hagiya M. Molecular computation by DNA hairpin formation. Science. 2000. V.288(5469). P.1223-1226. doi: 10.1126/science.288.5469.1223

127.Sakamoto K, Kiga D, Komiya K, Gouzu H, Yokoyama S, Ikeda S, Sugiyama H, Hagiya M. State transitions by molecules. Biosystems. 1999. V.52(1-3). P.81-91. doi: 10.1016/s0303-2647(99)00035-0

128.Sakhabutdinova A.R., Mikhailenko K.I., Garafutdinov R.R., Kiryanova O.Yu., Sagitova M.A., Sagitov A.M., Chemeris A.V. Non-biological application of DNA molecules. Biomics. 2019. V.11(3). P. 344-377. DOI: 10.31301/2221-6197.bmcs.2019-28 (In Russian)

129.Sakowski S, Krasiński T, Sarnik J, Blasiak J, Waldmajer J, Poplawski T. A detailed experimental study of a DNA computer with two endonucleases. Z Naturforsch C J Biosci. 2017. V.72(7-8). P.303-313. doi: 10.1515/znc-2016-0137

130.Sakowski S, Krasinski T, Waldmajer J, Sarnik J, Blasiak J, Poplawski T. Biomolecular computers with multiple restriction enzymes. Genet Mol Biol. 2017. V.40(4). P.860-870. doi: 10.1590/1678-4685-GMB-2016-0132

131.Schmidt KA, Henkel CV, Rozenberg G, Spaink HP. DNA computing using single-molecule hybridization detection. Nucleic Acids Res. 2004. V.32(17). P.4962-4968. doi: 10.1093/nar/gkh817

132.Seelig G, Soloveichik D, Zhang DY, Winfree E. Enzyme-free nucleic acid logic circuits. Science. 2006. V.314(5805). P.1585-1588. doi: 10.1126/science.1132493

133.Seeman NC. Nucleic acid junctions and lattices. J Theor Biol. 1982. V.99(2). P.237-247. doi: 10.1016/0022-
5193(82)90002-9

134.Sergeenko A.N. Sravnenie trudoemkostej metoda perebora i algoritma, osnovannogo na DNKvychislenijah, na primere reshenija zadachi o kommivojazhere. V sbornike: Nedelja nauki SPbPU. Materialy nauchnoj konferencii s mezhdunarodnym uchastiem. Luchshie doklady. 2018. S. 167-169.[Comparison of the labor intensity of the brute force method and the algorithm based on DNA calculations, using the example of solving the traveling salesman problem] (In Russian)

135.Sergeenko A.N., Granichin O.N. DNK-vychislenija kak sposob reshenija zadachi kommivojazhera. Vosemnadcataja nacional'naja konferencija po iskusstvennomu intellektu s mezhdunarodnym uchastiem KII-2020. S.137-144. [DNA computing as a way to solve the traveling salesman problem] (In Russian)

136.Sergeenko A., Yakunina M., Granichin O. Hamiltonian path problrem solution using DNA computing. Cybernetics and Physics. 2020. V.9. P.69-74.

137.Sharma D, Ramteke M. In Vitro Identification of the Hamiltonian Cycle Using a Circular Structure Assisted DNA Computer. ACS Comb Sci. 2020. V.22(5). P.225-231. doi: 10.1021/acscombsci.9b00150

138.Smith LM, Corn RM, Condon AE, Lagally MG, Frutos AG, Liu Q, Thiel AJ. A surface-based approach to DNA computation. J Comput Biol. 1998. V.5(2). P.255-267. doi: 10.1089/cmb.1998.5.255

139.Song T, Eshra A, Shah S, Bui H, Fu D, Yang M, Mokhtar R, Reif J. Fast and compact DNA logic circuits based on single-stranded gates using strand-displacing polymerase. Nat Nanotechnol. 2019. V.14(11). P.1075-1081. doi: 10.1038/s41565-019-0544-5

140.Song T, Garg S, Mokhtar R, Bui H, Reif J. Analog Computation by DNA Strand Displacement Circuits. ACS Synth Biol. 2016. V.5(8). P.898-912. doi: 10.1021/acssynbio.6b00144

141.Stemmer WP. The evolution of molecular computation. Science. 1995. V.270(5241). P.1510. doi: 10.1126/science.270.5241.1510

142.Stojanovic MN, Mitchell TE, Stefanovic D. Deoxyribozyme-based logic gates. J Am Chem Soc. 2002. V.124(14). P.3555-3561. doi: 10.1021/ja016756v

143.Stojanovic MN, Stefanovic D. A deoxyribozymebased molecular automaton. Nat Biotechnol. 2003. V.21(9). P.1069-1074. doi: 10.1038/nbt862

144.Stojanovic MN, Stefanovic D, Rudchenko S. Exercises in molecular computing. Acc Chem Res. 2014. V.47(6). P.1845-1852. doi: 10.1021/ar5000538

145.Su X, Smith LM. Demonstration of a universal surface DNA computer. Nucleic Acids Res. 2004. V.32(10). P.3115-3123. doi: 10.1093/nar/gkh635

146.Taghipour, H., Taghipour, A., Rezaei M., Esmaili H. Solving the independent set problem by sticker based
DNA computers. American Journal of Molecular Biology. 2012. V.2. P. 153-158. doi: 10.4236/ajmb.2012.22017

147.Taghipour H, Rezaei M, Esmaili HA. Solving the 0/1 knapsack problem by a biomolecular DNA computer. Adv
Bioinformatics. 2013. 341419. doi: 10.1155/2013/341419

148.Tang Z, Yin ZX, Sun X, Cui JZ, Yang J, Wang RS. Dynamically NAND gate system on DNA origami template. Comput Biol Med. 2019. V.109. P.112-120. doi: 10.1016/j.compbiomed.2019.04.026

149.Taniguchi N. On the Basic Concept of Nanotechnology. Proceedings of the International Conference on Production Engineering. Tokyo. 1974. P.18-23.

150.Tian X, Liu X, Zhang H, Sun M, Zhao Y. A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model. PLoS One. 2020. V.15(12). e0242083. doi: 10.1371/journal.pone.0242083

151.Totsingan F, Marchelli R, Corradini R. Molecular computing by PNA:PNA duplex formation. Artif DNA PNA XNA. 2011. V.2(1). P.16-22. doi: 10.4161/adna.2.1.15459

152.Turing AM. Computing Machinery and Intelligence. Mind. 1950. V. 49. P. 433-460.

153.van Noort, D., Landweber, L.F. Towards a Reprogrammable DNA Computer. In: Chen, J., Reif, J. (eds) DNA Computing. DNA 2003. Lecture Notes in Computer Science. 2004. V.2943. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-540-24628-2_18

154.Wang B, Thachuk C, Ellington AD, Winfree E, Soloveichik D. Effective design principles for leakless strand displacement systems. Proc Natl Acad Sci USA. 2018. V.115(52). E12182-E12191. doi: 10.1073/pnas.1806859115

155.Wang B, Wang SS, Chalk C, Ellington AD, Soloveichik D. Parallel molecular computation on digital data stored in DNA. Proc Natl Acad Sci USA. 2023. V.120(37). e2217330120. doi: 10.1073/pnas.2217330120

156.Wang L, Hall JG, Lu M, Liu Q, Smith LM. A DNA computing readout operation based on structure-specific cleavage. Nat Biotechnol. 2001. V.19(11). P.1053-1059. doi: 10.1038/nbt1101-1053

157.Wang L, Liu Q, Frutos AG, Gillmor SD, Thiel AJ, Strother TC, Condon AE, Corn RM, Lagally MG, Smith LM. Surface-based DNA computing operations: DESTROY and READOUT. Biosystems. 1999. V.52(1-3). P.189-191. doi: 10.1016/s0303-2647(99)00046-5

158.Wang X, Bao Z, Hu J, Wang S, Zhan A. Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction. Biosystems. 2008. V.91(1). P.117-125. doi: 10.1016/j.biosystems.2007.08.006

159.Wang Y, Wei Y, Zhang Y, Wang L, Dong Y. Enzyme-free and DNA-based universal platform for the construction of various logic devices based on graphene oxide and G-quadruplex. Comput Biol Chem. 2020. V.89. 107374. doi: 10.1016/j.compbiolchem.2020.107374

160.Wang Z, Huang D, Meng H, Tang C. A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation. Biosystems. 2013. V.114(1). P.1-7. doi: 10.1016/j.biosystems.2013.07.007

161.Wang Z, Ji Z, Wang X, Wu T, Huang W. A new parallel DNA algorithm to solve the task scheduling problem based on inspired computational model. Biosystems. 2017. V.162. P.59-65. doi: 10.1016/j.biosystems.2017.09.001

162.Wang Z, Pu J, Cao L, Tan J. A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing. Int J Mol Sci. 2015. V.16(10). P.25338-25352. doi: 10.3390/ijms161025338

163.Wang Z, Ren X, Ji Z, Huang W, Wu T. A novel bioheuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model. Biosystems. 2019. V.184. 103997. doi: 10.1016/j.biosystems.2019.103997

164.Wang Z, Wu X, Wu T. A Parallel DNA Algorithm for Solving the Quota Traveling Salesman Problem Based on Biocomputing Model. Comput Intell Neurosci. 2022. V.2022. 1450756. doi: 10.1155/2022/1450756

165.Wang ZC, Wu X, Liang K, Wu TH. Exploring the Potential of DNA Computing for Complex Big Data Problems: A Case Study on the Traveling Car Renter Problem. IEEE Trans Nanobioscience. 2024a. PP. doi: 10.1109/TNB.2024.3396142

166.Wang ZC, Liang K, Bao XG, Wu TH. A Novel Algorithm for Solving the Prize Collecting Traveling Salesman Problem Based on DNA Computing. IEEE Trans Nanobioscience. 2024. V.23(2). P.220-232. doi: 10.1109/TNB.2023.3307458

167.Winfree E. Algorithmic self-assembly of DNA. PhD Thesis. 1998. 109 P.

168.Winfree E. Algorithmic Self-Assembly of DNA: Theoretical Motivations and 2D Assembly Experiments. J Biomol Struct Dyn. 2000. V.17(Suppl 1). P.263-270. doi: 10.1080/07391102.2000.10506630

169.Winfree E, Liu F, Wenzler LA, Seeman NC. Design and self-assembly of two-dimensional DNA crystals. Nature. 1998. V.394(6693). P.539-544. doi: 10.1038/28998

170. Woods D, Doty D, Myhrvold C, Hui J, Zhou F, Yin P, Winfree E. Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature. 2019. V.567(7748). P.366-372. doi: 10.1038/s41586-019-1014-9. 171.Wu H. An improved surface-based method for DNA computation. Biosystems. 2001. V.59(1). P.1-5. doi:
10.1016/s0303-2647(00)00133-7

172. Wu X, Wang Z, Wu T, Bao X. Solving the Family Traveling Salesperson Problem in the Adleman-Lipton Model Based on DNA Computing. IEEE Trans Nanobioscience. 2022. V.21(1). P.75-85. doi: 10.1109/TNB.2021.3109067

173. Xiong F, Spetzler D, Frasch WD. Solving the fullyconnected 15-city TSP using probabilistic DNA computing. Integr Biol (Camb). 2009. V.1(3). P.275-280. doi: 10.1039/b821735c

174. Xu J., Dong Y., Wei X. Sticker DNA computer model —Part I: Theory. Chin. Sci. Bull. 2004. V.49. P.772–780.
doi: 10.1007/BF02889745
175. Xu J., Li S. Dong Y. et al. Sticker DNA computer model — Part II: Application. Chin. Sci. Bull. 2004a. V.49. P. 863–871. doi: 10.1007/BF03183999

176.Yasuga H, Kawano R, Takinoue M, Tsuji Y, Osaki T, Kamiya K, Miki N, Takeuchi S. Logic Gate Operation by DNA Translocation through Biological Nanopores. PLoS One. 2016. V.11(2). e0149667. doi: 10.1371/journal.pone.0149667

177.Yang S, Bogels BWA, Wang F, Xu C, Dou H, Mann S, Fan C, de Greef TFA. DNA as a universal chemical substrate for computing and data storage. Nat Rev Chem. 2024. V.8(3). P.179-194. doi: 10.1038/s41570-024-00576-4

178.Yang CN, Yang CB. A DNA solution of SAT problem by a modified sticker model. Biosystems. 2005. V.81(1). P.1-9. doi: 10.1016/j.biosystems.2005.01.001

179.Yin Z., Zhang F., Xu J. A Chinese postman problem based on DNA computing. J. Chem. Inf. Comp. Sci. 2002.
V.42. P.222-224.

180.Yurke B, Turberfield AJ, Mills AP Jr, Simmel FC, Neumann JL. A DNA-fuelled molecular machine made of DNA. Nature. 2000. V.406(6796). P.605-608. doi: 10.1038/35020524

181.Zadegan RM, Jepsen MD, Hildebrandt LL, Birkedal V, Kjems J. Construction of a fuzzy and Boolean logic gates based on DNA. Small. 2015. V.11(15). P.1811-1817. doi: 10.1002/smll.201402755

182.Zhang K, Chen YJ, Wilde D, Doroschak K, Strauss K, Ceze L, Seelig G, Nivala J. A nanopore interface for higher bandwidth DNA computing. Nat Commun. 2022. V.13(1). 4904. doi: 10.1038/s41467-022-32526-3

183.Zhang H, Liu X. A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences. Biosystems. 2011. V.105(1). P.73-82. doi: 10.1016/j.biosystems.2011.03.004

184.Zhang Y, Yin X, Cui C, He K, Wang F, Chao J, Li T, Zuo X, Li A, Wang L, Wang N, Bo X, Fan C. Prime factorization via localized tile assembly in a DNA origami framework. Sci Adv. 2023. V.9(13). eadf8263. doi: 10.1126/sciadv.adf8263

185.Zhou C, Geng H, Guo C. Design of DNA-based innovative computing system of digital comparison. Acta Biomater. 2018. V.80. P.58-65. doi: 10.1016/j.actbio.2018.09.018

186.Zhou C, Geng H, Wang P, Guo C. Programmable DNA Nanoindicator-Based Platform for Large-Scale Square Root Logic Biocomputing. Small. 2019. V.15(49). e1903489. doi: 10.1002/smll.201903489

187.Zhou C, Song Y, Jin X, Li B, Zhou C, Geng H, Wang P, Guo C. Ten-Input Cube Root Logic Computation with Rational Designed DNA Nanoswitches Coupled with DNA Strand Displacement Process. ACS Appl Mater Interfaces. 2020. V.12(2). P.2601-2606. doi: 10.1021/acsami.9b15180

188.Zhou C, Song Y, Jin X, Li B, Pang C. Construction of a scalable DNA computing nano-system for large-scale and complex logical operations. Nanoscale Horiz. 2023. V.8(2). P.176-184. doi: 10.1039/d2nh00525e

189.Zhu J, Kong J, Keyser UF, Wang E. Parallel DNA circuits by autocatalytic strand displacement and nanopore readout. Nanoscale. 2022. V.14(41). P.15507-15515. doi: 10.1039/d2nr04048d

190.Zhu Y, Xiong X, Cao M, Li L, Fan C, Pei H. Accelerating DNA computing via freeze-thaw cycling. Sci Adv. 2023. V.9(34). eaax7983. doi: 10.1126/sciadv.aax7983