Три десятилетия ДНК-вычислений
21.08.2024
Авторы:
Название:
Три десятилетия ДНК-вычислений
Страницы:
149-187
Три десятилетия назад, в ноябре 1994 г., вышла эпохальная статья Л.Адлемана, посвященная молекулярным вычислениям с помощью синтетических фрагментов ДНК, которой он пробудил дремавший у ряда исследователей интерес к небиологическому применению данного биополимера. Адлеман с использованием набора олигонуклеотидов путем их лигирования Т4 ДНК-лигазой и некоторых других молекулярно-биологических операций «нашел» путь в Гамильтоновом графе из семи вершин, им самим проложенный. И это был модельный эксперимент, показавший принципиальную возможность вести ДНК-вычисления на основе Булевой алгебры с помощью молекул ДНК и решать сверхтяжелые задачи с нечеткой логикой, характеризующиеся сложностью O(N!), в полиномиальное время, что часто невозможно для классических электронных компьютеров. Однако за той его статьей последовала отчасти справедливая мощная критика, сводившаяся к необходимости обращения с огромным количеством ДНК, превышающим для ряда задач, по некоторым подсчетам, вес нашей Планеты. Тем не менее, толчок развитию ДНК-вычислений был дан, и за прошедшее время опубликовано огромное количество работ, в которых описано множество иных подходов. Среди них появились принципиально новые, которые позволяют оперировать молекулами ДНК, присваивая нуклеотидным последовательностям компьютерные «0» и «1» и используя их как логические ДНК-вентили с образованием из них целых каскадов, а также просто кодируя олигонуклеотидами некие условия и формируя сложные наноконструкции, пригодные для молекулярных вычислений. В данном обзоре кратко рассмотрены особенности уникальнейшего природного биополимера, коим является ДНК, дающие возможность использовать его для молекулярных вычислений, основанных на различных принципах. Однако следует признать, что первые весьма оптимистичные ожидания от ДНК-вычислений пока так и не оправдались, хотя заметный прогресс в молекулярно-биологических технологиях в последние годы позволяет надеяться на дальнейшее совершенствование ДНК-вычислений и достижения возможности для них занять свою нишу, в том числе реализоваться в виде работающих ДНК-компьютеров. Уделено также некоторое внимание и их конкурентам в виде основанных на различных физических принципах квантовых компьютеров, которые не исключено, что в будущем смогут использовать для ведения вычислений и молекулы ДНК в виде их неприродных аналогов, несущих нужные модификации для обеспечения квантовой запутанности и квантового превосходства.
- Алферов Ж.И., Асеев А.Л., Гапонов С.В., Копьев П., Панов В.И., Полторацкий Э.А., Сибельдин Н.Н., Сурис Р.А. Наноматериалы и нанотехнологии // Микросистемная техника. 2003. № 8. С. 3-13. 2. Бикбулатова С.М., Мингазетдинова С.Р., Чемерис А.В., Вахитов В.А. Эволюция in vitro – есть ли предел методам «перетасовки» генов? // Успехи современной биологии. 2009. Т. 129. № 4. С. 323-335. 3. Гарафутдинов Р.Р., Баймиев Ан.Х., Малеев Г.В., Алексеев Я.И., Зубов В.В., Чемерис Д.А., Кирьянова О.Ю., Губайдуллин И.М., Матниязов Р.Т., Сахабутдинова А.Р., Никоноров Ю.М., Кулуев Б.Р., Баймиев Ал.Х., Чемерис А.В. Разнообразие праймеров для ПЦР и принципы их подбора // Биомика. 2019. Т.11(1). С. 23 – 70. DOI:10.31301/2221-6197.bmcs.2019-04 4. Геращенков Г.А., Гарафутдинов Р.Р., Баймиев Ан.Х., Кулуев Б.Р., Баймиев Ал.Х., Чемерис А.В. Два величайших открытия двух столетий - нуклеин и двойная спираль ДНК // Биомика. 2019. Т.11(3). С. 259-265. DOI: 10.31301/2221-6197.bmcs.2019-24 5. Караваева О.В., Ростовцев В.С. Аппаратная реализация ДНК-процессора // Перспективы науки. 2010. №6. С.1-4. 6. Кулуев Б.Р., Баймиев Ан.Х., Геращенков Г.А., Юнусбаев У.Б., Гарафутдинов Р.Р., Алексеев Я.И., Баймиев Ал.Х., Чемерис А.В. Сто лет гаплоидным геномам. Сейчас наступает время диплоидных // Биомика. 2020. Т.12(4). С. 411-434. DOI: 10.31301/2221-6197.bmcs.2020-33 7. Малинецкий Г.Г., Митин Н.А., Науменко С.А. Нанобиология и синергетика. Проблемы и идеи // Нанотехника. 2007. №2. С.103-132. 8. Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК. Эксперименты. Модели. Алгоритмы. Инструментальные средства // Информационные технологии и вычислительные системы. 2006. №1. С.5-27. 9. Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК. Эксперименты. Модели. Алгоритмы. Инструментальные средства // Препринты ИПМ им. М.В. Келдыша. 2005. С.1-24. 10. Нейман М.С. Некоторые принципиальные вопросы микроминиатюризации // Радиотехника. 1964. Т.19(1), с. 3-12. 11. Нейман М.С. О связях между надежностью, быстродействием и степенью микроминиатюризации на молекулярно-атомном уровне // Радиотехника. 1965. Т.20(1). С. 1-9. 12. Нейман М.С. О молекулярных системах памяти и о направленных мутациях // Радиотехника. 1965a. Т.20(6). С. 1-8. 13. Ожигов Ю.И. Квантовый компьютер. Москва : МАКС Пресс. 2020. 172 С. 14. Ожигов, Ю.И. Квантовый компьютер: учебное пособие. 2-е изд., доп. и перераб. Москва : Издательство Московского университета. 2023. 326 С. 15. Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений. М., Мир. 2005. 528 С. 16. Поленов А.С. Архитектура ДНК-подсистемы гибридного компьютера на базе расширенной стикерной модели ДНК-вычислений // Наука и бизнес: пути разития. 2015. №8. С.49-51. 17. Поленов А.С. Программный интерфейс для ДНК-подсистемы гибридного компьютера на базе расширенной стикерной модели ДНК-вычислений // Глобальный научный потенциал. 2016. №12. С.133-135. 18. Поленов А.С., Кротов Л.Н. Расширенная стикерная модель для ДНК-вычислений // Естественные и технические науки. 2016. №12. Сю269-272. 19. Ракитин А.Г. Интерпретатор ДНК-вычислений на функциональном языке программирования // Известия Российского государственного педагогического университете им. А.И. Герцена. 2014. № 170. С. 34-37. 20. Сахабутдинова А.Р., Михайленко К.И., Гарафутдинов Р.Р., Кирьянова О.Ю., Сагитова М.А., Сагитов А.М., Чемерис А.В. Небиологическое применение молекул ДНК // Биомика. 2019. Т.11(3). С. 344-377. DOI: 10.31301/2221-6197.bmcs.2019-28 21. Сергеенко А.Н. Сравнение трудоемкостей метода перебора и алгоритма, основанного на ДНК-вычислениях, на примере решения задачи о коммивояжере // В сборнике: Неделя науки СПбПУ. Материалы научной конференции с международным участием. Лучшие доклады. 2018. С. 167-169. 22. Сергеенко А.Н., Граничин О.Н. ДНК-вычисления как способ решения задачи коммивояжера // Восемнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2020. С.137-144. 23. Чемерис Д.А., Кирьянова О.Ю., Губайдуллин И.М., Чемерис А.В. Дизайн праймеров для полимеразной цепной реакции (краткий обзор компьютерных программ и баз данных) // Биомика. 2016. Т. 8. № 3. С. 215-238. 24. Чемерис Д.А., Никоноров Ю.М., Вахитов В.А. Гибридизационная цепная реакция в режиме реального времени // Доклады Академии наук. 2008. Т. 419(1). С. 123-125. 25. 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 26. Adleman LM. Molecular computation of solutions to combinatorial problems // Science. 1994. V.266(5187). P.1021-1024. DOI:10.1126/science.7973651 27. Adleman LM. Response // Science. 1995. V.268(5210). P.483-484. DOI:10.1126/science.268.5210.483 28. Adleman L. Computing with DNA // Scientific American. 1998. V.279. P.34-41. doi:10.1038/scientificamerican0898-54 29. 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 30. 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 31. 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 32. 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 33. Beaver D. Computing with DNA // J Comput Biol. 1995. V.2(1). P.1-7. doi:10.1089/cmb.1995.2.1 34. 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 35. 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 36. 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 37. 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. 38. 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 39. 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. 40. 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 41. Bunow B. On the potential of molecular computing // Science. 1995. V.268(5210). P.482-483. doi:10.1126/science.7725087 42. Byrne J., Dahm R. Friedrich Miescher and the 150th anniversary of the discovery of DNA // Biomics. 2019. V.11(3). P. 249-258. DOI:10.31301/2221-6197.bmcs.2019-23 43. Cardelli L. Strand algebras for DNA computing // Nat. Comp. 2011. V.10. P.407-428. 44. Chang WL, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model // Biosystems. 2003. V.72(3). P.263-275. doi:10.1016/s0303-2647(03)00149-7 45. 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 46. Chang WL, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model // Biosystems. 2003. V.72(3). P.263-275. doi:10.1016/s0303-2647(03)00149-7 47. 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 48. 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 49. 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 50. 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 51. 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 52. 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 53. Clelland C.T., Risca V., Bancroft C. Hiding messages in DNA microdots // Nature. 1999. V.399(6736). P.533-534. DOI:10.1038/21092 54. Conrad M. Molecular computing // Advances in Computers. 1990. V.31. P.235-324. doi:10.1016/S0065-2458(08)60155-2 55. Davis J. Microvenus // Art Journal. 1996. V. 55(1). P. 70-74. DOI:10.2307/777811 56. 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. DOI10.1088/1555-6611/aa51a7 57. 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 58. 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 59. Feng G, Hou S-Y, Zou H. et al. SpinQ Triangulum: a commercial three-qubit desktop quantum computer // arXiv. 2022. 2202.02983v1. 60. 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. 61. Franco G, Manca V. Algorithmic applications of XPCR // Natural Computing. 2011. V.10(2). P. 805 – 819. doi:10.1007/s11047-010-9199-8 62. 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 63. 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 64. 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. 65. 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 66. 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 67. 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 68. 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 69. 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 70. 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 71. 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 72. 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 73. Gifford DK. On the path to computation with DNA // Science. 1994. V.266(5187). P.993-994. doi:10.1126/science.7973681 74. 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 75. Guo Y., Wei B., Sun X., Yao D., Zhou X., Xiao S., Liang H. DNA and DNA computation based on toehold-mediated strand displacement reactions // International Journal of Modern Physics B. Vol. 32, No. 18, 1840014 (2018) doi:10.1142/S0217979218400143 76. 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 77. Hartmanis J. On the weight of computation // EATCS Bulletin. 1995. No 55. P.136-138. 78. 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 79. Hou S-Y, Feng G, Wu Z. et al. SpinQ Gemini: a desktop quantum computer for education and research // arXiv. 2021. 2101.10017v2. 80. 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 81. 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 82. 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 83. 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 84. Ibrahim Z, Tsuboi Y, Ono O. Hybridization-ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for direct-proportional length-based DNA computing // IEEE Trans Nanobioscience. 2006. V.5(2). P.103-109. doi:10.1109/tnb.2006.875043 85. Interview. Machines smarter than men? // U.S. News & World Report. 1964. Feb., 24. P.84-86. 86. 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 87. 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 88. Kiryanova OY, Garafutdinov RR, Gubaydullin IM, Chemeris AV. A novel approach to encode melodies in DNA // Biosystems. 2024. V.237. 105136. doi:10.1016/j.biosystems.2024.105136 89. 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 90. 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 91. Lee CM, Kim SW, Kim SM, Sohn U. DNA computing the Hamiltonian path problem // Mol Cells. 1999. V.9(5). P.464-469. 92. 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 93. Li D, Li X, Huang H, Li X. Scalability of the surface-based DNA algorithm for 3-SAT // Biosystems. 2006. V.85(2). P.95-98. doi:10.1016/j.biosystems.2005.12.002 94. 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 95. 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 96. 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 97. Linial M, Linial N. On the potential of molecular computing // Science. 1995. V.268(5210). P.481. DOI:10.1126/science.7725085 98. Lipton RJ. DNA solution of hard computational problems // Science. 1995. V.268(5210). P.542-545. DOI:10.1126/science.7725098 99. 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 100. 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 101. 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 102. 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 103. 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 104. 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 105. 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 106. 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 107. 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 108. Montagud-Martínez R, Heras-Hernández M, Goiriz L, Daròs 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 109. 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 110. 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 111. 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 112. Okamoto A, Tanaka K, Saito I. DNA logic gates // J Am Chem Soc. 2004. V.126(30). P.9458-9463. doi:10.1021/ja047628k 113. 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 114. 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 115. Pei Y, Bian T, Liu Y, Liu Y, Xie Y, Song J. Single-Molecule Resettable DNA Computing via Magnetic Tweezers // Nano Lett. 2022. V.22(7). P.3003-3010. doi:10.1021/acs.nanolett.2c00183 116. 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 117. Penchovsky R, Ackermann J. DNA library design for molecular computation // J Comput Biol. 2003. V.10(2). P.215-229. doi:10.1089/106652703321825973 118. 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 119. Pool R. A boom in plans for DNA computing // Science. 1995. V.268(5210). P.498-499. doi:10.1126/science.7725093 120. Porubsky D, Vollger MR, Harvey WT. et al.; Human Pangenome Reference Consortium. 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 121. 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 122. 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 123. Riera Aroche R, Ortiz García YM, Martínez 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 124. 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. 125. 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. 126. Rothemund PW. Folding DNA to create nanoscale shapes and patterns // Nature. 2006. V.440(7082). P.297-302. doi:10.1038/nature04586 127. 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 128. Roweis S, Winfree E, Burgoyne R, Chelyapov NV, Goodman MF, Rothemund PW, Adleman LM. A sticker-based model for DNA computation // J Comput Biol. 1998. V.5(4). P.615-629. doi:10.1089/cmb.1998.5.615 129. 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 130. 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 131. 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 132. 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 133. 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 134. 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 135. 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 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 deoxyribozyme-based 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 Re-programmable 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 bio-heuristic 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 fully-connected 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, Bögels 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