11.4. Метод подстановки при восстановлении слов

Как было отмечено, отношение А разбивает множество на подмножества где число подслов в наборе таких, что в каждое множество входят лишь элементы, соответствующие подсловам, с которыми перекрывается справа подслово Например, если подслово то в подмножество входят все подслова типа Последовательности всех перекрывающихся подслов из набора называются -цепями [131]. Эквивалентными считают любые две последовательности, в которых элементы, стоящие на одинаковых местах, соответствуют равным подсловам. Все эквивалентные друг другу последовательности составляют некоторые классы эквивалентности -цепей.

Таким образом, существование единственной -последователь-ности (слова) соответствует существованию единственного класса эквивалентности на множестве всех -цепей.

Для дальнейшего изложения удобнее рассматривать замкнутые -цепи. Для этого будем считать, что конечное подслово перекрывается справа только с начальным, а начальное слева — только с конечным.

Подстановкой из элементов называется взаимно-однозначное отображение множества на себя. Подстановку можно записать в форме разбиения на циклы. При этом

за каждым элементом в строку выписывается элемент, на который он отображается, пока не встретится уже выписанный элемент; такая последовательность заключается в скобки и называется циклом (последний выписанный в ней элемент отображается на первый). Затем выписываются остающиеся элементы до тех пор, пока все они не окажутся выписанными в виде не имеющих общих элементов циклов.

Подстановка, не разложимая на циклы, т. е. представляющая собой единый цикл, называется конечным циклом. Всякая Л-цик-лическая цепь является конечным циклом, в котором за каждым следует элемент из

Для определения -циклической цепи необходимо построить произвольную -подстановку (возможно, не являющуюся конечным циклом), а затем последовательно проводить попарные объединения 1 циклов этой подстановки, пока не придем к конечному циклу.

Все совпадающие множества можно объединить в одно а все элементы которым соответствуют эти равные множества, — в одно множество . В этом случае -подста-новке соответствует отображение элементов каждого множества на элементы соответствующего множества а все возможные -подстановки могут быть записаны в виде схемы

Множества объединяют подслова имеющие одинаковые правые граничные части, а множества объединяют подслова имеющие одинаковые левые граничные частицы.

Например, построим схему фрагмента молекулы РНК (см. рис. 121).

Часть схемы между двумя вертикальными чертами будем называть блоком.

Необходимое и достаточное условие существования класса -подстановок — возможность установления взаимно-однозначного соответствия между элементами каждой пары множеств т. е. равенство чисел элементов в них. Это эквивалентно условию существования эйлерова графа.

Возможность построения конечного цикла легко проверяется путем последовательного объединения циклов любой построенной подстановки. Такое объединение осуществляется в этом случае очень легко, достаточно провести транспозицию пары элементов, входящих в разные циклы.

Например: выбираем подслово из первого столбца и подслово, на которое оно отображается, Для подслова находим подслово, на которое оно отображается в столбце 6: GU. Получаем первый цикл (GU, UAG). Аналогичным путем строится следующий цикл: (AGC, CG, GC, CCG, GAU, AUG, GGU, UAG). Объединение указанных циклов приводит к конечному циклу (GU, UAG, AGC, CG, GC, CCG, GAU, AUG, GGU, UAG). Отбрасывая перекрывающиеся части подслов, получаем исходное слово (см. рис. 121).

Если такой процесс попарного объединения, проводимый в одном произвольном случайно выбранном порядке, не приводит к построению конечного цикла, то конечный цикл на множестве не существует.

Вопрос о единственности конечного цикла легко решается с использованием метода, аналогичного рассмотренным ранее регулярным преобразованиям (см. раздел 11.3). Так, на множестве единственный класс эквивалентности -цепей определен тогда и только тогда, когда в случайно выбранной -цепи не существует двух пар элементов принадлежащих к одному множеству расположенных в цепи следующим образом: (в частном случае может равняться и таких, что не эквивалентно

Алгоритм построения последовательности путем объединения циклов имеет порядок менее где число подслов в наборе а проверка единственности построенной последовательности превосходит

Учет продуктов частичного гидролиза осуществляется также с использованием схемы (11.1). Если имеются перекрывающиеся продукты частичного гидролиза, то в тождественных им частях схемы появляются дополнительные блоки [133]. Дробление блоков уменьшает число элементов в каждом новом блоке и соответственно число возможных -цепей, так как в -цепи за каждым элементом верхней строки блока должен следовать какой-нибудь элемент нижней строки. Это эквивалентно уменьшению числа

ребер в «графе молекулы» при наложении на него «графа фрагментов», полученного частичным гидролизом.

Важным моментом при учете информации о частичных гидролизатах является возможность идентификации тождественных подслов.

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