Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

Введение 11

лей, а также механических и электрических устройств, появив-

шихся только в XX веке. Возможно, сегодня мы находимся в

сходной ситуации по отношению к ДНК-компьютеру. Биохи-

мической технике пока недостает точности, и направление ее

развития не вполне адек ватн о специфическим запросам моле-

кулярных вычислений. Однако весьма вероятно, что здесь пе-

риод ожидания будет намного короче, чем в случае Беббиджа.

Надежды на успешное будущее молекулярных вычислений

основаны на двух фундаментальных феноменах. Это:

(a) массированный параллелизм цепочек ДНК,

(б) комплементарность Уотсона–Крика.

Вкратце обсудим роль этих феноменов.

(a) Большинство знаменитых «труднорешаемых» задач мо-

жет быть решено путем исчерпывающего перебора всех допу-

стимых вариантов. Непреодолимая пока трудность кроется в

том, что такой перебор слишком объемен, чтобы его можно бы-

ло осуществить, используя существующие технологии. Однако

благодаря плотности, с которой можно хранить информацию в

цепочках ДНК, и простоте, с которой можно размножать эти

цепочки, исчерпывающий перебор становится реальным. Ти-

пичным примером может служить задача раскрытия шифра:

в ней можно одновременно испробовать все ключи.

(б) Комплементарность Уотсона–Крика — это свойство, ко-

торым прир ода снабдила нас «бесплатно». Когда (в идеальных

условиях) возникает связь между двумя цепочками ДНК, то

мы знаем, что противоположные друг другу основания компле-

ментарны. Итак, если известна одна компонента п олучи вшейся

молекулы, то известна и другая, и это не нуждается в какой-

либо дополнительной проверке. Данное обстоятельство приво-

дит к мощному инструменту вычислений, поскольку, как мы

увидим позже, комплементарность выводит на сцену вычис-

лительно универсальный язык перетасованных копий. Различ-

ным образом кодируя информацию в цепочках ДНК, подлежа-

щих связыванию, мы способны делать далеко идущие выводы,

основываясь лишь на факте, что связывание имело место.

12 Введение



 

 

А Ц Г А

Т ТЦГТ



 

   



 

А Ц Г А Г Т Т Т Ц



 

 

А Т Г Ц



Рис. 4. Комплементарность Уотсона–Крика.

Обсудим парадигму комплементарности чуть подробней.

ДНК состоит из п олимер ных нитей, обычно именуемых це-

почками. Эти цепочки составлены из нуклеотидов, которые

различаются только своими основаниями. Таких оснований

четыре: А (аденин), Г (гуанин), Ц (цитозин) и Т (тимин). Хре-

стоматийная двойна я спираль ДНК возникает при связывании

двух отдельных цепочек. При образовании двойных цепочек

и проявляется феномен, известный как комплементарность

Уотсона–Крика. Связывание происходит за счет попарного

притяжения осно вани й: А всегда связывается с T, а Г — с Ц.

Комплементарность при образовании двойных цепочек схема-

тически представлена на рис. 4. (В этом сжатом изложении

опущены важные детали, такие, как ориентация цепочек.)

Рис. 5 и 6 иллюстрируют всю важность комплементарности,

показывая, в частности, разительное различие между ситуаци-

ями, когда комплементарность есть и когда ее нет. На рис. 5

пользователи ДНК-компьютера сталкиваются с безнадежной

задачей отыскания попарно соответствующих цепочек в огром-

ном ворохе одиночных нитей. Если бы ситуация действительно

была бы такой, перспективы молекулярных вычислений были

бы мрачны, да и теория, и злагаемая в этой к ниге, выглядела

бы довольно малопривлекательно. Но ситуация рис. 5 не отве-

Введение 13

Рис. 5. Отсутствие комплементарности.

Рис. 6. Присутствие комплементарности.

чает реальности. На деле пользователь безо всяких усилий, как

показано на рис. 6, получает готовый результат после того, как

соответствующие цепочки сами находят друг друга.

Парадигма комплементарности и некоторые ее обобщения

и модификации лежат в основе математической теории, обсуж-

даемой в главах 3–11 нашей книги. Главы 1 и 2 п редставляют

собой общее введение в молекул ярные вычисления, включаю-

щее введение (глава 1) в основные поняти я молекулярной био-

логии, необходимые в этой книге. В главе 2 обсуждаются так-

же перспективы лабораторной реализации. Например, нали-

чие ошибок при операциях с цепочками ДНК может привести

14 Введение

к весьма серьезным погрешностям. Поэтому в конечном счете

успех идеи молекулярных вычислений существенно зависит от

развития адекватной лабораторной техники.

Есть много оснований для изучения молекулярных вы-

числений и помимо надежд использовать ДНК как средство

для решения задач большой вычислительной сложности. Во-

первых, важно попытаться понять, как «вычисляет» сама

природа (вспомним, что невероятная изощренность и эффек-

тивность живых организмов достигнута как раз посредством

манипуляций с ДНК). Во-вторых, как мы увидим в после-

дующих главах, «вычисления с ДНК» приводят к вычисли-

тельным парадигмам, весьма отличным от общепри нятых в

