eISSN: 2221-6197 DOI: 10.31301/2221-6197

Biomics

Архив номеров

Индексирование
  1. Главная
  2. →
  3. 2024
  4. →
  5. Том 16, № 2
  6. →
  7. Статьи
  8. →
  9. ТРИ ДЕСЯТИЛЕТИЯ ДНК-ВЫЧИСЛЕНИЙ

ТРИ ДЕСЯТИЛЕТИЯ ДНК-ВЫЧИСЛЕНИЙ

Год: 2024

Страницы: 149-187

Номер: Том 16, № 2

Тип: научная статья

DOI: https://doi.org/10.31301/2221-6197.bmcs.2024-9

Рубрика: Статьи

Авторы: Михайленко Константин Иванович, Гарафутдинов Равиль Ринатович, Привалов Л.Ю., Матниязов Рустам Тахирович, Чемерис Дмитрий Алексеевич, Сахабутдинова Ассоль Рафиковна, Гиниятов Айрат Ришатович, Чемерис Алексей Викторович

Скачать pdf

Аннотация:

Три десятилетия назад, в ноябре 1994 г., вышла эпохальная статья Л.Адлемана, посвященная молекулярным вычислениям с помощью синтетических фрагментов ДНК, которой он пробудил дремавший у ряда исследователей интерес к небиологическому применению данного биополимера. Адлеман с использованием набора олигонуклеотидов путем их лигирования Т4 ДНК-лигазой и некоторых других молекулярно-биологических операций «нашел» путь в Гамильтоновом графе из семи вершин, им самим проложенный. И это был модельный эксперимент, показавший принципиальную возможность вести ДНК-вычисления на основе Булевой алгебры с помощью молекул ДНК и решать сверхтяжелые задачи с нечеткой логикой, характеризующиеся сложностью O(N!), в полиномиальное время, что часто невозможно для классических электронных компьютеров. Однако за той его статьей последовала отчасти справедливая мощная критика, сводившаяся к необходимости обращения с огромным количеством ДНК, превышающим для ряда задач, по некоторым подсчетам, вес нашей Планеты. Тем не менее, толчок развитию ДНК-вычислений был дан, и за прошедшее время опубликовано огромное количество работ, в которых описано множество иных подходов. Среди них появились принципиально новые, которые позволяют оперировать молекулами ДНК, присваивая нуклеотидным последовательностям компьютерные «0» и «1» и используя их как логические ДНК-вентили с образованием из них целых каскадов, а также просто кодируя олигонуклеотидами некие условия и формируя сложные наноконструкции, пригодные для молекулярных вычислений. В данном обзоре кратко рассмотрены особенности уникальнейшего природного биополимера, коим является ДНК, дающие возможность использовать его для молекулярных вычислений, основанных на различных принципах. Однако следует признать, что первые весьма оптимистичные ожидания от ДНК-вычислений пока так и не оправдались, хотя заметный прогресс в молекулярно-биологических технологиях в последние годы позволяет надеяться на дальнейшее совершенствование ДНК-вычислений и достижения возможности для них занять свою нишу, в том числе реализоваться в виде работающих ДНК-компьютеров. Уделено также некоторое внимание и их конкурентам в виде основанных на различных физических принципах квантовых компьютеров, которые не исключено, что в будущем смогут использовать для ведения вычислений и молекулы ДНК в виде их неприродных аналогов, несущих нужные модификации для обеспечения квантовой запутанности и квантового превосходства.

Ключевые слова:

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

