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

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

Глава 6

Системы вставки и удаления

6.1 Вставка и удаление в контексте ДНК

В этой главе рассматриваются вычислительные модели, осно-

ванные на двух операциях, которые возникли в теории фор-

мальных языков по мотивам, связанным с лингвистикой. Эти

операции — вставка и удаление с зависимостью от контекста.

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

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

Представим себе, что в пробирке находится одинарная це-

почка ДНК вида 5

− x

uvx

z − 3

, где x

, x

, u, v, z — некото-

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

− ¯u¯y¯v − 5

, где через ¯u, ¯v обозначены строки, комплементар -

ные по Уотсону–Кри ку строкам u, v, а строка ¯y комплементар-

на некоторой новой строке y.

Цепочки будут соединяться так, что ¯u прилипнет к u, а

¯v к v, сворачивая ¯y. Получится картина, изображенная на

рис. 6.1(b). Если теперь разрезать двойную подцепочку uv (с

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

ная на рис. 6.1(c). Добавив праймер ¯z (и полимеразу), получим

двойную цепочку, показанную на рис. 6.1(d). При нагревании

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

цепочек будет иметь вид x

uyvx

z. Это означает, что строка y

оказалась вставлена между u и v.

С помощью подобного же частичного отжига теоретически

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

от контекста. Возьмем uyv в качестве исходной строки, доба-

вим ¯u¯v, а зат ем произведем аналогичную процедуру. На рис. 6.2

показаны все ее фазы (переход от (b ) к (c) производится путем

полимеризации и удаления петли y с помощью рестриктазы).

242 6. Системы вставки и удаления

(d)

(e)

¯z

¯x

¯v

¯y

¯u

¯x

¯z

¯v

¯y

¯u

(c)





(b)

u v

¯u ¯v

¯y

(a)

u v

¯v

¯y

¯u

Рис. 6.1. Вставка с помощью частичного отжига.

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

ции вставки и удаления. Такие операции происходят и в есте-

ственном процессе эвол юции в виде (случайных) точечных му-

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

вательность ДНК или удаляется из нее, в общем случае без

явного контроля контекста, показанного на рис. 6.1 и 6. 2. Эти

же операции происходят и при редактировании РНК, см. [23],

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

ходят проще и чаще, чем вставки и удаления А, Ц и Г.

Как и ожидалось, операции вставки и удаления, работаю-

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

ризациям рекурсивно перечислимых языков. (Грубо говоря,

порождающий механизм, равновыразительный грамматикам

Хомского типа 0, должен обладать «достаточным количе-

ством» встроенной контекстной зависимости и возможностью

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

6.2. Характеризации языков из RE 243

u v

¯z

¯x

¯v¯u

¯x

u v

(d)

(c)





u v

¯z

¯v¯u

(b)

(a)

¯v¯u

Рис. 6.2. Удаление с помощью частичного отжига.

ют и то, и др угое.) Ниже мы докажем такие характеризации

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

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

и удаления или, кратко, ВУ-системой.

6.2 Характеризации рекурсивно перечислимых

языков

ВУ-система — это конструкция

γ = (V, T, A, R),

в которой V — алфавит, T ⊆ V , A — конечный язык над V ,

R — конечное множество троек вида (u, α/β, v), где u, v ∈ V

∗

, и

(α, β) ∈ (V

×{λ})∪({λ}×V

). Элементы множества T — тер-

минальные символы, множества A — аксиомы, тройки из R —

правила вставки и удаления.

Запись (u, λ/β, v) означает, что β можно вставить между u

и v, а запись (u, α/λ, v) означает, ч то α можно удалить из uαv

Иначе говоря, (u, λ/β, v) соответствует переписывающему пра-

вилу uv → uβv, а (u, α/λ, v) соответствует переписывающему

правилу uαv → uv.

244 6. Системы вставки и удаления

Следовательно, для x, y ∈ V

∗

можно написать x =⇒ y, ес-

ли y можно получить из x применением упомянутых выше пра-

вил вставки и удаления. Точнее это означает, что имеет место

один из двух случаев:

1. x = x

uvx

, y = x

uβvx

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

, x

∈ V

∗

(u, λ/β, v) ∈ R,

2. x = x

uαvx

, y = x

uvx

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

, x

∈ V

∗

(u, α/λ, v) ∈ R.

Язык, порожденный системой γ, определяется как

L(γ) = {w ∈ T

∗

| x =⇒

∗

w для некоторого x ∈ A},

где через =⇒

∗

обозначено рефлексивное и транзитивное замы-

кание отношения =⇒.

Будем говорить, что ВУ-система γ = (V, T, A, R ) имеет вес

(n, m; p, q), если

n = max{|β| | (u, λ/β, v) ∈ R},

m = max{|u| | (u, λ/β, v) ∈ R или (v, λ/β, u) ∈ R},

p = max{|α| | (u, α/λ, v) ∈ R},

q = max{|u| | (u, α /λ , v) ∈ R или (v, α/λ, u) ∈ R}.

Обозначим через INS

DEL

, где n, m, p, q > 0, семейство

языков L(γ), пор ожденных такой ВУ-системой веса (n

, m

; p

), что n

6 n, m

6 m, p

6 p, q

6 q. Когда один из парамет-

ров n, m, p, q не ограничен, заменим его на ∗. Таким образом,

семейство всех ВУ-языков записывается как IN S

∗

DEL

∗

. По-

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

то при n = 0 предполагается, что m = 0, а при p = 0 предпола-

гается, что q = 0. Запись INS

означает, что не используются

правила вставки, а запись DEL

означает, что не используются

правила удаления.

Из определений очевидным образом имеем следующие

включения.

Лемма 6.1. (i) INS

DEL

⊆ INS

DEL

, для всех 0 6

n 6 n

, 0 6 m 6 m

, 0 6 p 6 p

, 0 6 q 6 q

(ii) INS

∗

DEL

∗

⊆ RE , INS

∗

DEL

⊆ CS .

6.2. Характеризации языков из RE 245

Используя ВУ-системы произвольных весов, легко охарак-

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

Теорема 6.1. RE = INS

DEL

Доказательство. Возьмем язык L ⊆ T

∗

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

матикой G = (N, T, S, P ) типа 0, в которой P содержит прави-

ла вида X → x для X ∈ N, x ∈ (N ∪ T )

∗

, |x| 6 2, и п рави ла

вида XY → UZ для X, Y, U, Z ∈ N (нап ример, возьмем G в

нормальной форме Куроды). Построим ВУ-систему

γ = (N ∪ T ∪ {E, K

, K

}, T, {SEE}, R),

R = {(X , λ/K

x, α

) | X → x ∈ P для X ∈ N, x ∈ (N ∪ T )

∗

|x| 6 2, и α

, α

∈ N ∪ T ∪ {E}}

∪ {(XY, λ/K

UZ, α

) | XY → UZ ∈ P для

X , Y, U, Z ∈ N, и α

, α

∈ N ∪ T ∪ {E}}

∪ {(λ, XK

/λ, λ) | X ∈ N}

∪ {(λ, XY K

/λ, λ) | X, Y ∈ N }

∪ {(λ, EE/λ, λ)}.

Символ E используется только для создания на конце строки

пары символ ов α

, необходимых в качестве контекста для

ВУ-правил. Символы K

, K

выполняют роль «киллеров»: K

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

слева от него, а K

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

непосредственно слева от него. Применением этих символов

правила вставки из R моделируют правила из P . Символы,

помеченные «киллерами» K

, K

, уже не могут использоваться

в качестве контекста для правил из R (α

, α

в перечисленных

выше правилах из R не могут совпадать с K

, K

). Следова-

тельно, L(G) = L(γ).

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

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

сматривая более короткие вставляемые и удаляемые строки и

короткие контексты, контролирующие вставки и удаления. В

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

ляются или удаляются лишь одиночные символы. Этот же во-

246 6. Системы вставки и удаления

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

работы с ДНК и РНК. Как упоминалось в предыдущем раз-

деле, вставки и удаления одиночных символов соответствуют

точечным мутациям в генетической эволюции.

ВУ-системы весьма ограниченного веса характеризуют ре-

курсивно перечислимые языки:

Теорема 6.2. RE = INS

DEL

Доказательство. Разумеется, нужно доказывать лишь вклю-

чение RE ⊆ INS

DEL

Рассмотрим язык L ⊆ T

∗

, L ∈ RE , порожденный грамма-

тикой G = (N, T, S, P ) типа 0 в нормальной форме Петтонена

(теорема 3.4), т. е. содержащей контекстно-свободные правила

X → x, в которых |x| 6 2, и не контекстно-свободные правила

вида XY → XZ для X, Y, Z ∈ N.

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

дом прави ле X → α

∈ P выполняется X 6= α

, X 6= α

6= α

. (Если потребуется, заменим X → α

на X → X

→ α

, α

→ α

, где X

, α

— новые символы.) Аналогично,

можно предполагать, что для каждого правила XY → XZ ∈ P

выполняется X 6= Y , X 6= Z и Y 6= Z. Более того, заменив

каждое правило X → α ∈ P , α ∈ N ∪ T , на X → αZ, Z → λ,

получим эквивалентную грамматику. Значит, можно считать,

что каждое правило из P имеет один из трех следующих видов:

1. X → α

для таких α

, α

∈ N ∪ T , что X 6= α

, X 6= α

6= α

2. X → λ,

3. XY → XZ для таких X, Y, Z ∈ N , что X 6= Y , X 6= Z,

Y 6= Z.

Кроме того, можно предполагать, что правила из P помечены,

причем это помечивание взаимно однозначно.

Построим ВУ-систему γ = (V, T, A, R), в которой

V = N ∪ T ∪ {[r], (r) | r — метка правила из P } ∪ {B, E},

A = {BSE},

и множество R сконструировано следующим образом.

6.2. Характеризации языков из RE 247

1. По каждому правилу r : X → α

∈ P типа 1, в котором

, α

∈ N ∪T , конструируются следующие правила вставки

и удаления:

(β

, λ/[r], Xβ

), для

∈ N ∪ T ∪ {B},

∈ N ∪ T ∪ {E},

(r.1)

([r]X, λ/(r), β), для β ∈ N ∪ T ∪ {E}, (r.2)

([r], X/λ, (r)), (r.3)

([r], λ/α

, (r)), (r.4)

(α

, λ/α

, (r)), (r.5)

(λ, [r]/λ, α

), (r.6)

(α

, (r)/λ, λ). (r.7)

2. По каждому прави лу r : X → λ ∈ P типа 2 конструируется

правило удаления

(β

, X/λ, β

) для

∈ N ∪ T ∪ {B}

∈ N ∪ T ∪ {E}

. (r.1)

3. По каждому правилу r : XY → XZ ∈ P типа 3, в котором

X , Y, Z ∈ N, конструируются следующие правила вставки

и удаления:

(β

X , λ/[r], Y β

) для

∈ N ∪ T ∪ {B}

∈ N ∪ T ∪ {E}

, (r.1)

([r]Y, λ/(r), β) для β ∈ N ∪ T ∪ {E}, (r.2)

([r], Y/λ, (r)), (r.3)

([r], λ/Z, (r)), (r.4)

(X , [r]/λ, Z), (r.5)

(Z, (r)/λ, λ). (r.6)

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

(λ, B/λ, λ),

(λ, E/λ, λ).

Получаем равенство L(G) = L(γ).

248 6. Системы вставки и удаления

(⊆) Каждый шаг вывода w =⇒ w

в G моделируется в γ

выводом BwE =⇒

∗

E, использующим правила (r.i), ассо-

циированные с примененным в w =⇒ w

правилом из P так, как

показано выше. Например, пусть w = w

, w

= w

для r : X → α

∈ P . Тогда мы получаем:

E =⇒ Bw

[r]Xw

E по правилу (r.1)

=⇒ Bw

[r]X(r)w

E по правилу (r.2)

=⇒ Bw

[r](r)w

E по правилу (r.3)

=⇒ Bw

[r]α

(r)w

E по правилу (r.4)

=⇒ Bw

[r]α

(r)w

E по пр ави лу (r.5)

=⇒ Bw

(r)w

E по правилу (r.6)

=⇒ Bw

E по правилу (r.7)

= Bw

Подобным образом можно поступить, когда шаг w =⇒ w

сде-

лан с помощью правила вида r : XY → XZ. Подробности

оставим читателю.

Вывод начинается с BSE. В любой момент символы B, E

можно удалить. Таким образом, любая строка терминальных

символов, порожденная G, лежит в L(γ).

(⊇) Рассмотрим строку BwE. Первоначально w = S. Мож-

но к этому применить правило (r.1) из группы 1, или правило

удаления (β

, X/λ, β

), ассоциированное с X → λ ∈ P , или пра-

вило (r.1) из группы 3, или правило из группы 4. Допустим, что

применено (β

, λ/[r], Xβ

) для некоторого r : X → α

∈ P .

Тогда имеем

E =⇒ Bw

[r]Xw

Поскольку правила из P однозначно помечены, X 6= α

и у

правил вида (r.1) в группах 1 и 3 левый контекст указывает на

символ, расположенный непосредственно перед X (то же мож-

но сказать и о правилах группы 2), есть лишь одно правило,

в котором участвует символ X, а именно (r.2). В конце кон-

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

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

6.2. Характеризации языков из RE 249

После этого подстрока [r]X строки Bw

[r]Xw

превратится в

[r]X(r). Дал ее, вновь есть лишь одно возможное продолжение

по правилу (r.3), которое стирает символ X. Символ [r] мож-

но будет удалить только после того, как между [r] и (r) будет

вставлен символ α

. По правилу (r.5) между символами α

и (r)

можно вставить символ α

. Необходимый для этого в качестве

левого контекста символ α

должен появиться на предыдущем

шаге по правилу (r.4) между [r] и (r), поскольку X 6= α

. После

появления α

, отличного как от α

, так и от X, п о правилу (r.7)

можно удалить (r). Благодаря контекстам, никакое другое пра-

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

стве левого или правого элемента или удалить их. Таким об-

разом, после применения (r.1), обязательно должны сработать

все правила (r.i), 2 6 i 6 7, ассоциированные с r : X → α

чем и моделируется применение правила X → α

Из тех же соображений после применения правила (β

X ,

λ/[r], Y β

), ассоциированно го с r : XY → XZ ∈ P , необходимо

продолжить процесс правилами (r.i), 2 6 i 6 6 (необязательно

применять их правила по порядку, но только эти правила мо-

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

самым, моделируется применение правила XY → XZ.

Правила удалени я (β

, X/λ, β

) напрямую соответствуют

стирающим правилам из P . Маркеры B, E можно удалить

на любом шаге. Следовательно, γ может порождать только

строки из L(G).

Теорема 6.3. RE = INS

DEL

Доказательство. Рассмотрим язык L ∈ RE , L ⊆ T

∗

и возь-

мем такую грамматику G = (N, T, S, P ) в нормальной форме

Гефферта, приведенной в теореме 3.5(2), что L = L(G). Сле-

довательно, P = P

∪ P

, где P

содержит только контекстно-

свободные правила вида

S → uSv для u, v ∈ (N ∪ T − {S})

S → x для x ∈ (N ∪ T − {S})

а P

состоит из правил вида XY → λ для X, Y ∈ N.

250 6. Системы вставки и удаления

Построим ВУ-систему

γ = (V, T, A, R),

в которой

V = N ∪ T ∪ {c, K, K

, F }

∪ {[S, r] | r : S → x ∈ P

}

∪ {[X, r, i] | r : S → zXw ∈ P

, z, w ∈ (N ∪ T )

∗

, i = |z| + 1,

X ∈ N ∪ T },

A = {Sc},

и R содержит следующие правила вставки и удаления:

A. Заменим каждое правило S → uSv из P правилом S →

uScv. Правила S → x, в которых |x|

= 0, оставим без

изменений. Обозначим через P

получившееся в результа-

те этого множество. Для каждого правила r : S → X

. . . X

∈ P

, где X

∈ N ∪ T ∪ {c}, 1 6 i 6 k, k > 1, напишем

следующие правила:

1. (S, λ/[S , r], c),

2. (S, λ/K, [S, r]),

3. (λ, SK/λ, λ),

4. ([S, r], λ/[X

, r, 1], c),

5. ([X

, r, i], λ/[X

i+1

, r, i + 1], c), 1 6 i 6 k − 1,

6. ([S, r], λ/K, [X

, r

, 1]),

7. (λ, [S, r]K/λ, λ),

8. ([X

, r, i], λ/X

, [X

i+1

, r, i + 1]), 1 6 i 6 k − 1,

9. ([X

, r, i], λ/K, X

), 1 6 i 6 k − 1,

10. (λ, [X

, r, i]K/λ, λ), 1 6 i 6 k,

11. ([X

, r, k], λ/F, c),

12. ([X

, r, k], λ/X

, F ),

13. ([X

, r, k], λ/K, X

14. (X

, λ/K

, F ),

15. (λ, K

F/λ, λ).

B. Кроме этого, добавим в R правила

(λ, XY /λ, λ) для XY → λ ∈ P