Ученые создали алгоритм составления расписаний с помощью молекул ДНК

ДНК-компьютер позволяет осуществить перебор решений за относительно короткое время благодаря большому количеству молекул, участвующих в реакциях.

ДНК-компьютеры выполняют вычисления при помощи химических реакций, в которых участвуют молекулы ДНК. В этих реакциях ферменты разрезают и склеивают молекулы подобно тому, как это происходит в живом организме. Таким образом, можно получить множество молекул ДНК с разным строением и отобрать те, что отвечают заданным условиям. Эти действия можно перевести на математический язык и создать в пробирке биохимический компьютер, способный производить вычисления.

Такие задачи, как составление расписания, не имеют рецепта быстрого поиска решения, а требуют перебора возможных комбинаций. С виду такие задачи могут казаться простыми, но для их решения нужно такое количество операций, что они не под силу обычным компьютерам

Для решения таких задач математики ищут разные пути. Один из них — создание квантового компьютера, который поможет найти алгоритм, позволяющий ускорить решение задачи и обойтись без перебора вариантов. Напротив, ДНК-компьютер позволяет осуществить перебор решений за относительно короткое время благодаря большому количеству молекул, участвующих в реакциях.

Сейчас ДНК-компьютеры являются лишь теоретической разработкой. Всего алгоритмов для них существует пара десятков, а практически реализованы лишь единицы, при этом ДНК-компьютеры пока что умеют решать только самые примитивные задачи и отнюдь не быстро. Так, например, уже существует алгоритм решения с помощью ДНК математической задачи, в которой нужно проложить путь между несколькими соединенными друг с другом точками, обойдя их все, но только по одному разу.

Работа опубликована в International Journal of Bioinformatics Research and Applications.