сегодняшней информатике: к новым структурам данных, к

новым операциям как над новыми, так и над классическими

структурами данных (строками, языками), к новым моделям

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

не сбудется (например, из-за его чувствительности к ошибкам),

возможной альтернативой могло бы стать воплощение новых

вычислительных парадигм в рамках силиконовых технологий.

В такого рода рассуждениях можно пойти и дальше. Клас-

сическая теор етич еская информатика основана на операциях

переписывания — это так для большинства моделей, базирую-

щихся на автоматах и формальных языках. Как мы увидим,

природа производит «вычисления» с молекулами ДНК с помо-

щью операций совсем другого типа: вырезания и вклеивания,

подсоединения, вставки, удаления и т. п. Мы покажем, что, ис-

пользуя эти операции, можно построить модели вычислений,

равносильные машинам Тьюринга. Таким образом, вся теория

вычислимости может быть перестроена на этой новой основе.

Вопрос о практическом значении такой перестройки с точки

зрения приложений пока, по-видимому, преждевременен.

Глава 1

Как устроена ДНК и как с ней работают

Термин генетическая инженерия используют как общее на-

именование для всевозможных манипуляций с генетическим

материалом. В данной книге этот термин обозначает ман ип у-

ляции с ДНК и родственными ей молекулами вне живой клет-

ки, in vitro. С помощью таких манипуляций можно выполнять

различного рода вычисления.

В этой главе мы приводим основные сведения о строении

молекулы ДНК, а затем описываем тот «набор инструментов»

для манипулирования с ДНК, который применяется в молеку-

лярных вычислениях.

1.1 Строение ДНК

Молекула ДНК играет центральную роль в молекулярных вы-

числениях, а стало быть, и в данной книге. С точки зрения био-

химии, где молекулы делятся на большие и малые, на полиме-

ры и мономеры, ДНК — это полимер, составленный из мономе-

ров, называемых дезоксирибонуклеотидами. ДНК — ключевая

молекула в живой клетке, in vivo. Ее пор азител ьная структура

обеспечивает две важнейшие функции: кодирование образова-

ния белков и самоудвоение, при котором точная копия этой

молекулы передается дочерним клеткам.

Заглянем внутрь молекулы ДНК (ДезоксирибоНуклеино-

вой Кислоты) с той степенью детализации, которая будет

нужна в этой книге. Как уже сказано, мономеры, входящие

в ДНК, — это дезоксирибонуклеотиды. Каждый дезоксири-

бонуклеотид состоит из трех компонентов: сахара, фосфатной

группы и азотистого основания. Сахар, входящий в ДНК,

называется дезоксирибозой, что и объясняет происхождение

приставки «дезоксирибо». Чтобы упростить терминологию, бу-

16 1. Как устроена ДНК и как с ней работают



Рис. 1.1. Схематическая структура нуклеотида.

дем исп ользо вать более короткий термин «нуклеотид» вместо

«дезоксирибонуклеотид».

В состав дезоксирибозы входят пять атомов углерода. Для

удобства ссылок их нумеруют некоторым фиксированным об-

разом. Поскольку углерод встречается и в основании, во избе-

жание путаницы углеродные атомы сахара имеют номера от 1

до 5

(а не от 1 до 5). Фосфатная группа присоединена к 5

му, а основание — к 1

-му атомам углерода. В молекуле сахара

имеется гидроксильная группа (ОН), присоединенная к 3

-му

атому углерода.

Различные нуклеотиды отличаются друг от друга только

своими основаниями, которые бывают двух типов: пурины и

пиримидины. В нуклеотидах присутствуют два ви да пуринов:

аденин и гуанин, обозначаемых соответственно А и Г, и два

вида пиримидинов: цитозин и тимин, обозначаемых соот вет-

ственно Ц и Т. Поскольку нуклеотиды однозначно определя-

ются основаниями, говорят о А-, Г-, Ц- и Т-нуклеотидах в за-

висимости от входящего в них основания.

Структура нуклеотида показана (в очень упрощенном ви-

де) на рис. 1.1, где В — одно из четырех возможных основа-

