Научная литература
booksshare.net -> Добавить материал -> Химия -> Кинг Р. -> "Химические приложения топологии и теории графов " -> 199

Химические приложения топологии и теории графов - Кинг Р.

Кинг Р. Химические приложения топологии и теории графов — М.: Мир, 1987. — 560 c.
Скачать (прямая ссылка): himicheskieprilojeniya1987.djvu
Предыдущая << 1 .. 193 194 195 196 197 198 < 199 > 200 201 202 203 204 205 .. 216 >> Следующая

последовательно увеличивающихся подцепей до тех пор, пока не придем к
рассмотрению всей цепи. Таким образом, мы полагаем, что M(i,j) -
наибольшее число согласованных ребер типа Ь, которое может быть
изображено для вершин /, / + 1, ... , у - 1, у. То, что мы хотим знать, -
это величина М( 1, п) при условии, что имеется полное число п вершин, и
мы последовательно пронумеровали их вдоль цепи. Рекуррентным соотношением
является
Ч Г М('> к ~ *) + Щк + 1J -0+1
M(i,j) = max (1)
С M(i, j - I) для i < к < j.
522
X. Мартинец
В данном случае идея состоит в проверке возможности наличия ребра типа Ь,
исходящего из вершины у, соответственно для каждой из вершин от /' до у -
1. Если такое ребро могло бы привести к правильному значению для М(<, у),
то должно быть справедливо, что величина М(/, у) в действительности
является М(/, к - 1) + + М(к + 1,у - 1) + 1 и должна соответствовать
вершине к, для которой эта величина будет наибольшей. Но может оказаться,
что эта величина не больше, чем величина M{i, у - 1), соответствующая
случаю, когда вершина у не спарена с какой-либо вершиной к между к и у -
1. В результате мы имеем альтернативную возможность для М(/, у - 1).
Принятая в настоящее время реализация этого алгоритма [1] состоит в
первоначальном нахождении всех M(i, у), для которых у -
- i - 1, затем всех для которых у - / = 2, и т. д. до у -
- /' = п (т. е. длине цепи). Если мы считаем, что есть /,у-
элемент лхл-матрицы М, то эта матрица будет иметь поддиаго-нальные
элементы, и можно использовать, если необходимо, верхнюю часть матрицы
для хранения величины к, для которой предполагается, что М(/, у)
принимает значение в соответствии с приведенным выше рекуррентным
соотношением. Хранение этих величин к дает возможность построения графа с
ребрами Ь, который максимален. Таким образом, вершина п связана ребром
типа b с вершиной М(п, 1), вершина п - 1 связана ребром типа Ь с вершиной
М{п - 1,1) и т. д.
Альтернативное осуществление этого алгоритма должно было бы происходить
"снаружи вовнутрь". Так, например, если используется язык
программирования, в котором допускаются обращения в процедурах к самим
себе, то процедуру для нахождения М(1, п) следовало бы определить как
вызывающую саму себя для нахождения всех М( 1, к - 1) и М{к + 1, п - 1)
для 1 < к < п - 1 и т. д.
Трудность, связанная с этим алгоритмом, состоит в том, что хотя при
рассмотрении более сложных случаев он легко приспосабливается к критерию
оптимальности, основанному на функции энергии, но не так легко применим
для нахождения "грубых" структур. Алгоритм оказывается практичным для
последовательности, скажем, вплоть до 1000 оснований, но, когда их
намного больше, необходим новый подход к задаче. Так, например, вместо -
анализа в рамках отдельного уровня ребер типа b можно рассматривать
уровень, элементами которого являются группы ребер типа Ь, образующие
стебли, как определено выше. Это так называемое приближение
"ориентированного стебля". Доводы о его обоснован-
Динамика образования вторичной структуры РНК
523
ности обсуждаются ниже после постановки вопроса об алгоритме, который
пригоден для этого вида приближения, так же как и для более сложного
случая.
Идея алгоритма "ориентированного стебля" состоит в понимании того, что
ограничения инцидентности и пересечения для ребер типа b легко обобщаются
на случай, когда элементами являются стебли. Так, например, то, что два
стебля не могут быть инцидентными одной и той же вершине, преобразуется в
условие того, что два стебля не могут содержать одну и ту же вершину,
тогда как условие непересечения двух стеблей означает, что никакое ребро
одного из них не может пересекаться ни с одним ребром другого. Иногда это
условие непересечения стеблей рассматривается как избежание "узлов",
означающее, что половина одного стебля не может лежать между половинами
другого стебля, что соответствует первичной структуре. Два следующих
соотношения полезны при обсуждении стеблей. Говорят, что стебель х
включает стебель у, если обе половины стебля у лежат между половинами
стебля х, и стебель х исключает стебель у, если никакая из пбловин стебля
у не лежит между половинами стебля х. Преобразовав условие инцидентности
в условие перекрывания и условие непересечения в условие узлообразования,
мы получаем четыре соотношения, справедливые для стеблей, состоящих из
одного или большего числа ребер типа Ь: перекрывание, узлообразование,
включение и исключение.
Теперь мы можем определить последовательность исключения как такую
последовательность стеблей, что каждый член последовательности исключает
следующий за ним. В таком случае будет очевидно, что вторичная структура
состоит из вложенных последовательностей исключения, т. е. включенной в
стебель последовательностью исключения может быть другая
последовательность исключения и т. д. Если мы определим, что
последовательность исключения максимальна, когда она не является частью
Предыдущая << 1 .. 193 194 195 196 197 198 < 199 > 200 201 202 203 204 205 .. 216 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed