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

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

2.1. Опыт Эдлмана 61

мулировка, позволяющая использовать своего рода «язык про-

граммирования», понадобится и в следующем разделе.

По определению, пробирка — это мультимножество слов

(конечных строк) над алфавитом {А, Ц, Г, Т}. (С интуитив-

ной точки зрения пробирка — это вместилище одинарных це-

почек ДНК. Цепочки присутствуют в пробирке с некоторыми

кратностями, т. е. там может содержаться несколько копий од-

ной и той же цепочки). Следующие основные операции были

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

одинарных цепочек ДНК [4]. Однако их подходящие модифи-

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

Слить. Образовать объединение N

∪N

(в смысле мультимно-

жеств) двух данных пробирок N

и N

Размножить. Изготови ть две копии данной пробирки N. (За-

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

тимножеств.)

Обнаружить. Возвратить значение истина, если данная про-

бирка N содержит по крайней мере одну цепочку ДНК, в

противном случае возвратить значение ложь.

Разделить (или Извлечь). По данным пробирке N и слову

w над алфавитом {А, Ц, Г, Т} изготовить две пробирки

+(N, w) и −(N, w) такие, что +(N, w) состоит из в сех це-

почек в N, содержащих w в качестве (последовательной)

подстроки, а −(N, w) состоит из всех цепочек в N , которые

не содержат w в качестве подстроки.

Четыре операции слить, размножить, обнаружить и раз-

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

стые вопросы о наличии или отсутствии определенных под-

слов. Например, программа

(1) ввести(N )

(2) N ← +(N, A)

(3) N ← +(N, Г)

(4) обнаружить(N)

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

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

встречаются оба пурина A и Г. Следующая программа извле-

кает из данной пробирки все ц епоч ки, содержащие по крайней

мере один из пуринов A и Г, сохраняя кратности этих цеп очек :

(1) ввести(N )

(2) размножить(N ) на N

и N

(3) N

← +(N

, А)

(4) N

← +(N

, Г)

(5) N

← −(N

, А)

(6) слить(N

, N

)

Повторение операции размножить приводит к экспонен-

циальному (по отношению к числу итер аций ) росту числа це-

почек в данной пробирке.

Кроме четырех операций, пер ечисл енных выше и в [4], в

опыте Эдлмана используются комплементарность Уотсона–

Крика и два следующих варианта операции разделить:

Разделить по длине. По данным пробирке N и целому числу

n, изготовить пробирку (N, 6 n), состоящую из всех цепо-

чек из N длины не больше n.

Разделить по префиксу (суффиксу). По данным пробирке N

и слову w, изготовить пробирку B(N, w) (соответственно

E(N, w)), состоящую из всех цепочек в N, начало (соответ-

ственно конец) которых совпадает со словом w.

На данном этапе мы не вводим никакого формал изма для

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

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

опыту Эдлмана, мы опишем процедуру фильтрации с помо-

щью введенных выше операций. Итак, мы начинаем с п роби рки

N, содержащей результаты основного шага — реакции сшивки.

Так как двойные цепочки могут быть расплавлены на одинар-

ные путем подогрева раствора, можно считать, что N состо-

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

нуклеотидов s

, 0 6 i 6 6. (Мы пренебрегаем здесь хрупко-

стью одинарных цепочек, которую определенно следует учиты-

2.2. Решение задачи о выполнимости и взлом DES 63

вать при анализе б´ольших графов.) Тогда стадия фильтрации

в опыте Эдлмана может быть описана следующей программой.

Напомним, что каждый из олигонуклеотидов s

, 0 6 i 6 6, име-

ет длину 20.

(1) ввести(N )

(2) N ← B(N, s

)

(3) N ← E(N, s

)

(4) N ← (N, 6 140)

(5) для i от 1 до 5 выполнить N ← +(N, s

)

(6) обнаружить(N).

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

реализуемы указанные операции.

2.2 Как решить задачу о выполнимости

и взломать криптосистему DES?

Теперь мы сделаем существенный шаг вперед, представив

предложенное Липтоном [184] решение одной весьма общей

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

о задаче выполнимости пропозициональных формул. Здесь

приводится лишь краткое описание этой задачи; обсуждение

ее значимости см. в [293] и [305].

Мы рассматриваем (правильно построенные) формулы α,

составленные из пропозициональных переменных x

, x

, . . . с