ний (А, Т, Ц, Г), Р — фосфатная группа, а остальное (стер-

жень) — основа сахара (его углеродные атомы пронумерованы

от 1

до 5

1.1. Строение ДНК 17

C C

HOH

OPO

CHC



HN C

Сахар

Фосфат

Основание

Рис. 1.2. Строение нуклеотида с тиминовым основанием.

Для читателей, лучше знакомых с химией, рис. 1.2 дает

стандартную (но все же упрощенную) картину химической

структуры нуклеотида.

РНК (РибоНуклеиновая Кислота) — другой полимер, иг-

рающий ключевую роль в функционировании живой клетки.

Ее структура весьма близка к структуре ДНК. Мономеры

РНК, называемые рибонуклеотидами, отличаются от (дез-

оксирибо)нуклеотидов только двумя особенностями:

(1) Рибонуклеотид содержит другой сахар — рибозу, в кото-

ром в отличие от дезоксирибозы ко 2

-му атому углерода при-

соединена гидроксильная группа (ОН), а не водород (Н).

(2) Вместо азотистого основания тимин в рибонуклеотиде

встречается основание ура цил, обозначаемое У. Следовательно,

четыре возможных основания в РНК — это А, У, Ц, Г.

Читателя может заинтересоват ь тот факт, что риб онукл ео-

тид с основанием аденин (и с тремя фосфатными группами —

еще одна техническая деталь, которую мы опускаем) есть не

18 1. Как устроена ДНК и как с ней работают

B B

r r



s s

Рис. 1.3. Фосфодиэфирная связь.

что иное, как АТФ (аденозинтрифосфорная кислота), являю-

щаяся основным источником энергии в живой клетке.

Нуклеотиды могут соединяться двумя способами:

(1) 5

-фосфатная группа одного нуклеотида и 3

-гидро-

ксильная группа другого образуют сильную (ковалентную)

фосфодиэфирную связь. Такая связь показана на рис. 1.3.

Отметим, что в образовав шейся молекуле 5

-фосфатная

группа одного нуклеоти да и 3

-гидроксильная группа другого

доступны для дальней шего связывания. Тем самым задается

направление молекулы; можно говорить о направлениях 5

−3

или 3

−5

. Феномен направл енно сти молекул существен для

понимания того, как функционирует ДНК и как с ней можно

работать. Не менее важна направленность и тогда, когда, как

в данной книге, такие полимерные молекулы моделируются с

помощью слов.

(2) Осн ован ие одного нуклеотида взаимодействует с осн о-

ванием другого с образованием слабой водородной связи. При

этом соблюдается такое огр анич ени е: спариваться могут А с Т

и Ц с Г; никакие другие спаривания невозможны.

Этот принцип спаривания известен как принцип компле-

ментарности Уотсона–Крика. (Джеймс Д. Уотсон и Фрэнсис

Х. К. Крик расшифровали строение знаменитой двойной спи-

рали ДНК в 1953 г. и получили Нобелевскую премию за это от-

крытие.) Принцип комплементарности служит краеугольным

камнем для понимания устройства и функционирования ДНК.

1.1. Строение ДНК 19



либо B

= T и B

= A,

либо B

= C и B

= Г

Рис. 1.4. Водородная связь.

Рис. 1.4 иллюстрирует этот принцип: мы изобразили водород-

ную связь тонкой волнистой линией, чтобы подчеркнуть, что

она намного слабее фосфодиэфирной связи.

В действительности А–Т спаривание приводит к образова-

нию двух в одородных связей между нуклеотидами, тогда как

при Ц–Г спаривании образуются три водородные связи. Следо-

вательно, Ц–Г спаривание сильнее, чем А–Т спаривание: для

расщепления первого требуется больше энергии (например, бо-

лее высокая температура), чем для расщепления второго. Что-

бы отразить это различие, мы могли бы использовать две вол-

нистые линии для пары А–Т и три волнистые линии для пары

Ц–Г, но для наших рассмотрений это несущественно.

Используя фосфодиэфирные связи, можно образовать

одноцепочечную ДНК (рис. 1.5). Следуя стандартному со-

глашению, мы изображаем одноцепочечную молекулу так,

чтобы нуклеотид со свободным 5

-фосфатом оказался слева, а

нуклеотид со свободным 3

-гидроксильным концом — справа .

Поскольку мы идентифицируем нуклеотиды по их основа-

ниям (А-, Г-, Ц- или Т-нуклеотиды), одинарную цепочку

ДНК можно закодировать последовательностью букв (словом)

20 1. Как устроена ДНК и как с ней работают



ГА



PP P

Рис. 1.5. Одноцепочечная ДНК.

при условии, что будет указано направление. Так, одинарная

цепочка, изображенная на рис. 1.5, кодируется словом 5

-АЦГ.

Используя комплементарность Уотсона–Крика, из одноце-

почечной молекулы ДНК, показанной на рис. 1.5, можно обра-

зовать двухцепочечную молекулу, изображенную на рис. 1.6.

В действительности водородная связь между одиночными

нуклеотидами (рис. 1.4) слишком слаба для того, чтобы удер-

жать их вместе. Стабильность связи между длинными цепочка-

ми обеспечивается кумулятивным эффектом водородных свя-

зей между комплементарными основаниями молекулы ДНК.

Рис. 1.6 иллюстрирует общую схему соединения двух од-

ноцепочечных молекул с использованием водородных связей

(комплементарность Уотсона–Крика). Направления одинар-

ных цепей в двухцепочечной молекуле противоположны:

нуклеотид 5

-конца одной цепи связан с нуклеотидом 3

-конца

другой. При изоб ражении двухцепочечной молекулы (называ-

емой также двойной) принято располагать верхнюю цепь слева

направо в направлении 5

−3

, а нижнюю — слева направо в

направлении 3

−5

. Таким образом, верхняя цепь на р ис. 1.6 —

это 5

-АЦГ, а нижняя — 3

-ТГЦ.

Представление о двухцепочечной ДНК как о двух линей-

ных цепях, связанных в соответствии с комплементарностью

Уотсона–Крика, крайне упрощено, ибо в действительности в