Математическая биофизика клетки - Иваницкий Г.Р.
Скачать (прямая ссылка):
Если набор подслов Н таков, что для каждого подслова известны его граничные буквы, то может быть построено бинарное отношение А' = {(а,, Ь})}, такое, что А' будет представлять собой пары перекрытий (правые и левые), входящие в каждое подслово. В этом случае перекрываниям подслов можно поставить в соответствие вершины графа, а ребрам — сами подслова, выбрав направление ребра, например от левого перекрытия к правому (рис. 122, д).
Построение последовательности всех перекрывающихся подслов соответствует нахождению в таком ориентированном графе пути, проходящего через все ребра по одному разу. Такой путь
называется эйлеровым. Впервые эта задача была сформулирована в 1736 г. Для эйлерова пути известны эффективные алгоритмы и условия существования такого пути.
В терминах теории графов решение задачи восстановления слова можно интерпретировать как стремление заменить задачу Гамильтона задачей Эйлера.
Сведение задачи нахождения гамильтонова пути к задаче нахождения эйлерова пути можно рассматривать непосредственно на графе бинарных отношений подслов Д [131]. Если бинарное отношение А, определяющее граф, таково, что множество его ребер (граничных букв) разбивается на непересекающиеся подмножества *, то каждому ребру такого графа G можно поставить в соответствие вершину нового графа G', а каждой вершине графа G — ребро графа G' (граф G назовем «сопряженным» графу G'). Если исходная информация представляет собой набор подслов, полученных полными гидролизами, то всегда можно построить сопряженный граф и тем самым свести задачу восстановления слова к задаче Эйлера. Необходимым и достаточным условием существования гамильтонова цикла в ориентированном графе общего вида G является наличие в этом графе суграфа (т. е. графа G, у которого отсутствует часть ребер), такого, что сопряженный ему граф есть эйлеров (эйлеровым называется граф, в котором есть эйлеров цикл). В общем случае способ нахождения такого суграфа не известен.
Задача о единственности восстанавливаемого по исходной информации Н слова на графах интерпретируется как единственность гамильтонова или эйлерова пути и может быть решена построением всех возможных путей. В графах на рис. 122 возможны несколько путей. Способом борьбы с неоднозначностью ответа является пополнение исходной информации, например за счет увеличения числа полных или частичных гидролизов, что позволяет уменьшить число ребер на графе бинарных отношений.
Если информация задана продуктами полных гидролизов всей молекулы и полных гидролизов ее фрагментов, полученных частичным гидролизом, то для молекулы и фрагментов можно построить ориентированные графы («граф молекулы» и «графы фрагментов»). Очевидно, что множества вершин графов фрагментов будут подмножествами вершин графа молекулы, а множество ребер графов фрагментов — подмножествами ребер графа молекулы. Искомый гамильтонов путь должен проходить только через те ребра, входящие или выходящие из общих для этих графов вершин, которые являются общими для этих графов. Формально
1 Множество Н распадается на непересекающиеся подмножества S, если все слова набора являются внешними и использованы специальные виды перекрывания подслов.
а — частичный гидролиз фрагмента, ограниченного двумя минорными нуклеотидами Н, 2те; б — модифицированный «граф молекулы»
Ьлв cod
это осуществляется совмещением общих вершин графа фрагмента и графа молекулы и вычеркиванием тех из входящих в эти вершины или выходящих из них ребер, которые не являются общими для обоих графов. На рис. 123 показан «граф молекулы» (из рис. 122), построенный с учетом «графа фрагментов». Основная трудность в этой процедуре состоит в установлении общих для обоих графов вершин.
Установление тождества между вершинами различных графов, необходимое для их совмещения, называется идентификацией продуктов полных гидролизов фрагмента и всей молекулы. В общем случае идентификация не является однозначной процедурой и требует перебора вариантов, что приближает ее по сложности вычисления к задаче определения гамильтонова пути. Однако если все слова набора Н разные, то идентификация проводится тривиально. Идентификация может быть легко выполнена, если используемые фрагменты определенным образом -упорядочены или удовлетворяют достаточно жестким условиям, например
когда у всех фрагментов один из концов общий. Использование именно таких фрагментов довольно широко практикуется биохимиками [109, 110]. Кроме того, условие связности «графа фрагмента» также ограничивает возможные способы его совмещения с «графом молекулы». Поэтому оказывается полезным использовать процедуру идентификации во многих практически встречающихся задачах восстановления первичной структуры РЫК.
Рассмотрение задачи восстановления слов в терминах теории графов обеспечивает наглядность рассуждений, однако непосредственное использование графов для решения конкретных задач неудобно.
Разработано два типа алгоритмов для решения задачи восстановления слов: первоначально на основе кодирования исходной информации в виде состава второго ранга восстанавливаемого слова [128—130, 132J, а затем на основе алгебраического метода подстановок [131, 133—135].
