Вычисления в двойной спирали

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

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

Основополагающим для развития нового направления стал эксперимент, проведенный в конце 1994 года крупным специалистом по криптографии, профессором университета Южной Калифорнии Леонардом Адлеманом (Leonard Adleman). Возможность использования ДНК для вычислений Адлеман продемонстрировал на примере решения проблемы, которая формально обозначается как поиск Гамильтонова пути графа, но более известна под названием «задача коммивояжера». Допустим, коммивояжеру нужно выбрать оптимальный маршрут, ведущий из одной точки в другую и проходящий через определенное количество городов, причем через каждый из них - только один раз. При увеличении числа городов-узлов графа до некоторого предела задача становится нерешаемой даже при использовании самых мощных вычислительных ресурсов. Адлеман, впрочем, взял несложный вариант, задав семь узлов. Каждому из них был присвоен уникальный код, представляющий собой определенную последовательность четырех нуклеотидных оснований - аденина (A), гуанина (G), цитозина (C) и тимина (T). Ребра графа (путь от одного города к другому) были закодированы в виде цепочек, их началом служил код второй половины узла-точки отправления, а концом - код первой половины узла-точки прибытия. Следующий шаг - замена оснований в цепочках-узлах на парные им (аденин на тимин, цитозин на гуанин), иначе говоря, создание комплементарных нитей, которые, дополняя оригинальные фрагменты, образуют двойную спираль. Эти одинарные комплементарные нити Адлеман слил в одну пробирку с цепочками, кодирующими ребра графа. Следуя тому же принципу комплементарности, в смеси начали формироваться молекулы ДНК, в закодированном виде представляющие все возможные варианты маршрута. Спирали образовались за одну секунду, зато следующий этап работы - выделение нужной молекулы - отнял целую неделю. Адлеман нашел правильное решение, последовательно удалив цепочки, которые не начинались с узла-начальной точки или не заканчивались узлом-конечной точкой и состояли более чем из семи узлов или не содержали хотя бы один из узлов. Нетрудно представить, что любая из оставшихся после такого отбора нитей будет представлять собой ответ. Расшифровав последовательность оснований, можно определить порядок кодов, который есть не что иное, как порядок следования по ребрам графа.

Работа Адлемана, вызвав интерес как генетиков, так и микроэлектронщиков, стала поводом подумать о сотрудничестве различных, ранее обособленных групп ученых. Через несколько месяцев после публикации в журнале «Science» в Принстоне состоялась первая конференция по ДНК-компьютерам. Она собрала три сотни участников и, по сути, впервые заявила о новом направлении исследований. В работу включились специалисты ряда научных лабораторий. Они продолжили упражняться с логическими задачами, расширив их масштаб и спектр. Ученые из университета Висконсина экспериментировали с другим носителем генетической информации - одинарной спиралью РНК. С ее помощью они нашли решение шахматной головоломки, суть которой - разместить многочисленные фигуры коней на доске таким образом, чтобы ни один конь не угрожал другому. Проводились опыты с использованием молекул, закрепленных на поверхности золотой пластины, были предложены ДНК-алгоритмы для шифрования данных и, наоборот, вскрытия кодов. Ричард Липтон (Richard J. Lipton) из Принстона первым показал возможность ДНК-кодирования двоичных чисел и решения бинарных задач. Кроме того, изучается идея применения ДНК для «выращивания» отдельных компонентов процессоров. Ученые разрабатывают технологию создания необычных унифицированных молекулярных структур, которые могут стать основой полупроводниковых наносхем. Эта же технология рассматривается как первый шаг к программированию молекулярных реакций.

Последняя из привлекших внимание новостей появилась пару месяцев назад (см. «КТ» #423, с.6): израильские ученые опубликовали результаты экспериментов с автономным молекулярным компьютером, система ввода-вывода и «программное обеспечение» которого состоит из ДНК, а роль аппаратной части выполняют два фермента, разрезающих и соединяющих определенные фрагменты цепочки. Эта вычислительная схема способна работать с 765 простыми программами, решая задачи вроде нахождения кодов, содержащих четное число нулей или единиц. Триллион таких компьютеров в капле раствора обрабатывает данные с точностью 99,8 %, выполняя миллиард операций в секунду. В проведенных экспериментах в каждом отдельном цикле весь этот триллион параллельно решал одну задачу, работая с одинаковыми входящими молекулами. Однако в принципе, при усложнении процесса, можно одновременно задавать различные программы, что и станет действительно ценной реализацией идеи параллельных вычислений.

Еще шесть-семь лет назад, сразу после экспериментов Адлемана со многими основаниями, высказывалось мнение, что вычислительные системы на основе ДНК - это сомнительное решение неочевидной проблемы. Кажется, сейчас это решение, судя по растущему интересу к исследованиям в области молекулярных компьютеров, начинает внимательно прорабатываться, и поле деятельности для него находится. По мнению оптимистически настроенных ученых, новое направление развития вычислительной техники перестанет казаться экзотикой в ближайшие десять лет, хотя скептики справедливо указывают на сложности, связанные с управлением живыми молекулами и контролем их активности, необходимым для того, чтобы исключить ошибки в вычислениях. Принципиальное затруднение, непреодолимое с помощью существующих молекулярных методов, касается увеличения масштаба проблем, с которыми могут справиться ДНК-компьютеры. Выразительную оценку еще в 1995 году дал профессор Юрис Хартманис (Juris Hartmanis) в статье «О весе вычислений» («On the Weight of Computations»). Он подсчитал, что если многократно расширить задачу коммивояжера, включив в нее две сотни городов вместо семи, то вес цепочек ДНК, представляющих все возможные варианты решения, превысит вес Земли (стоит, впрочем, заметить, что задачу с двумя сотнями узлов современные суперкомпьютеры будут решать тысячи лет). В целом же не только способность живых «счетных машин» выполнять огромное число операций параллельно пока не находит применения, но и сам принцип использования ДНК для вычислений, как признают ученые, его разрабатывающие, еще предстоит как следует проверить.