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

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

2.3. Переосмысление парадигмы вычислений 91

Если считать комплементарными буквы в парах (0,

0) и (1,

1),

то при таком соответствии эта комплементарность есть в точ-

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

Теперь видна следующая взаимосвязь между языком пере-

тасованных копий T S и двойными цепочками ДНК. Рассмот-

рим некоторую двойную цепочку, скажем,

ТАГЦАТЦАТ

АТЦГТАГТА

Сначала мы перепишем буквы согласно указанному выше со-

ответствию:

001

Взяв буквы по очереди из обеих цепочек, мы получим строку

000

110

00, принадлежащую T S. Это верно и в общем

случае: для произвольных двойной цепочки ДНК этот метод

дает слово из T S. То, что при этом получаются не все слова

из T S, несущественно, поскольку это зависит лишь от нашей

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

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

ющее набл юдение. На вывод об универсальности ДНК-вычис-

лений не повлияло бы, если бы одна из цепочек ДНК состояла,

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

динов. В нашей расширенной двоичной записи это означало

бы, что буквы с чертой и без черты всегда оказывались бы в

различных цепочках. То, что природа в действительности по-

ступает и наче, несомненно обеспечивает б´ольшую свободу дей-

ствий и б´ольшую эффективность вычислений.

Другой способ «считывать» слова из T S с нуклеотидов мо-

лекул ДНК основан на следующем кодировании:

верхняя цепочка нижняя цепочка

А, Т 0

Ц, Г 1

Другими словами, нуклеотиды А и Т отождествляются с 0

при появлении в верхней цепочке и с

0 при появлении в нижней

цепочке; нуклеотиды Ц и Г отождествляются с 1 в верхней це-

92 2. Начала молекулярных вычислений

почке и с

1 в нижней. Теперь, чи тая обе цепочки данной двух-

цепочечной молекулы ДНК слева направо так, что скорость

чтения каждой из цепочек нед етермин иро вана и не зависит от

скорости чтения другой цепочки, мы получаем строку из T S.

Читатель может попробовать проделать это с молекулой, при-

веденной выше. Обратно, мы можем получить все слова из T S,

рассмотрев все молек улы (полные двухцеп очечн ые последова-

тельности) и все варианты их прочтения указанным способом.

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

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

(А, Ц), (А, Г), (Т, Ц), (Т, Г).

Опишем вкратце, в каком смысле универсален язык T S.

Согласно общепринятому тезису Черча–Тьюринга, любое вы-

числение может быть осуществлено машиной Тьюринга и, та-

ким образом, вычисления характеризуются языками L

, при-

нимаемыми машинами Тьюринга. С другой стороны, каждый

такой язык L

может быть представлен в виде L

= f(T S), где

f — так называемое ОПМ-отображение, зависящее от языка

. (Аббревиатура «ОПМ» происходит от слов «Обобщенная

Последовательная Машина».) Таким образом, язык T S раз и

навсегда фиксирован, в то время как отображение f меняется

в зависимости от сп ецифи ки языка L

. Можно рассматривать

отображение f как своего рода устройство ввода/вывода. Для

вычислений, основанных на ДНК, ситуация вполне аналогич-

на. Комплементарность Уотсона–Крика раз и навсегда фикси-

рована и обеспечивает универсальность в том же смысле, что

и T S. Ключевая проблема при разработке компьютеров, осн о-

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

собленные для ДНК-вычислений типы вычислительных мето-

дов или, на языке теории, типы ОПМ-отображений.

Мы вернемся к математическим деталям в главе 3, в осо-

бенности в разделе 3.2. Результат о представлении L

= f(T S)

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

тельства весьма примечательна. Возможно, это отражает про-

стоту первичной структуры ДНК.

2.3. Переосмысление парадигмы вычислений 93

Читателю уже ясно, что в теоретических исследованиях

по ДНК-вычислениям должны использоваться следующие

два преи мущества, проистекающие из устройства молекул

ДНК: (1) комплементарность Уотсона–Крика, которая предо-

ставляет в наше распоряжение всю силу языка перетасованных

копий, и (2) множествен ность молекул ДНК, которая обеспе-

чивает массированный параллелизм в ходе вычисления. Мы

уже обсуждали как (2) влияет на парадигму вычислений. Что

касается (1), общая парадигма комплементарности может

быть сформулирована одним из следующих двух способов.

(a) Цепочка порождает комплементарную ей либо случайным

образом, либо под управлением некоторого устройства.

(б) Комплементарность двух цепочек приводит к такому явле-

нию, как связывание. И обратно, наличие связи между дву-

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

комплементарны.

Мы дали здесь весьма абстрактную формулировку пара-