помощью связок ∼, ∨, ∧ (отрицание, дизъюнкция, конъюнк-

ция). Вот пример такой формулы:

α = (x

∨ ∼ x

∨ x

) ∧ (x

∨ x

) ∧ (∼ x

∨ x

)∧ ∼ x

Интерпретация для подобной формулы α — это отобра-

жение f множества переменных, входящих в α, во множество

{0, 1}. Здесь 0 и 1 обозначают соответствен но значения «ложь»

и «истина». Таким образом, интерпретация есть присвоение

каждой переменной некоторого значения истинности. Значение

истинности, принимаемое формулой α при данной интерпрета-

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

ции f, может быть вычислено с помощью таблиц истинности

связок:

∨ 0 1

0 0 1

1 1 1

∧ 0 1

0 0 0

1 0 1

x 0 1

∼ x 1 0

Формула α выполнима, если она принимает значение 1 хотя

бы при одной интерпретации. Ясно, что α невыполнима в точ-

ности тогда, когда ее отрицание ∼ α является тавтологией,

т. е. принимает значение 1 при всех интерпретациях.

Следующее простое рассуждение показывает, что выписан-

ная выше формула α невыполнима. Предположим противное:

пусть α принимает значение 1 при некоторой интерпретации f .

Тогда каждый из четырех компонентов (в последующем имену-

емых дизъюнктами) принимает значение 1 при f. В частности,

f(∼ x

) = 1, что влечет f(x

) = 0. Из третьего дизъюнкта мы

видим, что тогда f(x

) = 0, а из второго — что f(x

) = 1. Но

при такой интерпретации первый дизъюнкт принимает значе-

ние 0, что приводит к противоречию.

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

ния задачи о выполнимости для данной пропозициональной

формулы удается применить тот или иной приспособленный к

специфике случая метод. В общем случае, однако, неизвестен

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

котором для формулы с k переменными перебираются все 2

возможных интерпретаций. Такой перебор вычислительно тру-

ден и уже при, скажем, 200 переменных практически неосу-

ществим. Известно, что задача о выполнимости NP-полна. С

интуитивной точки зрения это, вероятно, самая основная NP-

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

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

случаях NP-полные задачи весьма естественно сводятся к за-

даче о выполнимости.

Предложенное Липтоном [184] «молекулярное» решение за-

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

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

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

2.2. Решение задачи о выполнимости и взлом DES 65

sss

s s s

sss

s s

































k−1

out

. . .

Рис. 2.3. Граф интерпретаций.

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

му цепочек ДНК. Начнем с описания интерпретаций на языке

графов. Предположим, что мы имеем дело с пропозициональ-

ной формулой, содержащей k переменных. Рассмотрим ориен-

тированный граф на рис. 2.3.

Из вершины v

в вершину v

out

проходит в точности 2

путей (ни один из которых не будет гамильтоновым). Дей-

ствительно, для каждой из вершин v

, v

, . . . , v

k−1

существует

ровно два варианта продолжения пути, и эти варианты не

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

тей и множеством интерпретаций переменных x

, x

, . . . , x

существует естественное взаимнооднозначное соот ветстви е.

Например, путь v

. . . v

k−1

out

соответствует интер-

претации, при которой все переменные принимают значение 0.

В общем случае, путь v

. . . v

k−1

out

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

ет и нтерп ретации, при которой x

принимает значение i

(j = 1, . . . , k).

Поступим теперь с этим графом в т очно сти так, как в опыте

Эдлмана. Каждую вершину закодируем случайным олигонук-

леотидом, скажем, длины 20. Рассмотрим коды s

и s

двух

вершин таких, что из первой во вторую ид ет ребро e

i,j

. За-

пишем s

как s

= s

, где s

и s

— цепочки равной длины,

и аналогично запишем s

= s

. Тогда ребро e

i,j

кодируется

олигонуклеотидом h(s

), где h — морфизм Уотсона–Крика.

Далее процесс продолжается так же, как и в опыте Эдлма-

на. Для каждой вершины и каждого ребра данного графа бе-

рется большое количество кодирующих их олигонуклеотидов;

эти нуклеотиды смешиваются вместе и вступают в реакцию

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

сшивки. Снова олигонук леоти ды s

служат скрепками, благо-

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

смежным ребрам. «Конец» вершины (т.е. конец кодирующего

ее олигонуклеотида) и «начало» ребра могут соединиться, по-

