Возможно, настало время поиска новой парадигмы вычислений, первые контуры которой уже намечаются.
Важными вехами на пути, приведшем к появлению парадигмы ДНК-вычислений, являются следующие события:
· Открытие комлементарности оснований ДНК Э. Чарграфом в 1950 г.
· Открытие двойной спирали ДНК Д. Уотсоном и Ф. Криком в 1953 г.
· Создание теории самовоспроизводящихся автоматов Дж. фон Нейманом в 1957 г.
· Расшифровка генетического кода М. Ниренбергом и Г. Матэем в 1965 г.
· Первый эксперимент по вычислениям на ДНК Л. Эдлмана в 1994 г.
· Реализация конечного автомата на ДНК Э. Шапиро в 2001 г.
Мы привыкли к тому, что любой алгоритм для цифровой ЭВМ эквивалентен соответствующей машине Тьюринга. В области ДНК-вычислений мы имеем дело с совершенно другим аппаратом: молекулами ДНК и операциями над ними. Молекула ДНК (рис. 6.3) представляет собой двойную ленту, составленную из четырех оснований: А (аденин), Т (Тимин), Г (гуанин), Ц (цитозин).
Рис. 6.3 Молекула ДНК под электронным микроскопом
Нуклеотид с тиминовым основанием (рис. 6.4) состоит из 34 атомов. Диаметр двойной спирали ДНК – 2нм, расстояние между соседними парами оснований – 0.34 нм. Полный оборот двойная спираль делает через 10 пар. ДНК простейших типов вирусов содержит всего несколько тысяч звеньев, бактерий – несколько миллионов, а высших организмов – миллиарды [18]: ДНК млекопитающих содержит
[19, с.138].
Рис. 6.4 Строение нуклеотида с тиминовым основанием
Комплементарность оснований заключается в том, что образование водородной связи возможно только для пар А-Т и Г-Ц (рис. 6.5). Этот же рисунок иллюстрирует операции ренатурации и денатурации. Ренатурация – это соединение двух одинарных цепочек ДНК за счет спаривания комплементарных оснований. Денатурация – разъединение одинарных цепочек. Денатурация и ренатурация происходят при нагревании и охлаждении раствора с ДНК. Плавление ДНК происходит в диапазоне температур 85-95◦C. Некоторые катализаторы позволяют понизить температуру процесса.
Рис. 6.5 Комплементарность, ренатурация, денатурация
Все остальные операции с ДНК осуществляются при помощи катализаторов биологической природы - ферментов. Ферменты исключительно избирательны и высокоэффективны.
Удлинение цепочки ДНК происходит при воздействии на исходную молекулу ферментов – полимераз (рис. 6.6).
Рис. 6.6 Удлинение и укорочение
За укорочение и разрезание молекул ДНК отвечают ферменты – нуклеазы. Различают эндонуклеазы и экзонуклеазы. Экзонуклеазы осуществляют укорочение молекулы ДНК с концов (рис. 6.6), эндонуклеазы же разрушают внутренние фосфодиэфирные связи в молекуле ДНК (рис. 6.7). Эндонуклеазы могут быть весьма избирательными в отношении того, что они разрезают, где они разрезают и как они разрезают. Сайт-специфичные эндонуклеазы – рестриктазы – разрезают молекулу ДНК в определенном месте, которое закодировано последовательностью нуклеотидов – сайтом узнавания.
Рис. 6.7 Разрезание
Сшивка - операция, обратная операции разрезания, происходит под воздействием ферментов – лигаз (рис. 6.7)
Часто возникает необходимость модифицировать молекулы ДНК, например, для того, чтобы исключить из какой-либо операции. В живой клетке рестриктазы играют роль защитников от агрессии – например, в клетке бактерии, рестриктазы разрушают ДНК вируса-агрессора. Чтобы собственная ДНК не подверглась разрезанию, она модифицируется. Существует несколько типов модифицирующих ферментов – метилазы, фосфатазы и т.д. Метилаза имеет тот же сайт узнавания, что и соответствующая рестриктаза. При нахождении нужной молекулы, метилаза модифицирует участок с сайтом так, что рестриктаза уже не сможет идентифицировать эту молекулу (рис. 6.8).
Рис. 6.8 Модификация
Иногда необходимо увеличить количество определенных фрагментов ДНК. Это делается при помощи метода полимеразной цепной реакции (К. Маллис). Этот метод позволяет получить миллионы копий желаемой молекулы, даже если начать всего лишь с одного ее экземпляра (рис. 6.9).
Рис. 6.9 Полимеразная цепная реакция
Еще одной интересной операцией является операция сплетения (рис. 6.10). Две молекулы ДНК разрезаются, а затем полученные половинки сшиваются между собой.
Рис. 6.10 Сплетение
Кроме перечисленных операций, также доступны операции «вывода резальтатов»: секвенирование и разделение молекул ДНК по длине при помощи гель-электрофореза.
Первым опытом, результаты которого обошли весь мир, и дали толчок развитию области молекулярных вычислений, был опыт Л. Эдлмана (1994 г.). В опыте решалась задача: существует ли в данном направленном графе G гамильтонов путь, т.е. путь, который проходит через каждую вершину в точности один раз (рис. 6.11).
Для решения задачи был применен следующий алгоритм:
Вход. Ориентированный граф G с n вершинами, среди которых выделены
2 вершины – vin и vout.
Шаг 1. Породить большое количество случайных путей в G.
Шаг 2. Отбросить все пути, которые не начинаются с vin или не закан-чиваются на vout.
Шаг 3. Отбросить все пути, которые не содержат точно n вершин.
Шаг 4. Для каждой из n вершин v отбросить пути, которые не содержат v.
Выход. Да, если есть хоть один путь, нет – в противном случае.
Рис. 6.11 Граф в опыте Эдлмана
Каждая вершина графа кодировалась последовательностью из 20 нуклеотидов (рис. 6.12). Ребра кодировались так, как показано на рис. 6.12: бралась вторая половина цепочки для исходной вершины, и первая половина цепочки для конечной вершины, эти цепочки соединялись в одну, затем бралась комплементарная к полученной цепочке последовательность нуклеотидов, которой и кодировалось соответствующее ребро графа.
Рис. 6.12 Кодирование ребер и вершин в опыте Эдлмана
Опыт, осуществленный в 2001 г. группой Э. Шапиро [20] принципиально отличается от опыта Эдлмана тем, что и «исходные данные», и «программа» описываются молекулами ДНК, в то время как в опыте Эдлмана «программа» - это, по большому счету, последовательность реакций, задаваемых человеком.
В опыте Э. Шапиро был реализован конечный автомат, т.е. система, состоящая из множества состояний, алфавита, начального состояния, множества заключительных состояний и функции переходов. Данный автомат изображен на рис. 6.13. Автомат может находиться в двух состояниях – S0 и S1. Алфавит автомата состоит из двух символов – a и b. На вход автомату подается последовательность символов a и b. Автомат отвечает на вопрос – четное или нечетное количество символов b содержится во входной последовательности. Автомат может отвечать на 765 подобных «вопросов». Программирование автомата заключается в задании функции переходов, которой соответствует набор стрелок на рис. 6.13. И переходам, и состояниям, и входной последовательности в опыте Шапиро отвечают молекулы ДНК.
Рис. 6.13 Конечный автомат в опыте Э. Шапиро
Логическая схема опыта изображена на рис. 6.14. Основная идея заключается в следующем: входная последовательность кодируется цепочкой ДНК. Цепочка разрезается некоторым специальным образом при помощи рестриктазы Fok1 для того, чтобы к ней могла прилипнуть молекула, соответствующая одному из переходов автомата. Молекула-переход прилипает, происходит сшивание при помощи лигазы. Затем снова происходит разрезание при помощи рестриктазы Fok1, и прилипание следующего перехода. По окончании вычислений к молекуле – результату прилипает одна из молекул – меток. Естественно, молекулы, отвечающие за переходы, заданы так, чтобы работать в соотвествии со схемой автомата на рис. 6.13. В опыте Э. Шапиро использовались искусственные молекулы ДНК, синтезированные специально для эксперимента.
пар нуклеотидов, птиц - 
, пресмыкающихся - 
, насекомых - 
, высших растений - 
б бактерий - 
, вирус папилломы - 
[19, с.138].