ДНК-компьютеры выполняют вычисления при помощи химических реакций, в которых участвуют молекулы ДНК. В этих реакциях ферменты разрезают и склеивают молекулы подобно тому, как это происходит в живом организме. Таким образом можно получить множество молекул ДНК с разным строением и отобрать те, что отвечают заданным условиям. Эти действия можно перевести на математический язык и создать в пробирке биохимический компьютер, способный производить вычисления.
«Все ДНК-алгоритмы предлагают рецепты, как закодировать информацию, которая нам нужна, то есть перевести на 'язык' цепочек ДНК, какие операции с ДНК делать - это могут быть только те операции, которые выполнимы в реальности, и потом, как извлечь ответ. Последнее обычно просто. Вот один из таких алгоритмов мы и предложили», - пояснил Игорь Попов из Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики.
Такие задачи, как составление расписания, не имеют рецепта быстрого поиска решения, а требуют перебора возможных комбинаций. С виду такие задачи могут казаться простыми, но для их решения нужно такое количество операций, что они не под силу обычным компьютерам.
«(В задаче составления расписания) есть и учителя, и классы, и уроки - все это надо перебрать и сопоставить. Задача гигантская по объему, и поэтому компьютерные расписания так реально до сих пор и не внедрены», - сказал Попов.
Для решения таких задач математики ищут разные пути. Один из них - создание квантового компьютера, который поможет найти алгоритм, позволяющий ускорить решение задачи и обойтись без перебора вариантов. Напротив, ДНК-компьютер позволяет осуществить перебор решений за относительно короткое время благодаря большому количеству молекул, участвующих в реакциях.
Сейчас ДНК-компьютеры являются лишь теоретической разработкой. Всего алгоритмов для них существует пара десятков, а практически реализованы лишь единицы, при этом ДНК-компьютеры пока что умеют решать только самые примитивные задачи и отнюдь не быстро. Так, например, уже существует алгоритм решения с помощью ДНК математической задачи, в которой нужно проложить путь между несколькими соединенными друг с другом точками, обойдя их все, но только по одному разу.
«(Ученые) решали ее в примитивном варианте - всего 7 вершин. Любой человек, глядя на эту картинку, в течение минуты выдаст ответ, или даже быстрее. У них это заняло с переливанием пробирок, по-моему, 3 рабочих дня» - рассказал Попов.
Сейчас ДНК-компьютеры больше интересны теоретикам, чем практикам, отмечает Попов. Одна из наиболее перспективных областей их возможного применения - шифровка и взлом кодов.
Работа Попова и его коллег Анастасии Воробьевой и Ирины Блиновой опубликована в International Journal of Bioinformatics Research and Applications.