скольку являются комплементарными по Уотсону–Крику. Ана-

логично, «конец» ребра может соединиться с «началом» сле-

дующей вершины. Поскольку коди рующие олигонуклеотиды

выбираются случайным образом и достаточно д лин ны (заме-

тим, что с увеличением числа переменных k длина 20 возмож-

но не будет достаточной), возникновение «нечаянных» путей

маловероятно. Это означает, что по завершении сшивки «бу-

льон» будет содержать двойные ц епоч ки ДНК, кодирующие

произвольные пути в данном графе. Как мы пояснили выше,

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

менных. Так как наш граф весьма симметричен, нет никаких

причин полагать, что появление одних путей более вероятно,

нежели появление других.

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

личию между опытом Эдлмана и решением Липтона задачи о

выполнимости; это различие касается основной реакции сшив-

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

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

пропозициональной формулы. Таким обра зом, можно всегда

начинать решение с одной и той же пробирки, в которой зако-

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

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

пропозициональными формулами. В опыте Эдлмана ситуация

иная — поскольку там граф служит исходным данным задачи,

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

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

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

здается указанным выше способом и содержит коды всех воз-

можных интерпретаций. К ней и будут применяться операции ,

описанные в предыдущем разделе. Следуя Липтону (см. [184],

с. 544), мы предполагаем, что начальная пробирка содержит

одинарные цепочки. (Дело молекулярной биологии — устано-

2.2. Решение задачи о выполнимости и взлом DES 67

s ss

s s

















out

Рис. 2.4. Граф, связанный с формулой β.

вить, выгодно ли на деле денатурировать двойные цепочки,

возникающие при создании начальной пробирки, или же про-

сто следует понимать наши операции как действия над одной

половиной двойной цепочки.)

Мы будем использовать операции разделить, слить и об-

наружить. Для начала мы обсудим пример, предложенный

в [184]. Рассмотрим пропозициональную формулу

β = (x

∨ x

) ∧ (∼ x

∨ ∼ x

Здесь две переменные, и соответствующий граф показан на

рис. 2.4.

Каждому из 4 путей из v

в v

out

в этом графе соответ-

ствует одна из 4 интерпретаций переменных x

и x

. Исходная

пробирка N

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

ки для каждого из этих путей и, следовательно, для каждой

интерпретации. С учетом длины олигонуклеотидов, кодирую-

щих вершины a

, эти олигонуклеотиды легко отличить д руг

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

Это значит, что, например, олигонуклеотид, кодирующий вер-

шину a

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

позиции. Если мы, применив операцию разделить, создад им

пробирку +(N

, a

), то мы выделим те интерпретации, в кото-

рых переменная x

принимает значение 1 (истина). (Напомним,

что пробирка +(N

, a

) состоит из таких цепочек из N

, в кото-

рых олигонуклеотид a

появляется в качестве подстроки.) Это

простое наблюдение лежит в основе всей процедуры.

Мы пользуемся естественными обозначениями интерпрета-

ций с помощью последовательностей из двух бит. Так, 01 обо-

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

значает интерпретацию x

= 0, x

= 1. Подобное обозначение

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

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

щие путям из v

в v

out

в графах интерпретаций. Так, цепочка

out

обозначается через 01. Ясно, что такое обозначе-

ние однозначно характеризует эту цепочку среди в сех цепочек,

отвечающих путям в графе н а рис. 2.4. Наконец, если пробирка

N состоит из цепочек указанного типа, записанных битовыми

последовательностями, то через S(N, i, j) мы обозначаем про-

бирку из тех цепочек из N, в которых i-й бит равен j, (j = 0, 1).

Согласно сделанному выше простому набл юдению, пробирка

S(N, i, j) получается из N с помощью операции разделить:

S(N, i, j) = +(N, a

Мы рассматриваем также пробирку, состоящую из тех ц епоч ек

из N, в которых i-й бит равен 1 − j:

−

(N, i, j) = −(N, a

Следующая программа решает задачу о выполнимости для

пропозициональной формулы β:

(1) ввести(N

)

(2) N

= S(N

, 1, 1)

(3) N

= S

−

, 1, 1)

(4) N

= S(N

, 2, 1)

(5) слить(N

, N

) = N

(6) N

= S(N

, 1, 0)

(7) N

= S

−

, 1, 0)

(8) N

= S(N

, 2, 0)

(9) слить(N

, N

) = N

(10) обнаружить(N

)

Заметим, что на каждом из шагов (2), (4), (6) и (8) операция

разделить применяется в смысле +(N, w), тогда как на ша-

гах (3) и (7) она применяются в смысле −(N, w). Следующая

2.2. Решение задачи о выполнимости и взлом DES 69

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

программы.

Шаг 1 2 3 4 5

Пробирка 00,01,10,11 10,11 00,01 01 10,11,01

Шаг 6 7 8 9

Пробирка 01 10,11 10 01,10

Таким образом, на шаге (10) команда обнаружить возвра-

щает значение истина.

Данная программа основана на полном переборе. На ша-

ге (1) в исходной пробирке содержатся всевозможные ин тер-

претации. На шаге (5) в пробирку попадают в точности те ин-

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

циональной формулы β. (Для этого либо x

, либо x

должны

принимать значение 1. На шаге (2) мы отделяем те интерпрета-

ции, при которых x

= 1. На шаге (4) из оставшихся интерпре-

таций выбираются такие, для которых x

= 1.) Далее интер-

претации в пробирке N

фильтруются так, чтобы на шаге (9)

отобрать те из них, которые обращают в 1 и второй дизъюнкт

пропозициональной формулы β.

Метод, проиллюстрированный на этом простом примере,

непосредственно применим в общем случае. Мы будем рассмат-

ривать пропозициональные формулы в конъюнктивной нор-

мальной форме. Это означает, что формулы выглядят как фор-

мулы α и β выше: они суть конъюнкции

( . . . ) ∧ ( . . . ) ∧ . . . ∧ ( . . . ),

где каждое из выражений в скобках есть дизъюнкция термов,

а каждый терм — это либо п еременная, либо ее отрицание. Из-

вестны быстрые алгоритмы для перевода произвольной пропо-

зициональной формулы в конъюнктивную нормальную форму.

Рассмотрим пропозициональную формулу

γ = C

∧ C

∧ · · · ∧ C

где каждый из m дизъюнктов C

есть дизъюнкция переменных

и их отрицаний. Предположим, что в записи γ участвует в об-

щей сложности k переменных x

, x

, . . . , x

. Тогда мы приходим

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

к ориентированному графу, изображенному на рис. 2.3 выше,

и к начальной пробирке N

, содержащей все k-битные после-

довательности (при условии, что цепочки из N

обозначаются

описанным выше образом). Начав с N

, мы пройдем через все

дизъюнкты формулы γ, выбрасывая из N

ненужные цепочки,

пока, пройдя через C

, не оставим лишь цепочки, отвечающие

интерпретациям, при которых γ принимает значение «истина».

Рассуждая по индукции, опишем в явном виде индуктив-

ный переход. Допустим, что каждая интерпретация, отвечаю-

щая цепочкам из N

, 0 6 i < m, обращает в истину подформулу

= C

∧ · · · ∧ C

а C

i+1

= y

∨ · · · ∨ y

, где y

— переменная или ее отрицание. На

начальном шаге мы имеем пробирку N

со всеми возможными

интерпретациями значений истинности и пустую формулу γ

Используя операции разделить и слить, превратим N

i+1

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

выше. Рассмотрим терм y

. Построим S(N

, n, 1), если y

= x

и S(N

, n, 0), если y

=∼ x

, 1 6 n 6 k. Таким образом, мы

извлечем из N

подпробирку S(N

, n, j), обращающую терм y

в 1. То, что осталось от N

, т. е. S

−

, n, j), исследуем по от-

ношению к терму y

и ее «положительную» часть (т. е. цепоч-

ки, обращающие y

в 1) со льем с S(N

, n, j). «Отрицательную»

часть подвергнем исследованию по отношению к терму y

, и

т. д., пока не исчерпаем весь дизъюнкт, исследовав y

Когда указанным образом будет построена пробирка N

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

обнаружить. Как и в оп ыте Эдлмана, этот заключительный

шаг можно модифицировать так, чтобы в том случае, когда

решение существует, найти его явный вид.

Вычислительная сложность описанного нами процесса

невелика: требуется m шагов, каждый из которых состоит

из нескольких применений операций разделить и слить.

Число таких применений не превышает числа переменных в

дизъюнкте. Другое дело, что при этом предполагается, что все

операции выполняются без ошибок. Это — далеко не очевидное

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