дигмы комплементарности . Алфавит, н ад которым рассматри-

ваются цепочки, может быть б´ольшим, чем четырехбуквенный

алфавит цепочек ДНК, мы лишь предполагаем, что между бук-

вами имеется комплементарность. Математическая теория та-

ких более общи х алфавитов будет рассмотрена во второй части

этой книги.

Формулировка (б) есть абстракция идеи, присутствовавшей

уже в опыте Эдлмана. То, что мы «бесплатно» получаем язык

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

гих моделях ДНК-вычислений, также может быть объяснено

при помощи (б): связывание гарантирует комплементарность

вовлекаемых в него нуклеотидов, а это, как отмечалось выше,

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

С другой стороны, формулировка (а) пар ади гмы компле-

ментарности представляет комплементарность как операцию:

от данной строки (ц епочк и) мы переходим к комплементарной

ей. Такая операция может оказаться важной по крайней ме-

ре в определенных фазах ДНК-вычислений. Она представляет

несомненный теоретический интерес. Иногда, дополняя клас-

94 2. Начала молекулярных вычислений

сическую структуру операцией комплементарности, мы неожи-

данно получаем нечто новое. Так, например, происходит, когда

комплементарность добавляется в систему Линденмайера [221].

2.4 ДНК-вычисления:

надежды и предостережения

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

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

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

рования мгновенного описания машины Тьюринга и что до-

