Кислотные вычисления Почему не получились ДНК-компьютеры

Скорый кризис транзисторных процессоров в начале 1990-х казался неизбежным. И пока в одних лабораториях альтернативу искали, проектируя квантовые алгоритмы и экспериментируя с кубитами, в других — двигали компьютеры на биомолекулах. В 1994 году практически одновременно ученые собрали первый квантовый вентиль и решили первую задачу с помощью ДНК. Но к тому, чтобы двигаться дальше, одни «альтернативные айтишники» были готовы лучше, чем другие. Проектировать квантовые компьютеры начали задолго до появления кубита. Еще в 60-х теоретики занялись квантовой информатикой, а к 80-м уже думали о квантовых алгоритмах, возможном устройстве логических вентилей на кубитах, а экспериментаторы собирали разнообразные прототипы кубитов. А над теорией ДНК-вычислений никто специально не работал. Там сразу начали решать конкретные вычислительные задачи.

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

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

Первым, кто понял, что имеющихся у биологов инструментов уже хватает для вычислений, стал математик Леонард Адлеман, один из создателей системы шифрования RSA (Rivest — Shamir — Adleman). Познакомившись в начале 1990-х с миром ДНК, ученый, по его собственным словам, «отчетливо увидел» аналогию между нуклеиновой логикой и транзисторной логикой компьютерных процессоров — и уже в 1994 году опубликовал статью об эксперименте, в котором нуклеиновые кислоты решили задачу о гамильтоновом цикле на графе.

Это частный случай NP-полной задачи коммивояжера (о полиномиальных и неполиномиальных задачах мы говорили в материале «Удаленное доказательство»). В задаче коммивояжера определенное количество точек на карте надо соединить самой короткой траекторией, ни одну из них при этом не пропустив. В задаче поиска гамильтонова пути надо просто доказать, что траектория, которая соединяет все точки и проходит через каждую ровно один раз, существует. Вычислитель Адлемана искал решение для графа с семью узлами.

В этом ДНК-вычислителе каждому из узлов графа соответствовала случайная молекула из 20 нуклеотидов. Соответственно, ребра графа, то есть соединения узлов, складывались из двух половинок: первые десять звеньев — 3′-хвост молекулы одного узла, а вторые десять — 5′-хвост второй. Ребра таким образом становились векторами: i→j-последовательность нуклеотидов отличалась от j→i-последовательности. Это и нужно для того, чтобы синтезировать непрерывные траектории, последовательно идущие через узлы графа.

Биопроцессор Адлемана использовал ДНК в качестве носителя информации, а для операций над ней — полимеразу и лигазу, которые, соответственно, синтезировали новые цепочки нуклеиновых кислот и сшивали их друг за другом.

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

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

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

Продолжение в источнике: NPlus1

Источник фото:naturalblaze