11.3. Восстановление слов по составу второго ранга

Пусть дано некоторое слово z и пусть первая и последняя буквы этого слова. Рассмотрим все двубуквеиные подслова слова Пусть подслово (см. рис. 121) к раз входит в Образуем упорядоченную пару Объединим все такие упорядоченные пары в одно множество и добавим к нему две граничные пары Полученное множество обозначим через Таким образом вводится оператор, который слову z ставит в соответствие множество

Рассмотрим множество пар, состоящее из следующих элементов: два граничных элемента внутренних При этом произвольные части подслова, натуральные числа и если то Множество такого типа называется составом второго ранга. Пусть дано множество являющееся составом второго ранга. Если существует слово которое является решением уравнения то есть состав второго ранга слова Задача восстановления слова заключается в реконструкции неизвестного слова по заданному составу второго ранга этого слова. К этому сводится задача установления первичной структуры по полным гидролизам [128, 129].

При построении соответствующих алгоритмов и решении вопроса единственности восстанавливаемого слова существенную оль играют регулярные преобразования слов. Пусть слово можно редставить в одной из форм:

где — части подслов, произвольные слова. Тогда каждое из слов соответственно для (1) и есть результат регулярного преобразования слова Слово z тогда и только тогда однозначно восстанавливается по своему составу второго ранга, когда оно не изменяется никаким регулярным преобразованием.

Сложность алгоритма, восстанавливающего слово (или проверяющего его существование и единственность), определяется элементарными операциями, число которых не превосходит где число букв в восстанавливаемом слове [130].

Располагая данными полного гидролиза и накладывая определенные ограничения на данные частичного гидролиза, можно использовать метод, который уменьшает возможный перебор. Этот метод называется алгоритмом покрытий [132].

Приближенная оценка времени вычисления указанного алгоритма имеет вид где среднее число фрагментов частичного гидролиза, число букв в восстанавливаемом слове, Основной перебор определяется величиной При различных частичных гидролизов оценка сложности примет вид