Библиографический список:

  1. Алферов Ж.И., Асеев А.Л., Гапонов С.В., Копьев П., Панов В.И., Полторацкий Э.А., Сибельдин Н.Н., Сурис Р.А. Наноматериалы и нанотехнологии // Микросистемная техника. 2003. № 8. С. 3-13.
  2. Бикбулатова С.М., Мингазетдинова С.Р., Чемерис А.В., Вахитов В.А. Эволюция in vitro – есть ли предел методам «перетасовки» генов? // Успехи современной биологии. 2009. Т. 129. № 4. С. 323-335.
  3. Гарафутдинов Р.Р., Баймиев Ан.Х., Малеев Г.В., Алексеев Я.И., Зубов В.В., Чемерис Д.А., Кирьянова О.Ю., Губайдуллин И.М., Матниязов Р.Т., Сахабутдинова А.Р., Никоноров Ю.М., Кулуев Б.Р., Баймиев Ал.Х., Чемерис А.В. Разнообразие праймеров для ПЦР и принципы их подбора // Биомика. 2019. Т.11(1). С. 23 – 70. DOI: https://doi.org/10.31301/2221-6197.bmcs.2019-04  
  4. Геращенков Г.А., Гарафутдинов Р.Р., Баймиев Ан.Х., Кулуев Б.Р., Баймиев Ал.Х., Чемерис А.В. Два величайших открытия двух столетий - нуклеин и двойная спираль ДНК // Биомика. 2019. Т.11(3). С. 259-265. DOI: https://doi.org/10.31301/2221-6197.bmcs.2019-24 
  5. Караваева О.В., Ростовцев В.С. Аппаратная реализация ДНК-процессора // Перспективы науки. 2010. №6. С.1-4.
  6. Кулуев Б.Р., Баймиев Ан.Х., Геращенков Г.А., Юнусбаев У.Б., Гарафутдинов Р.Р., Алексеев Я.И., Баймиев Ал.Х., Чемерис А.В. Сто лет гаплоидным геномам. Сейчас наступает время диплоидных // Биомика. 2020. Т.12(4). С. 411-434. DOI: https://doi.org/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: https://doi.org/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: https://doi.org/10.1073/pnas.0400731101
  26. Adleman LM. Molecular computation of solutions to combinatorial problems // Science. 1994. V.266(5187). P.1021-1024. DOI: https://doi.org/10.1126/science.7973651 
  27. Adleman LM. Response // Science. 1995. V.268 (5210). P.483-484. DOI: https://doi.org/10.1126/science.268.5210.483 
  28. Adleman L. Computing with DNA // Scientific American. 1998. V.279. P.34-41. doi: https://doi.org/10.1038/scientificamerican0898-54 
  29. Adleman LM, Rothemund PW, Roweis S, Winfree E. On applying molecular computation to the data
  30. encryption standard // J Comput Biol. 1999. V.6(1). P.53-63. doi: https://doi/or/10.1089/cmb.1999.6.53 
  31.  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: https://doi.org/10.1166/jnn.2011.38844717 
  32. 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: https://doi.org/10.1016/s0303-2647(99)00045-3 
  33. 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: https://doi.org/10.1126/science.293.5536.1763c 
  34. Beaver D. Computing with DNA // J Comput Biol. 1995. V.2(1). P.1-7. doi: https://doi.org/10.1089/cmb.1995.2.1 
  35. 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: https://doi.org/10.1073/pnas.0535624100 
  36. 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: https://doi/org/10.1038/nature02551 
  37. 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: https://doi.org/10.1038/35106533 
  38. 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.
  39. 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 doi: https://doi.org/10.1126/science.1069528 
  40. 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.
  41. 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: https://doi.org/10.1021/acsnano.7b06699 
  42. Bunow B. On the potential of molecular computing // Science. 1995. V.268(5210). P.482-483. doi: https://doi.org/10.1126/science.7725087 
  43. Byrne J., Dahm R. Friedrich Miescher and the 150th anniversary of the discovery of DNA // Biomics. 2019. V.11(3). P. 249-258. DOI: https://doi.org/10.31301/2221-6197.bmcs.2019-23 
  44. Cardelli L. Strand algebras for DNA computing // Nat. Comp. 2011. V.10. P.407-428.
  45. 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: https://doi.org/10.1016/s0303-2647(03)00149-7  
  46. 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: https://doi.org/10.1016/j.biosystems.2003.11.001 
  47. 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: https://doi.org/10.1016/s0303-2647(03)00149-7 
  48. 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: https://doi.org/10.1038/nnano.2017.127 
  49. 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: https://doi.org/10.31301/2221-6197.bmcs.2023-26 
  50. Chen RC, Yang SJ. Applying DNA computation to intractable problems in social network analysis // Biosystems. 2010. V.101(3). P.222-232. doi: https://doi.org/10.1016/j.biosystems.2010.05.006 
  51. 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
  52. 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
  53. 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
  54. Clelland C.T., Risca V., Bancroft C. Hiding messages in DNA microdots // Nature. 1999. V.399(6736). P.533-534. DOI: 10.1038/21092
  55. Conrad M. Molecular computing // Advances in Computers. 1990. V.31. P.235-324. doi: 10.1016/S0065- 2458(08)60155-2
  56. Davis J. Microvenus // Art Journal. 1996. V. 55(1). P. 70-74. DOI: 10.2307/777811
  57. 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
  58. 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
  59. 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
  60. Feng G, Hou S-Y, Zou H. et al. SpinQ Triangulum: a commercial three-qubit desktop quantum computer // arXiv. 2022. 2202.02983v1.
  61. 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.
  62. Franco G, Manca V. Algorithmic applications of XPCR // Natural Computing. 2011. V.10(2). P. 805 – 819. doi: 10.1007/s11047-010-9199-8
  63. 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
  64. 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
  65. 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.
  66. 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
  67. 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
  68. 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
  69. 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
  70. 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
  71. 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
  72. 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
  73. 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
  74. Gifford DK. On the path to computation with DNA // Science.1994. V.266(5187). P.993-994.   doi:10.1126/science.7973681
  75. 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
  76. 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
  77. 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
  78. Hartmanis J. On the weight of computation // EATCS Bulletin. 1995. No 55. P.136-138.
  79. 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
  80. Hou S-Y, Feng G, Wu Z. et al. SpinQ Gemini: a desktop quantum computer for education and research // arXiv. 2021. 2101.10017v2.
  81. 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
  82. 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
  83. 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
  84. 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
  85. 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
  86. Interview. Machines smarter than men? // U.S. News & World Report. 1964. Feb., 24. P.84-86.
  87. 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
  88. 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
  89. 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
  90. 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
  91. 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
  92. Lee CM, Kim SW, Kim SM, Sohn U. DNA computing the Hamiltonian path problem // Mol Cells. 1999. V.9(5). P.464469.
  93. 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
  94. Li D, Li X, Huang H, Li X. Scalability of the surface- based DNA algorithm for 3-SAT // Biosystems. 2006. V.85(2). P.9598. doi: 10.1016/j.biosystems.2005.12.002
  95. 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
  96. 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
  97. 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
  98. Linial M, Linial N. On the potential of molecular computing // Science. 1995. V.268(5210). P.481. DOI: 10.1126/science.7725085
  99. Lipton RJ. DNA solution of hard computational problems // Science. 1995. V.268(5210). P.542-545. DOI: 10.1126/science.7725098
  100. 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
  101. 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
  102. 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
  103. 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
  104. 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
  105. 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
  106. 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
  107. 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
  108. 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
  109. 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
  110. 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
  111. 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
  112. 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
  113. Okamoto A, Tanaka K, Saito I. DNA logic gates // J Am Chem Soc. 2004. V.126(30). P.9458-9463. doi: 10.1021/ja047628k
  114. 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
  115. 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
  116. 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
  117. 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 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
  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
  151. Turing AM. Computing Machinery and Intelligence // Mind. 1950. V. 49. P. 433-460.
  152. 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
  153. 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
  154. 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
  155. 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
  156. 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
  157. 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
  158. 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
  159. 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
  160. 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
  161. 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
  162. 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
  163. 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
  164. 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
  165. 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
  166. Winfree E. Algorithmic self-assembly of DNA. PhD Thesis. 1998. 109 P.
  167. 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
  168. 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
  169. 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.
  170. 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
  171. 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
  172. 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
  173. 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
  174. 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
  175. 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
  176. 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
  177. 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.
  178. 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
  179. 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
  180. 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
  181. 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
  182. 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
  183. 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
  184. 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
  185. 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
  186. 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
  187. 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
  188. 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
Скачать pdf
наверх
eISSN: 2221-6197 DOI: 10.31301/2221-6197