|
ДНК-компьютеры будущего
|
|
|
|
Согласно прогнозу агентства IDC, к 2020 году объем данных, созданных и сохраненных человечеством, достигнет 40000 эксабайт. Это 40 трлн гигабайт, или 5200 гигабайт на душу населения. Для хранения всей этой информации было бы достаточно менее 100 г ДНК. Сей факт заставляет искренне верить в перспективу развития ДНК-компьютеров. Упаковка равных по массе контейнеров, поиск кратчайшего маршрута между несколькими пунктами назначения, расшифровка закодированных данных — что может быть общего у этих задач? Ответ прост — они слишком сложны для современных компьютеров.
|
|
|
|
Классическим примером может служить старинная задача о Кенигсбергских мостах, в которой спрашивалось, как пройти по всем семи мостам города, не пройдя ни по одному из них дважды. Впервые задача была решена в 1736 году великим Леонардом Эйлером, который родился в Швейцарии, но практически полжизни жил и работал в России, в Петербургской академии наук. Эйлер хорошо знал русский язык и многие свои труды публиковал на русском.
|
|
|
Работы Эйлера заложили основы теории графов, позволяющей формализовать подобные задачи. Точки маршрута (берега) в ней называются вершинами графа, переходы между вершинами (мосты) — ребрами. Каждое ребро имеет вес, характеризующий сложность данного перехода (расстояние, которое необходимо пройти). Эйлер выяснил, что пройти по каждому мосту Кенигсберга лишь по одному разу невозможно. Но это не отменяет другой, более важной задачи: как обойти все мосты города кратчайшим путем (задача коммивояжера)? Сложность этой и подобных задач заключается в том, что на сегодняшний день не существует ни одного известного алгоритма их решения, кроме полного перебора вариантов. В каждой последующей вершине графа задача распадается на множество аналогичных задач, и количество возможных решений возрастает экспоненциально.
|
|
|
|
В современных лабораториях процесс создания коротких фрагментов ДНК с заданным кодом полностью автоматизирован. Небольшие науч-ные группы, которые не могут позволить себе собственный синтезатор, заказывают олигонуклеотиды у коммерческих фирм.
|
|
|
|
В основе кремниевых компьютеров лежит последовательный принцип решения задач. Один за другим компьютер складывает возможные маршруты, проверяет их соответствие условиям задачи, вычисляет их длину, сравнивает результаты и выявляет кратчайший путь. Для решения задачи с 30 мостами наиболее прямолинейным способом, именуемым методом лексического перебора, понадобилось бы время большее, чем возраст Вселенной.
|
|
|
|
К счастью, существуют алгоритмы, позволяющие кремниевым компьютерам решать относительно сложные комбинаторные задачи за приемлемое время. Но есть и другой путь — вычисления с высокой параллельностью, позволяющие анализировать все возможные решения задачи одновременно. Именно этим и займутся будущие ДНК-компьютеры.
|
|
|
|
Биоавтомат
|
|
|
|
Интересно, что создатель первого ДНК-компьютера Леонард Адлеман известен прежде всего как выдающийся криптограф. В названии алгоритма шифрования RSA, без которого немыслимы мировые финансы, третья буква обозначает именно его фамилию (Rivest — Shamir — Adleman).
|
|
|
|
В 1994 году Адлеман повторил опыт Эйлера, предложив собственное решение задачи коммивояжера для графа с семью вершинами. В этом ему помог не привычный кусок кремния, а несколько пробирок, каждая из которых содержала миллиарды миллиардов молекул ДНК — биологических нанокомпьютеров. Еще в далеком 1953 году нобелевские лауреаты Фрэнсис Крик, Джеймс Уотсон и Морис Уилкинс, расшифровавшие структуру ДНК, сравнивали эту молекулу с машиной Тьюринга, гипотетическим предвестником современных процессоров.
|
|
|
|
Двойная спираль ДНК — это не что иное, как программный код, общий для всех живых организмов на Земле. По простоте и универсальности он стоит на одной ступени с машинным двоичным кодом.
|
|
|
|
Напомним, что ДНК представляет собой две спирали, соединенные между собой парами азотистых оснований. Спирали — это гигантские макромолекулы, состоящие из дезоксирибозы и фосфатных групп. Если провести аналогию с машиной Тьюринга, спираль — это перфолента, на которой записан программный код.
|
|
|
|
Код состоит из четырех букв, обозначающих азотистые основания: А — аденин, Т — тимин, С — цитозин и G — гуанин. Азотистые основания двух соседних спиралей притягиваются друг к другу, причем аденин соединяется только с тимином, а цитозин — с гуанином. Благодаря азотистым основаниям две спирали, являющиеся зеркальным отображением друг друга, соединяются в одну молекулу ДНК.
|
|
|
|
ДНК в живом организме постоянно тиражируется с помощью молекулярных машин — энзимов. Хеликазы расщепляют двойную спираль на две комплементарные спирали. Полимераза, двигаясь вдоль одинарной спирали, выстраивает ее «зеркальную» копию. Такая копия называется дополнением Уотсона-Крика.
|
|
|
|
Принципиальная схема работы вычислительных блоков ДНК. В таком виде граф задачи был представлен в работе Леонарда Адлемана. Как видно из графа, для работы ДНК-компьютера ученому пришлось секвенировать 20 олигонуклеотидов, 7 из которых представляют вершины и 13 — ребра.
|
|
|
|
Абстрактная вычислительная машина, описанная в 1936 году Аланом Тьюрингом, представляла собой бесконечную ленту, поделенную на кадры с входящими данными, и управляющее устройство, движущееся вдоль ленты, считывающее данные и изменяющее свое состояние согласно некому внутреннему алгоритму. Чем не ДНК и полимераза?
|
|
Суп из кубиков LEGO
|
|
|
|
Чтобы решить задачу для графа с семью вершинами, Адлеман использовал простейший экстенсивный алгоритм: сгенерировать все возможные маршруты; исключить все пути, которые не проходят через заданные начальную и конечную точки; исключить все пути, которые проходят более семи вершин; исключить все пути, которые проходят более одного раза через одну вершину. ДНК-компьютер чем-то напоминает конструктор LEGO. Представьте себе, что есть кубики, обозначающие вершины графа, и перемычки, способные соединять вершины в цепочки любой длины.
|
|
|
|
Источник
|
