Диссертация (1149246), страница 11
Текст из файла (страница 11)
В свою очередь вершиныu2 = (3, 11) и u10 = (6, 12) также соединены ребром, в силу того что вершины3 и 6 соединены ребром в графе G′1 , обладающим тем же свойством ("II"), чтои ребро (11, 12) в графе G2 . В свою очередь вершины u1 = (3, 8) и u10 = (6, 12)графе A несмежны, так как (3, 6) ∈ E1′ , а (8, 12) ∈/ E2 . Искомое множестворебер вспомогательного графа A: Z = {(u1 , u7 ), (u1 , u8 ), (u1 , u9 ), (u2 , u3 ), (u2 , u4 ),(u2 , u5 ), (u2 , u6 ), (u2 , u7 ), (u2 , u8 ), (u2 , u9 ), (u2 , u10 ), (u2 , u11 ), (u3 , u11 ), (u4 , u7 ),87Рис.
37: Вспомогательный граф A.(u4 , u10 ), (u5 , u10 ), (u5 , u11 ), (u6 , u10 ), (u6 , u11 ), (u7 , u10 ), (u8 , u10 ), (u8 , u11 ), (u9 , u10 ),(u9 , u11 )}.В графе A требуется найти наибольшую клику. Для этой цели будем использовать алгоритм MaxIS поиска наибольшего независимого множества вдополнительном графе к A (G = A), в котором множество Z есть множествонесмежных пар. В результате работы алгоритма получим наибольшее независимое множество Qmax графа G: Qmax = {u2 , u4 , u7 , u10 }. Для графа A множество Qmax представляет собой наибольшую клику. Подграф L′ ⊂ G′1 , индуцированный множеством вершин X ′ = {u12 , u14 , u17 , u110 } = {3, 4, 5, 6}, изоморфенподграфу L′′ ⊂ G2 , индуцированному соответствующим множеством вершинX ′′ = {u22 , u24 , u27 , u210 } = {11, 13, 14, 12}.
С учетом того, что мощность наибольшей клики графа A равна четырем, а значит, равна и количеству вершинмолекулярного графа G′1 , можно заключить, что молекула глицина содержитисследуемую подструктуру молекулы угольной кислоты.88§2. Построение потенциальных вторичных структур РНКЗадача определение вторичной структуры РНК является фундаментальнойпроблемой биоинформатики. Это объясняется тем, что вторичная структураРНК играет важную роль в молекулярной биологии [8].
Она имеет большоезначение для функционирования рибозимов [63], рРНК [39], рибопереключателей [51], сборки рибонуклеиновых комплексов [28], инициации сигналов трансляции [48].Первичная структура РНК представляет собой линейную последовательность азотистых оснований: A – аденин, U – урацил, G – гуанин, C – цитозин(Рисунок 38).Рис. 38: Первичная структура РНК.Формирование вторичной структуры происходит путем сворачивания первичной структуры за счет спаривания входящих в нее азотистых оснований,причем A может быть соединено с U , а G – c C [4]. В результате сворачиванияво вторичной структуре могут образовываться петли, стебли (Рисунок 39(a)), атакже в редких случаях псевдоузлы (Рисунок 39(б)). Образование псевдоузловвозможно не для всех РНК, поэтому часто ими пренебрегают при построениивторичной структуры [5].
В целях упрощения задачи мы также будем предполагать их отсутствие.89Не вдаваясь в детали сложных правил сочетания спаренных оснований вторичной структуры РНК, выделим основные моменты в них, которые позволятнам продемонстрировать комбинаторный способ построения искомых структур.б)а)Рис. 39: Стебли, петли (а) и псевдоузлы (б) вторичной структуры РНК.На Рисунке 38 представлен небольшой участок РНК, в котором цифрамиобозначены потенциальные спаренные основания A − U и G − C. Рассмотримпроцесс моделирования вторичной структуры РНК.
Каждой вершине графаT соответствует одно спаренное основание. Две вершины соединяются ребром,если спаренные основания, которым эти вершины соответствуют, совместимы.Например, вершина 1: A − U и вершина 5: U − A в графе T , заданном матрицейсмежности M (Рисунок 40), не смежны, т.к. пары A − U и U − A имеютобщее основание U (Рисунок 38), что недопустимо во вторичной структуре.Исходя из взаимного расположения спаренных оснований 6: U − A и 11: G − Cв первичной структуре РНК, соответствующие им вершины моделируемогографа также не могут быть соединены ребром. Соединение ребром вершин5: U − A и 11: G − C, 6: U − A и 8: A − U , 2: A − U и 10: G − C привелобы к образованию псевдоузлов, которые по нашему предположению в искомойвторичной структуре быть не могут.С учетом того, что потенциальные вторичные структуры РНК представляютсобой клики в построенном графе T , для их построения воспользуемся алгорит-90Рис. 40: Матрица смежности графа T .мом AllIS.
Для применения этого алгоритма построим дополнение T к графу T .Очевидно, что множество ребер исходного графа будет являться множествомнесмежных пар в графе T . Тогда граф T можно представить в виде:T = (V, SV,M ),где V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, SV,M = {(1, 3), (1, 7), (1, 8), (1, 9), (1, 11),(2, 7), (2, 8), (2, 9), (2, 11), (3, 5), (3, 6), (3, 10), (3, 11), (4, 5), (4, 6),(4, 10), (4, 11),(5, 9), (5, 10), (6, 10), (7, 11)}.Проведя поиск максимальных независимых множеств в построенном графе T с использованием программной реализации алгоритма AllIS, получимследующие клики исходного графа T : {4, 6, 10}, {4, 5, 10}, {3, 6, 10}, {3, 5, 10},{1, 7, 11}, {2, 7, 11}, {1, 3, 11}, {1, 8}, {2, 8}, {1, 9}, {2, 9}, {4, 11}, {5, 9}.
На Рисунках 41, 42 представлены соответствующие им потенциальные вторичные структуры.91Рис. 41: Потенциальные вторичные структуры РНК с тремя спаренными основаниями.Рис. 42: Потенциальные вторичные структуры РНК с двумя спаренными основаниями.92ЗАКЛЮЧЕНИЕВ диссертационной работе была рассмотрена проблема поиска максимальных независимых множеств в произвольном неориентированном графе. Изучение существующих алгоритмов ее решения позволило выбрать те, которыесогласно их теоретической оценке сложности являются одними из наиболееэффективных – это алгоритм Брона-Кербоша (для построения всех максимальных независимых множеств) и алгоритм Робсона (для поиска наибольшего независимого множества).В ходе диссертационного исследования были разработаны новые алгоритмыдля решения поставленной задачи: алгоритм AllIS и MaxIS, также модифицирован алгоритм Робсона для нахождения элементов наибольшего независимогомножества.Для экспериментальной оценки эффективности разработанных алгоритмовбыло проведено комплексное тестирование двух групп алгоритмов.
Первая группа – алгоритмы Брона-Кербоша, AllIS, полного перебора – для построения всехмаксимальных независимых множеств, вторая группа – алгоритмы Робсона,MaxIS, полного перебора – для поиска наибольшего независимого множества.В процессе тестирования получены графики зависимости времени работы исследуемых алгоритмов от размерности, а также от плотности, обрабатываемыхграфов. Анализ результатов тестирования позволил установить, что алгоритмыБрона-Кербоша, AllIS и MaxIS, в отличие от алгоритмов Робсона и полногоперебора, сильно чувствительны к изменению плотности графов в рамках фиксированной размерности.
При построении всех максимальных независимых множеств алгоритм AllIS показал лучшие результаты для обработки разреженныхграфов (при значении плотности ребер менее 10%), чем алгоритм Брона-Кербоша. В свою очередь при сравнении алгоритмов Робсона и MaxIS при решениизадачи о поиске наибольшего независимого множества выяснилось, что при93значении плотности ребер больше 70% эти алгоритмы имеют практически одинаковый порядок временного роста, не превышающий O(2 0.276n ).Завершающим этапом разработки алгоритмов стала реализация их в видепроблемно-ориентированного комплекса, в который также включены алгоритмы Брона-Кербоша и Робсона.Кроме этого была изучена сфера использования разработанных алгоритмовдля решения прикладных проблем. Практическое применение алгоритмовAllIS и MaxIS было продемонстрировано на примере решения двух задач избиоинформатики: поиск максимальной общей подструктуры органических соединений и построение потенциальных вторичных структур РНК.94Список литературы[1] Гантмахер Ф.
Р. Теория матриц. М.: Наука, 1966. – 576 с.[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи:пер. с англ. – М.: Мир, 1982. – 416 с.[3] Зыков А. А. Основы теории графов. М.: Вузовская книга, 2004. – 664 с.[4] Игнасимуту С. Основы биоинформатики: пер. с англ. – М.: Ижевск:НИЦ «Регулярная и хаотическая динамика», Институт компьютерныхисследований, 2007. – 320 с.[5] Козлов Н. Н., Кугушев Е. И., Сабитов Д.
И., Энеев Т. М. Компьютерныйанализ процессов структурообразования нуклеиновых кислот. ПрепринтИПМ им М. В. Келдыша РАН, 2002. № 42.[6] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: Построение ианализ: пер. с англ. – М.: Вильямс, 2005. – 1296 с.[7] Левин Л. А. Универсальные задачи перебора // Проблемы передачиинформации.
1973. Т. 9. №3. С. 115–117.[8] Миронов А. А. Метод поиска консервативных структур РНК. Молекулярнаябиология. 2007. Т. 41. № 4. c. 711–718.[9] Новиков Ф. А. Дискретная математика для программистов: Учебник длявузов. 3-е изд. – СПб.: Питер, 2009. – 384 с.[10] Олемской И. В. Алгоритм выделения структурных особенностей //Николай Ефимович Кирин: Сб. ст. Под ред. В. В. Жука, В. Ф. Кузютина.Спб: АССПИН. 2003. С.
224–251.95[11] Олемской И. В. Модификация алгоритма выделения структурныхособенностей // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика,информатика, процессы управления. 2006. Вып. 2. С. 55–65.[12] Олемской И. В. Методы интегрирования систем структурно разделенныхдифференциальных уравнений. СПб.: Изд-во С.-Петерб. ун-та, 2009. 180 с.[13] Олемской И. В., Фирюлина О.
С. Алгоритм вычисления наибольшегонезависимого множества // Обозрение прикладной и промышленнойматематики. 2012. Том 19. Вып. 3. С. 10.[14] Олемской И. В., Фирюлина О. С. Решение задачи о поиске максимальнойобщей подструктуры в молекулярных графах // Процессы управления иустойчивость: Труды 44-й межд. научн. конф. аспирантов и студентов /Под ред. Н. В. Смирнова, Т.
Е. Смирновой. СПб.: Издат. Дом С.-Петерб.гос. ун-та, 2013. С. 355–360.[15] Олемской И. В., Фирюлина О. С. Алгоритм поиска наибольшего независимого множества // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2014. Вып. 1. С. 81–91.[16] Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: теорияи практика: пер. с англ. – М.: Мир, 1980.
– 476 с.[17] Селиверстов A. В., Любецкий В. А. Алгоритм поиска консерватиныхучастковнуклеотидныхпоследовательностей//Информационныепроцессы. 2006. Т. 6. № 1. C. 33–36.[18] УльяновМ.В.Ресурсно-эффективныекомпьютерныеалгоритмы.Разработка и анализ. М.: ФИЗМАТЛИТ, 2008. – 304 с.[19] Фирюлина О. С., Олемской И. В., Нечипорук А. А. Алгоритмнахождения наибольшего независимого множества // Процессы управления96и устойчивость: Труды 40-й межд. научн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
