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

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

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

другой последовательности исключения, то вторичная структура будет
максимальна только при условии, что все последовательности исключения,
которые она содержит, максимальны. Проблемой вторичной структуры в рамках
модели стеблей является нахождение наилучшей максимальной вторичной
структуры. > Что касается данного множества стеблей, то они содержат
подмножество стеблей, в котором полное число ребер типа b будет настолько
большим, насколько это возможно.
В алгоритме, который будет здесь представлен, стебель обозначается
тройкой чисел: наименьшей и наибольшей содержащимися в нем вершинами, а
также числом содержащихся в нем ребер типа Ь.
524
X. Мартинец
Наименьшая вершина называется 5' -концом стебля, наибольшая - 3'-концом,
а число содержащихся в нем ребер типа b - длиной стебля.
В алгоритме предполагается, что множество рассматриваемых стеблей найдено
и что они упорядочены в соответствии со значением их 5'-конца. Выбранное
рабочее множество стеблей обычно состоит из всех стеблей, имеющих длину
выше некоторого минимума, и является таким, что ни один стебель множества
не есть часть любого другого стебля, входящего в состав множества. Для
данного рассматриваемого множества стеблей S определим теперь понятие
конкурентного множества C(s) для любого стебля s в множестве S как
множество всех членов множества S, перекрывающихся или связывающихся
узлом с s. Используя введенное выше обозначение М(/, у), для суммы длин
наилучшей вторичной структуры, образованной стеблями, все вершины 5' и 3'
которых разграничены вершинами < и у, мы можем рекурсивно определить M(i,
у), концентрируя внимание на стебле, разграниченном вершинами < и у,
который имеет наименьшее число 5' из всех стеблей, разграниченных
вершинами / и у. Назовем этот стебель s(/, у) и определим его
соответствующее конкурентное множество RC(s(i, у)) как содержащее
конкуренты s, которые разграничены вершинами i и у, но не исключаются
любым другим стеблем, разграниченным вершинами ( и у. Тогда M(i, у)
определяется соотношением
М(/, у) = шах \М(5'(х), З'(х)) + М(3'(х) + 1,у)1х
вЛС(5(/,у))}. (2)
Если множество стеблей состоит просто из всех ребер типа Ь, т. е. всех
стеблей длины 1, это соотношение интерпретируется следующим образом. Для
данных вершин / и у находим ребро типа Ь, которое инцидентно наименьшей
пронумерованной вершине, т.е. равно или больше, чем <, и другая вершина
которого (3'-конец) эквивалентна или меньше, чем у. Если имеется больше
одного такого ребра типа Ь, выберем из них ребро с наименьшим 3'-концом.
Это ребро типа b назовем s, соответствующее конкурентное множество s
будет образовано всеми ребрами Ь, разграниченными i и у, которые имеют те
же самые величины 5' - или 3' -концов, что и ребро s, или пересекают s.
Такой выбор s позволяет нам разбить цепь, простирающуюся от i до у, на
две части, и это можно осуществить столькими же способами, сколько
имеется членов конкурентного множества RC(s(i, у)). Вполне очевидно, что
величина Л/(/, у) должна быть получена в результате одного из этих
разбиений и что именно она будет соответствовать разбиению, дающему
наибольшее значение.
Динамика образования вторичной структуры РНК
525
Приближение ориентированного стебля дает надежду свести задачу к
разумному размеру при условии, что основное предположение справедливо, а
именно: если рассматривать стебли длины 1, то мы можем найти оптимальную
структуру и затем, удалив в такой отдельной структуре все стебли длины,
скажем, 3 или меньше, получить структуру, являющуюся оптимальной
относительно множества стеблей, состоящего из всех стеблей длины 4 или
больше. Обоснованность этого предположения не была проверена расчетным
или экспериментальным путем. Теоретическое доказательство ("за" или
"против") стоит, несомненно, на повестке дня.
То, что приближение ориентированного стебля может уменьшить сложность
задачи, становится очевидным на основании следующих соображений.
Алгоритм Нусинова имеет сложность по времени как rt3 в соответствии с
тем, что рассматриваются п(п - 1)/2 пар (/, j) и для каждой такой пары
должны быть тестированы все значения между / и j - 1 для осуществления
указанной максимизации. Поскольку среднее значение j - i пропорционально
п, мы, таким образом, имеем сложность алгоритма п3. С другой стороны,
нахождение всех стеблей длины к или больше является приближенно задачей
со сложностью п log п согласно недавно разработанной процедуре [2J; в
таком случае при наличии стеблей, число которых в среднем равно л (л -
1)/4*+1/2, задача выбора максимального подмножества в соответствии с
описанным выше алгоритмом является, по-видимому, задачей со сложностью
примерно N2. Выбор достаточно большой величины к обеспечивает, таким
образом, редуцирование сложности л4 к меньшей, чем была бы получена для
сложности л3.
Описанный алгоритм приближения ориентированного стебля легко
модифицируется для различных критериев оптимальности. Кроме того, он был
Предыдущая << 1 .. 194 195 196 197 198 199 < 200 > 201 202 203 204 205 206 .. 216 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed