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

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

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

мулы. (Здесь ярко проявляется, как прогресс биохимических

технологий — в данном случае, недавно разработанный метод

закрепления цепочек ДНК на гелеобразующем полимере — воз-

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

ДНК, кодирующие интерпретации переменных, перемещаются

от одного такого участка к следующему под действием тока.

«Гелевый» ДНК-компьютер компактен и допускает авто-

матическое управление процессом фильтрации. Еще более су-

щественным его преимуществом является то, что фильтрация

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

конкретном опыте, оп исан ном в [31], формула имела 6 пере-

менных и 11 дизъюнктов и принимала значение 1 лишь при

одной из 64 возможных интерпретаций. Таким образом, среди

исходных цепочек ДНК лишь

часть соответ ствовал а иско-

мой интерпретации. После прохождения всех 11 фил ьтров доля

«правильных» цепочек возросла в 100 миллион ов раз и вероят-

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

почка кодирует искомую интерпретацию, составила 99,99994%.

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

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

ленных в настоящей книге. Так, в [85] возможные альтернати-

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

ет разрушение «неправильных» цепочек с помощью фермента

рибонуклеаза H. В «ДНК-автоматах» и з [24, 25] внутренние

состояния и программа суть цепочки ДНК, а исполнение про-

граммы обеспечивает эндонуклеаза Fok I. Отметим, что и эти

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

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

роятностные алгоритмы, см. [43, 74, 148, 227, 354]. Дело в

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

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

перебор. Например, в опыте, описанном в [31], исходный набор

молекул ДНК состоял из 3 ·10

цепочек. (При длине цепоч-

ки в 90 оснований масса такого количества ДНК составляет

примерно 0,014 миллиграмма.) Если с тем же количеством мо-

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

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

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

из 2

возможных интерпретаций была представлена хотя бы

одной цепочкой, приводит к неравенству n < 50. Чтобы пер е-

шагнутьй этот барьер, и нужны алгоритмы, которые переби-

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

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

предложенный в [227], использует только порядка 2

0,4n

цепочек

ДНК; иными словами, того же количества цепочек, что и в [31],

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

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

кают вычислительные процессы в живых клетках (см., напри-

мер, статьи [15, 78] и монографию [79]). Так, с вычислительной

точки зрения чрезвычайно интересна процедура сборки генов

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

(к нему принадлежит зн акомая по школьным урокам зоологии

инфузория-туфелька). Удивительно, но хранение генетич еской

информации в так называемом генеративном ядре инфузории

организовано по тому же принципу, по которому размещаются

файлы на жестком диске современного компьютера! При этом

сложный процесс извлечения фрагментов гена из ДНК ядра с

последующим соединением их в нужном порядке происходит

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

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

ДНК-вычислениям in vitro. Такие факты убеждают, что путь к

созданию по-настоящему эффективных ДНК-компьютеров ле-

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

В заключение упомянем многочисленные публикации [21,

40, 135, 136, 138, 147, 166, 177, 178, 183, 187, 189, 192, 193, 195,

196, 207, 218, 226, 227, 277, 283, 286, 298, 299, 301, 310, 320, 325,

326, 327, 329, 331, 332, 333, 337, 344, 345, 346, 347, 351, 353], в

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

ний и/или новые молекулярные алгоритмы, отличающиеся от

изложенных в настоящей книге по биохимическим основ ам, п о

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

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

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

Глава 3

Введение в теорию формальных языков

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

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

теории формальных языков. Как мы видели в главе 1, мо-

лекулы ДНК естественно представлять в виде «удвоенных»

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

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

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

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

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

ных вычислений удобно и естественно описывать посредством

(удвоенных) строк и операций над ними. Поэтому теория фор-

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

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

Эта глава является введением в теорию формальных язы-

ков в необходимом для данной книги объеме. За д опо лни тель-

ной информацией читатель может обратится к монографиям

в этой област и, например, к [7, 51, 66, 69, 145, 302, 304, 305].

Исчерпывающим источником является [HFL]. Читатель, уже

знакомый с теорией формальных языков, может обращаться к

главе 3 только при необходимости.

3.1 Основные понятия: грамматики, автоматы,

грамматические системы

Основные обозначения. Множество всех подмножеств дан-

ного множества X обозначим через P(X); если X — бесконеч-

ное множество, то через P

(X) обозначим множество всех его

конечных подмножеств. Мощность множества X обозначает-

ся через card(X). Множество натуральных чисел {0, 1, 2, . . . }

обозначим через N, а пустое множество — через ∅.

104 3. Введение в теорию языков

Алфавит — это конечное непустое множество абстрактных

символов. Через V

∗

обозначим множество всех строк символов

из алфавита V . Пустую строку обозначим через λ. В математи-

ческих терминах V

∗

— это свободный моноид, порожденный V

относительно операции приписывания. (Еди ниц ей этого монои-

да является λ.) Множество непустых стро к над V , т. е. V

∗

−{λ},

обозначим через V

. Каждое подмножество в V

∗

называется

языком над V . Говорят, что язык λ-свободен, если он не содер-

жит пустую строку (т. е. является подмножеством в V

Если x = x

, для некоторых x

, x

∈ V

∗

, то x

называется

префиксом строки x, а x

— ее суффиксом; если x = x

для

некоторых x

, x

∈ V

∗

, то x

называется подстрокой в x.

Множества всех префиксов, суффиксов и подстрок строки x

обозначаются через Pref(x), Suf(x) и Sub(x), соответственно.

Длина строки x ∈ V

∗

(число вхождений символов в x) обо-

значается через |x|. Число вхождений данного символа a ∈ V

в x ∈ V

∗

обозначается через |x|

. Если x ∈ V

∗

, U ⊆ V, то через

|x|

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

всех символов, не лежащих в U, т. е.

|x|

a∈U

|x|

Для L ⊆ V

∗

множество length(L) = {|x| | x ∈ L} называется

множеством длин языка L.

Множество символов, встречающихся в строке x, обозна-

чается через alph(x). Для языка L ⊆ V

∗

мы обозначим через

alph(L) множество ∪

x∈L

alph(x). Заметим, что alph(L) может

быть собственным подмножеством V .

Вектор Париха, связанный со строкой x ∈ V

∗

относи-

тельно алфавита V = {a

, . . . , a

}, — это Ψ

(x) = (|x|

, |x|

. . . , |x|

). Для L ⊆ V

∗

мы определим Ψ

(L) = {Ψ

(x) | x ∈ L}.

Говорят, что множество M векторов из N

линейно, если

можно найти такие v

∈ N

, 0 6 i 6 m, что

M = {v

i=1

| α

, . . . , α

∈ N}.

3.1. Основные понятия 105

Конечное объединение линейных множеств называется по-

лулинейным. Язык L ⊆ V

∗

называется полулинейным, если

(L) — полулинейное множество.

Операции над строками и языками. Булевы операции над

языками обозначаются обычным образом: ∪ — объединение,

∩ — пересечение, C — доп олн ение.

Произведение L

и L

— это L

= {xy | x ∈ L

, y ∈ L

Далее мы определяем:

= {λ},

i+1

= LL

, i > 0,

∗

= ∪

∞

i=0

(∗-итерация Клини),

= ∪

∞

i=1

(+-итерация Клини).

Отображение s : V −→ P(U

∗

), продолжаемое на V

∗

по

правилам s(λ) = {λ} и s(x

) = s(x

)s(x

) для x

, x

∈ V

∗

называется подстановкой. Для языка L ⊆ V

∗

мы полагаем

s(L) = ∪

x∈L

s(x). Вообще, любую n-местную операцию со стро-

ками g : V

∗

× · · · × V

∗

−→ P(U

∗

), мы распространяем на языки

над V таким образом:

g(L

, . . . , L

) =

[

∈ L

, 1 6 i 6 n

g(x

, . . . , x

Если подстановка s : V −→ P(U

∗

) такова, что множество s(a)

конечно для каждого a ∈ V, то s называется конечной подста-

новкой; если card



s(a)



= 1 для a ∈ V, то s называется морфиз-

мом. Если λ /∈ s(a) для каждого a ∈ V , то s — нестирающая

подстановка (нестирающий морфизм).

Морфизм h : V

∗

−→ U

∗

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

h(a) ∈ U для каждого a ∈ V , и слабым кодированием, если

h(a) ∈ U ∪ {λ} для всех a ∈ V . Если V

∩ V

= ∅, то мор-

физм h : (V

∪ V

)

∗

−→ V

∗

, о пред еляемый правилом h(a) = a

для a ∈ V

и h(a) = λ в противном случае, мы будем назы-

вать проекцией (на V

) и обозначать через pr

. Для морфизма

h : V

∗

−→ U

∗

мы определим отображение h

−1

: U

∗

−→ P(V

∗

)

106 3. Введение в теорию языков

(которое назовем обратным морфизмом) по правилу h

−1

(w) =

{x ∈ V

∗

| h(x) = w}.

Пусть L ⊆ V

∗

и k > 1. Морфизм h : V

∗

−→ U

∗

со свой-

ством h(x) 6= λ для всех x ∈ Sub(L) таких, что |x| = k, будем

называть k-ограниченным на L.

Если V — некоторый алфавит и мы рассматриваем некото-

рые фиксированные видоизменения g(a) символов a ∈ V (на-

пример, штрихование, подчеркивание и т.п.), то мы полагаем

= {g(a) | a ∈ V } и для любого w ∈ V

∗

пишем w

вме-

сто g(w). (В частности, в случае штрихования символов имеем

= {a

| a ∈ V } и для w = a

· · · a

∈ V

∗

, где a

∈ V, 1 6 i 6 k,

имеем w

= a

· · · a

Для x, y ∈ V

∗

определим их перетасовку как

x t⊥ y = {x

· · · x

| x = x

· · · x

, y = y

· · · y

, y

∈ V

∗

, 1 6 i 6 n, n > 1}.

Зеркальным отражением строки x = a

· · · a

, где a

∈ V,

1 6 i 6 n, назовем строку mi(x) = a

· · · a

. Как обычно,

mi(L) = {mi(x) | x ∈ L}.

Левое частное языка L

⊆ V

∗

при делении на язык L

⊆

∗

— это L

= {w ∈ V

∗

| существует строка x ∈ L

такая,

что xw ∈ L

Левая производная языка L ⊆ V

∗

по строке x ∈ V

∗

— это

∂

(L) = {w ∈ V

∗

| xw ∈ L}.

Правое частное и правая производная определяются сим-

метричным образом: L

= {w ∈ V

∗

| существует строка

x ∈ L

такая, что wx ∈ L

}, ∂

(L) = {w ∈ V

∗

| wx ∈ L}.

Семейство языков F L замкнуто относительно n-местной

операции g, если для любого набора языков L

, . . . , L

из F L

язык g(L

, . . . , L

) также лежит в F L.

Язык, который может быть получен из букв алфавита V

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

изведения и ∗-итерации Клини, называется регулярным; кроме

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

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

крайней мере один язык, отличающийся от ∅ и {λ}. (Мы

3.1. Основные понятия 107

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

жество» или «набор».) Трио — это нетривиальное семейство

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

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

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

AFL (аббревиатура AFL происходит от Abstract Language

Family, т. е. абстрактное семейство языков). Полу-AFL, за-

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

называется AFL. Говорят, что трио/полу-AFL/AFL полное, ес-

ли оно замкнуто относительно произвольных морфизмов (и ∗-

итерации Клини в случае AFL). Семейство языков, не замкну-

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

называется анти-AFL.

Следующие свойства определ енных выше операций бывают

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

носительно этих операций (например, для того чтобы доказать,

что семейство языков является AFL, нет нужды проверять его

замкнутость относительно всех шести операций):

1. Семейство всех регулярных языков есть наименьшее полное

трио.

2. Каждое (полное) полу-AFL, замкнутое относительно +-ите-

рации Клини, есть (полное) AFL.

3. Если семейство λ-свободных языков F L замкнуто относи-

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

морфизмов, то F L замкнуто и относительно пересечения

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

F L — полу-AFL. Если, кроме того, семейство F L замкнуто

относительно +-итерации Клини, то оно будет AFL.

4. Если семейство языков F L замкнуто относительно пересе-

чения с регулярными языками, объединения с регулярными

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

то относительно обратных морфизмов.

5. Каждое полу-AFL замкнуто относительно подстановк и λ-

свободных регулярных языков. Каждое полное полу-AFL

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

108 3. Введение в теорию языков

лярных языков и относительно левых и правых частных

при делении на регулярные языки.

6. Семейство λ-свободных языков является AFL, если оно за-

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

мов, обратных морфизмов и +-итерации Клини.

7. Если семейство языков F L замкнуто относительно пересе-

чения с регулярными языками, объединения с регулярными

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

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

обратных морфизмов.

Грамматики Хомского. Вообще говоря, грамматика — это

(конечное) устройство, порождающее строки языка по точно

определенному правилу (и тем самым задающее множество

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

тик являются частными случаями переписывающих систем.

Переписывающая система — это пара γ = (V, P ), в которой

V — алфавит, а P — конечное подмножество в V

∗

×V

∗

; элемен-

ты (u, v) из P записываются в виде u → v и называются пере-

писывающими правилами/продукциями (или просто правила-

ми или продукциями). Для x, y ∈ V

∗

мы пишем x =⇒

y, если

x = x

, y = x

для некоторых u → v ∈ P и x

, x

∈ V

∗

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

будем писать =⇒ вместо =⇒

. Рефлексивное и транзитивное

замыкание отношения =⇒ обозначается через =⇒

∗

Если к переписывающей системе такой, что во всех пра-

вилах u → v строка u непуста, добавить аксиому, то полу-

чится понятие чистой грамматики. Для чистой грамматики

G = (V, w, P ) с аксиомой w ∈ V

∗

определим язык, порожден-

ный G , как

L(G) = {x ∈ V

∗

| w =⇒

∗

x}.

Грамматика Хомского — это четверка G = (N, T, S, P ), в

которой N, T — непересекающиеся алфавиты, S ∈ N и P —

конечное подмножество в (N ∪ T )

∗

N(N ∪ T )

∗

× (N ∪ T )

∗

Алфавит N называется нетерминальным, а T — терми-

нальным, S — аксиома, а P — множество правил вывода грам-

3.1. Основные понятия 109

матики G. Правила (или продукции) (u, v) из P записываются

в виде u → v. Заметим, что |u|

> 1.

Для x, y ∈ (N ∪ T )

∗

мы пишем

x =⇒

тогда и только тогда, когда x = x

, y = x

, для неко-

торых x

, x

∈ (N ∪ T )

∗

и u → v ∈ P . Говорят, что y непо-

средственно выводимо из x (в грамматике G). Каждая строка

w ∈ (N ∪ T )

∗

такая, ч то S =⇒

∗

w, называется сентенциальной

формой. Язык, порожденный G, обозначается L(G) и опреде-

ляется так:

L(G) = {x ∈ T

∗

| S =⇒

∗

x}.

Две грамматики G

, G

называются эквивалентными, если

L(G

) − {λ} = L(G

) − {λ} (два языка совпадают с точностью

до пустой строки).

Вообще, в данной книге мы считаем два порождающих ме-

ханизма эквивалентными, если они п орождают один и тот же

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

Если в непосредственном выводе x =⇒ y, описанном вы-

ше, x

∈ T

∗

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

x =⇒

lef t

y. Левосторонний язык L

lef t

(G), порожденный грам-

матикой G, получается при выводах, все шаги которых лево-

сторонние.

В соответствии с видом пр ави л вывода грамматики Хомско-

го классифицируются следующим образом. Грамматика G =

(N, T, S, P ) называется:

Монотонной или неукорачивающей, если для всех u → v ∈ P

выполняется |u| 6 |v|.

Контекстной, если каждое правило u → v ∈ P устроено так:

u = u

, v = u

для u

, u

∈ (N ∪ T )

∗

, A ∈ N и

x ∈ (N ∪ T )

. (В монотонных и контекстных грамматиках

правило S → λ допустимо при условии, что S не встреча-

ется в правых частях правил из P .)

Контекстно-свободной, если u ∈ N для всех u → v ∈ P .

Линейной, если u ∈ N, v ∈ T

∗

∪ T

∗

для всех u → v ∈ P .

110 3. Введение в теорию языков

Праволинейной, если u ∈ N, v ∈ T

∗

∪ T

∗

N для всех u → v ∈ P .

Леволинейной, если u ∈ N, v ∈ T

∗

∪ NT

∗

для всех u → v ∈ P .

Регулярной, если u ∈ N, v ∈ T ∪ T N ∪ {λ} для всех u → v ∈ P .

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

бодная и регулярная грамматики — это соответственно грам-

матики типа 0, типа 1, типа 2 и типа 3.

Семейство языков, порожденных монотонными граммати-

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

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

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

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

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

Мы обозначаем через RE, CS, CF , LIN и REG семей-

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

контекстными, контекстно-свободными, линейными и регу-

лярными грамматиками (аббревиатура RE происходит от

Recursively Enumerable, т. е. рекурсивно перечислимый). Через

F IN мы обозначим семейство конечных языков.

Выполняются следующие строгие включения:

F IN ⊂ REG ⊂ LIN ⊂ CF ⊂ CS ⊂ RE.

Это иерархия Хомского, на которую нам придется постоянно

ссылаться в следующих главах.

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

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

лице 3.1. Из нее видно, что RE, CF, REG — полные AFL, CS —

неполное AFL, а LIN является полным полу-AFL.

Контекстно-свободная грамматика G = (N, T, S, P ) называ-

ется приведенной, если для каждого A ∈ N существует вывод

S =⇒

∗

xAy =⇒

∗

xwy, где x, w, y ∈ T

∗

(т. е. каждый нетерми-

нальный символ достижим из аксиомы и может быть заменен

на строку терминальных символов). Для каждой контекстно-

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

денную контекстно-свободную грамматику.