ступные в настоящее время протоколы и ферменты могут (по

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

ваны для выполнения последовательности модификаций, ко-

торые соответствова ли бы исполнению программы этой ма-

шины. В будущем исследования в молекулярной биологии мо-

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

ций с макромолекулами. Исследования в химии могут сделать

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

ми свойствами. В конечном счете можно вообразить появление

компьютера общего назначения, состоящего только из одной-

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

ным набором воздействующих на нее ферментов.»

Эти слова Эдлмана [2] в сжатом виде описывают большие

ожидания, связанные с ДНК-вычислениями. Даже в этих оп-

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

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

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

реальность или останутся лишь сн оской в книгах по истории

компьютерных наук, еще далек от какого-либо окончательного

решения. В этом разделе мы обсудим позитивные и негативные

перспективы ДНК-вычислений. В частности, мы вернемся к об-

суждению реализуемости некоторых важных для ДНК-вычис-

лений простых операций, рассматривавшихся в разделах 2.1

и 2.2. Уже на этом этапе важно отметить, что некоторые раз-

делы математической теории из второй части нашей кни ги вы-

ходят далеко за пределы этих простых наблюдений. Некоторые

2.4. ДНК-вычисления: надежды и предостережения 95

из более сильных результатов этой теории могут быть приме-

нены на практике, только когда будут развиты новые методы

в молекулярной биологии. Однако многое можно сделать, ис-

пользуя только простые операции, обсужденные в разделах 2.1

и 2.2.

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

но, взлом криптосистемы DES. Соответствующая техника из [6]

была описана в разделе 2.2; в [6] содержится также детальный

анализ реализуемости предлагаемой процедуры. Этот анализ

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

вычислений. Он показывает, что «реальные задачи» (а взлом

наиболее широко применяемой криптосистемы несомненно

является реальной задачей!) могут быть решены с помощью

небольших машин, которые не нуждаются в огромных количе-

ствах ДНК и используют разве лишь несколько ферментов. В

настоящее время криптографические задачи кажутся наиболее

подходящем полем приложения ДНК-вычислений, поскольку

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

что обычно требуется от электронных компьютеров.

Время, требуемое для взлома DES, оценивается в пять дней.

Эта оценка получена в предположении, что каждая отдельная

операция (выполняемая роботизированным комплексом) зани-

мает одну минуту. Если каждую операцию будет выполнять

студент-старшекурсник, то она может занять день, и тогда все

вычисление займет 18 лет. При скорости одна операци я в час

общая продолжительность составит 9 месяцев.

Насколько громоздким будет оборудование и какова веро-

ятность успеха? Некоторые из операций приводят к ошибкам

чаще, чем другие. Для каждой операции ее погрешность — это

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

Говоря, что общая по грешность есть E, мы имеем в виду, что

E — это погрешность наихудшей опер аци и, т. е. что все опе-

рации, задействованные в вычислении, имеют погрешность, не

превосходящую E. Если E — погрешность, то 1 − E обычно

называется выходом. Так, погрешности 10

−4

соответствует вы-

ход 99,99%.

96 2. Начала молекулярных вычислений

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

рассматривавшейся в разделе 2.2, кри птоан али тик знает па-

ру, со стоящую из открытого текста и соответствующего кр ип-

тотекста, и должен определить ключ. Все ключи, отобража-

ющие данный открытый текст в данный криптотекст, назы-

ваются выигрышными. Возможно, что существуют несколько

выигрышных ключей, хотя для DES их число вряд ли будет

большим. В идеальных условиях алгоритм возвращает «фи-

нальную пробирку», содержащую для каждого выигрышного

ключа по мень шей мере одну кодирующую его молекулу. Бо-

лее того, финальная пробирка не дол жн а содержать пусты-

шек, т. е. молекул, которые не кодируют выигрышный ключ и

попадают в финальную пробирку по ошибке. Е сли выигрыш-

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

что либо он не был создан в процессе инициал изаци и, либо он

был создан, но был по ошиб ке исключен в процессе вычисле-

ния.

В [6] представлены очень интересные численные результа-

ты, относящиеся к этой постановке. Они касаются необходимо-

го количества ДНК и числа пустышек в финальной пробирке.

Необходимое количество ДНК определялось из условия, чтобы

должен б ыть обеспечен «разумный шанс» — 63% или больше —

для попадания по крайней мере одного выигрышного ключа в

финальную пробирку. (Величина 63% появляется из пуассонов-

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

ходе инициализации.)

Если достижима погрешность 10

−4

, то потребуется лишь

немногим более одного грамма ДНК; вычисление дает величи-

ну 1,4 г. Более того, при погрешности 10

−4

, вероятность присут-

ствия пустышки в финальной пробирке составляет только 8%.

Положение разительно меняется, если достижима только

погрешность 10

−2

. Результаты весьма ясно показывают, где

проходит граница реализуемости для ДНК-вычислени й, по

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

особенно подходящих для решения с помощью ДНК. Пр и

погрешности 10

−2

, не говоря уже о более высокой погрешно-

2.4. ДНК-вычисления: надежды и предостережения 97

сти, ДНК-вычисления определенно нереализуемы. Для того,

чтобы выигрышный ключ оказался в финальной пробирке с

вероятностью 63%, потребовалась бы ДНК в количестве, при-

близительно равном 23 массам Земли, и при этом пришлось

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

стышек. При погрешности 10

−3

требуется менее килограмма

ДНК, что могло бы еще считаться реализуемым.

Размер оборудовани я диктуется количеством используемо-

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

именно с 96 пробирками параллельно. Оценки, приведенные

в [6], позволяют заключить, что при погрешности 10

−4

все обо-

рудование могло бы разместиться на столе.

Весьма специфическая задача взлома кри птоси стемы DES

достаточно ясно демонстрирует границы реализуемости для

ДНК-вычислений. Существенным является успешное, т. е. с

малой погрешностью, выполнение операций. Предполагая, что

малая погрешность достижима, можно изучать сложность

различных задач. Тогда в силу массиро ванн ого п ара ллел изма

ДНК экспоненциальные оценки сложности при последова-

тельных вычислениях, такие, как для некоторых хорошо

известных NP-полных задач, заменяются на линейные. Это

так для двух из задач, обсуждавшихся в р аздела х 2.1 и 2.2, —

задачи о гамильтоновом пути и задачи о выполнимости. В

то же время число цепочек ДНК, которые могут появиться в

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

циальному; так, для задачи о гамильтоновом пути оно имеет

порядок n!. В [28] читатель может ознакомиться с оценками

сложности различных задач в терминах двух параметров:

числа (биологических) шагов, выполняемых алго рит мом, и

числа используемых цепочек ДНК.

Такого рода оценки сложности уже рассматривались ранее

в теории параллельных алгоритмов. В этих рассмотрениях был

важен компромисс между числом шагов и числом паралл ель-

ных процессоров. Как мы видели, при ДНК вычислениях число

шагов может быть радикально сокращено за счет экспоненци-

98 2. Начала молекулярных вычислений

ального роста числа процессоров. Поскольку процессоры — это

цепочки ДНК, такое положение дел остается приемлемым.

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

ние. В большинстве случаев длина не вызывает никаких про-

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

Сведем теперь воедино все операции, обсуждавшиеся выше

в этой главе. Как мы отмечали, эти операции лежат в осн ове

многих алгоритмов для ДНК-вычислений и, следовательно,

дальнейшие лабораторные исследования их надежности, эф-

фективности и погрешности весьма существенны. (Сюда не

включена операция сплетения; она будет изучаться парал-

лельно с соответствующей математической теорией во второй

части книги.) Мы также напомним читателю основные совре-

менные би оло гическ ие методы для выполнения этих операций;

эти методы описаны в главе 1.

Плавление. Двухцепочечные ДНК разделяют на одинарные

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

При этом разрываются водородные связи между компле-

ментарными цепочками.

Отжиг. Эта операция обратна к операции п лавл ени я. Раствор

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

ментарные по Уотсону-Крику цепочки могут соединяться.

Слить. Содержимое двух пробирок переливают в одну.

Разделить (или Извлечь). Напомним, что эта операция по дан-

ным пробирке N и цепочке w производит новую пробир-

ку +(N, w), состоящую из всех цепочек в N, содержащих

w в качестве подцепочки. Для разделения посредством ги-

бридизации используется большое число цепочек, компле-

ментарных к w и закрепленных на матрице. К ним и при-

соединяются цепочки из N, содержащие w.

Размножить. Эта операция — применение полимеразной цеп-

ной реакции, ПЦР. На каждом шаге число цепочек удваи-

вается, что приводит к экспоненциальному росту.

Обнаружить и Разделить по длине. В обеих операциях ис-

пользуется метод гель-электрофореза.

2.4. ДНК-вычисления: надежды и предостережения 99

Наконец, различные функции, включая восстановление

ДНК и образование комплементарных цепочек, выполняются

ДНК-полимеразами. С их помощью можно синтезировать

специфические олигонуклеотиды. Тем не менее, вопрос об

определении оптимальных (как в смысле длины, так и в

смысле строения) олигонуклеотидов для ДНК-вычислений в

значительной степени остается открытым.

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

ждать, что на данном этапе биомолекулярные технологии

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

шению основных программистских задач, возникающих при

ДНК-вычислениях. Это — хорошая новость. Тем не менее,

остается еще много «подводных камней». (См., нап ример , пе-

реписку в журнале Science.) Поскольку данная книга главным

образом посвящена математической теории ДНК-вычислений,

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

возникающих при лабораторно й реализации алгоритмов. На-

пример, присоединение ц епоч ек к приблизительно парным им

цепочкам, а не в точн ости парным, может повести все вычис-

ление по ложному пути. Такие проблемы определенно должны

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

реальностью.

Возможно, наиболее конструктивный подход в данный мо-

мент состоит в том, чтобы рассматривать будущие ДНК-ком-

пьютеры как дополнение современных компьютеров в некото-

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

кажутся особенно подходящими для ДНК-вычислений. Осо-

бенностями, характерными для таких задач, являются, во-пер-

вых, то, что наилучшим из известных методов их решения яв-

ляется полный перебор, а во-вторых, то, что достижение успеха

с высокой вероятностью почти так же хорошо, как получение

определенного ответа. Именно так ставятся типичные крипто-

аналитические задачи. Успехи робототехники могут открыть

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

ющих как молекулярные, так и электронные компоненты.

100 2. Начала молекулярных вычислений

2.5 Комментарии к библиографии

За время, прошедшее с момента выхода в свет оригинала на-

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

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

ставляется уместным хотя бы кратко рассказать о некоторых

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

пьютера, полученных в последние годы. По согласованию с ав-

торами такой рассказ помещен именно здесь, в конце «общедо-

ступной» части книги; он опирается на несколько публикаций,

добавленных к библиографии редактором перевода.

Обсудим прежде всего некоторые экспериментальные ре-

зультаты. Выше описан только один реальный эксперимент —

основополагающий опыт Эдлмана. Конечно, эксперименталь-

ная база ДНК-вычислений отнюдь не сводится к одному это-

му опыту. Среди многочисленных публикаций (см., к пример у,

[13, 24, 25, 31, 85, 122, 165, 179, 186, 225, 295, 300, 340, 354]),

сообщающих об успешном испытании того или иного прото-

типа молекулярного компьютера, читателю можно рекомен-

довать статью [31], в которой подробно описан эксперимент,

осуществленный коллективом под руководством все того же

Эдлмана. Для понимания биохимической сути этого экспери-

мента вполне достаточны те минимальные сведения о методах

генетической инженерии, которые приведены в главе 1 насто-

ящей книги; с математической же точк и зрения речь идет о

реализации детально изложенной в разделе 2. 2 схемы Липто-

на [184] решения задачи о выполнимости пропозици онал ьных

формул. Однако ДНК-компьютер, сконструированный автора-

ми [31], существенно отличается от громоздкой «пробирочной»

модели, представленной в разделах 2.1 и 2.2. В этом компьюте-

ре весь процесс фильтрации происходит в тонкой стеклянной

трубке (длина 35 см, внутренний диаметр 0,3 см), заполнен-

ной гелем, и осуществляется с помощью гель-электрофореза. В

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

кулы-зонды, соответствующие дизъюнктам исследуемой фор-

Составлены редактором перевода.