В выпуске журнала Science за 14 марта были опубликованы результаты исследований группы американских ученых под руководством Леонарда Эдлмэна, которые можно считать очередным крупным прорывом в области ДНК-компьютинга. Статья называлась "Решение 3-SAT-проблемы с 20 переменными на ДНК-компьютере". Действительно была решена очередная сложная комбинаторная задача. Однако все по порядку.

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

Пионером в этой области стал все тот же Леонард Эдлмэн (Leonard Adleman, Университет Южной Калифорнии), чья статья "Молекулярное вычисление решений для комбинаторных задач" ("Science", 11 ноября 1994 г.) открыла новую страничку в развитии вычислительной техники, которая получила название биокомпьютинга. В прессе открытие Эдлмэна было встречено восторженно и названо не иначе как "первым примером настоящей нанотехнологии".

Леонард Эдлмэн - профессиональный математик и специалист по теории вычислений. В частности, ему в числе некоторых других принадлежит честь создания системы шифрования с открытым ключом (RSA public-key encryption system), которая практически не поддается взлому с помощью обычных компьютеров и даже суперкомпьютеров, поскольку требует огромных затрат времени на вычисления. Но то, что не под силу обычным компьютерам, оказывается доступным системам, использующим принципиально иные вычислительные алгоритмы, как например, квантовые. Открытие Эдлмэна заключалось в том, что то, как молекулы ДНК действуют в природе, является одной из реализаций машины Тьюринга, а значит, может быть использовано для вычислений.

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

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

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

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

Идеи Эдлмэна были подхвачены и развиты по многим направлениям другими учеными. Так, Ричард Липтон (Richard Lipton), специалист по вычислительной технике Принстонского университета, доказал, что компьютер, построенный на основе молекул ДНК, может быть использован для взлома систем шифрования, распространенных как в правительственных учреждениях, так и в частных корпорациях, в частности, так называемую Des (Data Encryption Standard System), имеющую 256 различных способов кодирования информации. Каждый из них предусматривает 16 этапов разупорядочивания исходного сообщения. Для одновременной проверки всех 256 ключей обычным суперкомпьютерам потребуются десятилетия. А вот всего 3 грамма молекул ДНК в растворе, похоже, могут вполне справиться с этой задачей и потребуется им на это около 4 месяцев. На сегодняшний день ДНК-компьютеры позволяют "взломать" код с 72 квадриллионами возможных комбинаций.

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

В 20-х числах ноября 2001 г. информационные агентства распространили информацию об успехе израильских ученых по созданию действующего биокомпьютера, в котором в качестве логических элементов использованы молекулы ДНК (см., например: Nature, 22.11.2001, "КВ", № 48'2001).

Впервые пластиковая модель автономного ДНК-компьютера была представлена профессором факультета компьютерных наук Вейцманновского института науки Егудом Шапиро еще в 1999 году на 5-м Международном съезде по ДНК-компьютерам, который состоялся 14-15 июня в знаменитом MIT (Massachusetts Institute of Technology). С тех пор предпринимались различные попытки реализовать модель на практике, которые увенчались успехом только в прошлом году также под руководством Е. Шапиро.

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

Созданный израильскими учеными ДНК-компьютер мог производить вычисления с точностью до 99.8% и при этом полностью в автономном режиме. От "оператора" требуется только правильно смешать молекулы перед запуском вычислительного процесса.

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

Новую решенную NP-полную задачу один из членов исследовательской группы описал таким примером. В автомагазине, имеющем миллион машин на любой вкус, продавец пытается угодить привередливому покупателю, который выдвигает 24 непростых условия, предъявляемых к покупке. Например, машина может быть Кадиллаком, или с откидным верхом, или красного цвета. Если первое, то она должна иметь 4 сиденья и запирающуюся крышку бензобака. Если второе, то она не должна быть Кадиллаком, но должна иметь 2 сиденья, и т.д.

Ясно, что это довольно сложная комбинаторная задача, и человеку решить ее не по силам. Да и компьютер не сразу найдет решение. Для этого надо перебрать 1048576 возможностей.

Переменные в данной задаче задавались цепочками искусственных ДНК из 15 оснований и, в свою очередь, объединялись тройками. Задача заключалась в том, чтобы найти правильный ответ, удовлетворяющий формуле, задаваемой 20-ю такими цепочками. Для этого нужно было заставить провзаимодействовать ДНК-переменные и ДНК-формулы. Впервые для этого была применена техника высокотемпературного электрофореза, которая заставляла молекулы ДНК двигаться друг относительно друга. Ответу "да" соответствовало сцепление цепочек, ответу "нет" - их полное безразличие друг к другу. Потребовалось всего 24 шага, чтобы найти правильный ответ.

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

И вот в конце февраля появилось сообщение, что фирма Olympus Optical претендует на лидерство в создании коммерческой версии ДНК-компьютера, оптимизированного для генетического анализа. Промышленные поставки компания готова начать со следующего года. Сейчас идут лабораторные испытания. Что же, ждать осталось недолго. Посмотрим.

Ну а кодов ДНК-компьютеры пока не ломают...

Сергей САНЬКО