Математическая биофизика клетки - Иваницкий Г.Р.
Скачать (прямая ссылка):
11.3. Восстановление слов по составу второго ранга
Пусть дано некоторое слово z и пусть я0, fr0 — первая и последняя буквы этого слова. Рассмотрим все двубуквеиные подслова слова z. Пусть подслово аг&; (см. рис. 121) к раз входит в z. Образуем упорядоченную пару <аг6,&). Объединим все такие упорядоченные пары в одно множество и добавим к нему две граничные пары <я01), (fe0, 1). Полученное множество обозначим через С2 [zj. Таким образом вводится оператор, который слову z ставит в соответствие множество С2 [z\.
Рассмотрим множество пар, состоящее из следующих элементов: два граничных элемента <а0, 1), <fe0, 1) и р внутренних {<ягЬ;, &,->}, 1 ^ i ^ р. При этом а0, Ъ0, ah bt — произвольные части подслова, kt — натуральные числа и если atbt = aqbv, то kt = kq. Множество такого типа называется составом второго ранга. Пусть дано множество L2, являющееся составом второго ранга. Если существует слово z, которое является решением уравнения L2 = С2 [z], то Ь2 есть состав второго ранга слова z. Задача восстановления слова заключается в реконструкции неизвестного слова по заданному составу второго ранга этого слова. К этому сводится задача установления первичной структуры по полным гидролизам [128, 129].
При построении соответствующих алгоритмов и решении вопроса единственности восстанавливаемого слова существенную оль играют регулярные преобразования слов. Пусть слово можно редставить в одной из форм:
Zi = x1ax2bxsaxibx(l (1), z2 = ухсу2сугсу^ (2),
где а, Ь, с — части подслов, х2, х3, ж4, хъ, уг, yz, у3, г/4 — произвольные слова. Тогда каждое из слов соответственно для (1) и (2) z[ = хуах4Ьх3ах2Ьхъ, z'2 = yicy3cy2cy} есть результат регулярного преобразования слова z. Слово z тогда и только тогда однозначно восстанавливается по своему составу второго ранга, когда оно не изменяется никаким регулярным преобразованием.
Сложность алгоритма, восстанавливающего слово (или проверяющего его существование и единственность), определяется элементарными операциями, число которых не превосходит и4, где п — число букв в восстанавливаемом слове [130].
Располагая данными полного гидролиза и накладывая определенные ограничения на данные частичного гидролиза, можно использовать метод, который уменьшает возможный перебор. Этот метод называется алгоритмом покрытий [132].
Приближенная оценка времени вычисления указанного алгоритма имеет вид пк (р!)2, где р — среднее число фрагментов частичного гидролиза, п — число букв в восстанавливаемом слове, к = 3 -г- 4. Основной перебор определяется величиной р. При т различных частичных гидролизов оценка сложности примет вид пк (р!)т.
11.4. Метод подстановки при восстановлении слов
Как было отмечено, отношение А разбивает множество И на подмножества [5, (i = 1, . . ., т), где т — число подслов в наборе Н\ таких, что в каждое множество Si входят лишь элементы, соответствующие подсловам, с которыми перекрывается справа подслово xt. Например, если подслово х\ = х\я;, то в подмножество St входят все подслова типа atyj, atyj+l и т. д. Последовательности всех перекрывающихся подслов из набора Н называются А-цепями [131]. Эквивалентными считают любые две последовательности, в которых элементы, стоящие на одинаковых местах, соответствуют равным подсловам. Все эквивалентные друг другу последовательности составляют некоторые классы эквивалентности А-цепей.
Таким образом, существование единственной Д-последователь-ности (слова) соответствует существованию единственного класса эквивалентности на множестве всех А-цепей.
Для дальнейшего изложения удобнее рассматривать замкнутые A-цепи. Для этого будем считать, что конечное подслово перекрывается справа только с начальным, а начальное слева — только с конечным.
Подстановкой из т элементов xt (i = 1, . . ., т) называется взаимно-однозначное отображение множества Н на себя. Подстановку можно записать в форме разбиения на циклы. При этом
за каждым элементом в строку выписывается элемент, на который он отображается, пока не встретится уже выписанный элемент; такая последовательность заключается в скобки и называется циклом (последний выписанный в ней элемент отображается на первый). Затем выписываются остающиеся элементы до тех пор, пока все они не окажутся выписанными в виде не имеющих общих элементов циклов.
Подстановка, не разложимая на циклы, т. е. представляющая собой единый цикл, называется конечным циклом. Всякая Д-цик-лическая цепь является конечным циклом, в котором за каждым х, следует элемент из St.
Для определения A-циклической цепи необходимо построить произвольную Д-подстановку (возможно, не являющуюся конечным циклом), а затем последовательно проводить попарные объединения 1 циклов этой подстановки, пока не придем к конечному циклу.
Все совпадающие множества Siq можно объединить в одно Sit а все элементы xiq, которым соответствуют эти равные множества,— в одно множество (i ^ то). В этом случае Д-подста-новке соответствует отображение элементов каждого множества Mt на элементы соответствующего множества St, а все возможные Д-подстановки могут быть записаны в виде схемы
