9.2. Еще один вариант 413
тогда строка пропад ет, ибо из нее нельзя будет выделить тер-
минальную строку из-за невозможности удалить h(s
0
).
Мы вернулись к циклическому слову практически того же
вида, что и у слова, с какого мы начали (разница лишь в на-
личии упомянутых двухцепочечных участков). Мы уд аляем их
(нам не известно, как это можно сделать без денатурирования
двойных последовательностей из A
1
∪ A
2
) и повторяем дан-
ную процедуру. При встрече с маркером E мы либо продол-
жаем, либо присоединяем строку w(s
f
). Это создает цикличе-
скую последовательность, аналогичную последовательности на
рис. 9.3, делая возможным рассечение u
1
z
1
v
1
с помощью enz
1
слева о т блока h(s
f
)α
0
h(E), а u
n
z
n
v
n
с помощью enz
n
справа
от h(s
f
)α
0
h(E). Никакая сшивка невозможна: мы получаем две
линейные строки, которые не могут участвовать в последую-
щих отжигах со вспомогательными символами, а значит, рабо-
та системы здесь пр екр ащается. Строк и, содержащие только
блоки h(a), a ∈ T , и α
0
, α
1
, . . . , α
n
отбираются (фильтруются).
Итог вычислений — это строки, получаемые из отобранных вы-
черкиванием блоков α
0
, α
1
, . . . , α
n
.
Конечно, приведенная процедура — просто теоретический
план, в котором предполагается, что отжиг и сшивка проис-
ходят без ошибок, а две сплетаемые строки расположены ли-
нейно, никак не свернуты, и следовательно, комплементарные
фрагменты в этих двух строках расположены на одних и тех же
расстояниях. Как уйти от этого сильного предположения (за-
менив его использованием неустойчивых отжигов, когда спари-
ваемые фрагменты недостаточно длинны, или другой техники
способом) — вопрос непростой.
9.3 Комментарии к библиографии
Проблема сплетения циклических строк сформулирована
в [131]. Материал раздела 9.1 основан на [270, 271]. Цикли-
ческие строки, кроме того, рассматрив аются в [314, 352]. В
основе раздела 9.2 лежит работа [229], в которой исследуется
аналогичная операция.