Отчет о научно-исследовательской работе, выполняемой по государственному контракту 14. 740. 11. 0001 «Разработка алгоритмов для биоинформационного анализа комплексных метаболических и молекулярно-генетических сетей»

3Разработка метода поиска замкнутых контуров в сложных сетях с семантической разметкой. Структурный анализ ассоциативных или генных сетей имеет прямое практическое применение, особенно в фармакологии. На его основе проводят поиск белков-мишеней для создания новых лекарственных препаратов. Для этого необходимо выявление ключевых узлов с большим количеством связей как потенциальных мишеней. Анализ связи между белками, компонентами генной сети полезен для изучения последствий ингибирования или, напротив, сверхэкспрессии белка-мишени, которые могут сказываться на поведении всей системы в целом. Алгоритм поиска фундаментального множества циклов При анализе графов одной из подзадач является поиск фундаментального множества циклов. Полезность этого множества обусловлена тем, что оно полностью определяет циклическую структуру графа. Каждый цикл в графе может быть представлен комбинацией циклов из фундаментального множества. Рассмотрим остовное дерево Г0 = (X, U0, Ф) графа Г = (X, U, Ф). Любое ребро, не принадлежащее U0, т. е. любое ребро из U \ U0, пoрождает в точности один цикл при добавлении его к U0. Такой цикл является элементом фундаментального множества циклов графа Г относительно дерева Г0. Так как каждое остовное дерево графа Г включает |X| - 1 ребро, в фундаментальном множестве циклов относительно любого остовного дерева графа Г имеется |U|-|X|+1 циклов. Пусть F = {С1,С2, ... , С|U|-|X|+1} — фундаментальное множество циклов, где каждый цикл Сi, является подмножеством ребер СiU. Тогда любой цикл графа Г можно записать в виде ((...(Сi1Сi2)...)Сi), где символ обозначает операцию симметрической разности, . При порождении фундаментального множества циклов удобно использовать метод поиска в глубину; он строит остовное дерево, и каждое обратное ребро порождает цикл относительно этого дерева. Для того чтобы следить за ребрами дерева, используется «поиск в глубину» со стеком, в котором хранятся все текущие вершины пройденного пути в данный момент. Когда попадаем на обратное ребро, обнаруженный цикл будет состоять из этого ребра и ребер, соединяющих вершины из верха стека. Ниже приведено представление этого алгоритма на псевдокоде: for vX do Mark[v]=0; {Начальные метки вершин} count=0; jС=0; {Счетчик числа циклов} пС=0; {Вершина стека циклов} for vX do if Mark[v]=0 then begin nC=nC+1; C[nC]=v; Cycle(v, 0); пС=пС-1; end; Procedure Cycle(x, у) count=count+1; Mark[x]=count; {Вершина исследована} for vAdj[x] do begin nC=nC+1; C[nC]=v; {Вершину в стек} if Mark[v]=0 then Cycle(v, x) else if Mark[v] < Mark[x] vу then begin jC=jC+1; {Обратное ребро (х, v), найден цикл} WriteCycle(v, С, nС); {Печать цикла} end; nC=nC-1; {Удалить исследованную вершину из стека} end; end; Procedure WriteСуcle(x, С, nС) print jC; {Печать номера цикла} repeat print C[nC]; {Печать вершины из стека} пС=пС-1; until C[nC]=x; end.

Похожие:

	Отчет о научно-исследовательской работе по Государственному контракту... Этап второй: «Выбор направлений исследований и этап предварительных исследований по мембранным коллоидным системам»		Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 на выполнение поисковых научно-исследовательских работ для государственных...
	Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 на выполнение поисковых научно-исследовательских работ для государственных...		Список основных исполнителей по Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 Государственному контракту 14. 740. 11. 1258 от 17 июня 2011 на выполнение поисковых научно-исследовательских работ для государственных...
	Отчет по государственному контракту от 04. 06. 2012 №1102-01-41/06-12... ...		Отчет о научно-исследовательской работе по государственному контракту... Русский язык и культура речи: учебно-методический комплекс для студентов очной формы обучения / сост. И. А. Крым; Кузбасский институт...
	Отчет о научно-исследовательской работе Гост 32-2001. Межгосударственный стандарт. Система стандартов по информации, библиотечному и издательскому делу. Отчет о научно-исследовательской...		Отчет о научно-исследовательской работе Межгосударственный стандарт (гост 32-2001). Отчет о научно-исследовательской работе. Структура и правила оформления (редакция 2005...
	Общие положения отчет Отчет о научно-исследовательской работе (нир) документ, который содержит систематизированные данные о научно-исследовательской работе,...		Отчет по Государственному контракту № «Разработка концепции создания интеллектуальной транспортной системы на автомобильных дорогах федерального значения»
	Реферат Отчет о научно-исследовательской работе состоит Отчет о научно-исследовательской работе состоит из 33 рисунков, 8 разделов, 12 подразделов, 9 формул, 31 источника. Общий объем 48...		Разработка и применение инновационных молекулярно-генетических тестов... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Отчет по Дополнительному соглашению №2 к Государственному контракту... «Разработка проекта скиово бассейна реки Нарва и рек бассейна Псковско-Чудского озера» (С-10-01)		Отчет о научно-исследовательской работе по теме: «Разработка научно... «Институт законодательства и сравнительного правоведения при Правительстве Российской Федерации» (ИЗиСП)
	Отчет о научно-исследовательской работе «Разработка моделей и образцов... «Разработка моделей бакалавра по специальности и магистра по специальности. Реализация моделей по группам специальностей»		Отчет о научно-исследовательской работе в рамках федеральной целевой... «Разработка новых методов индивидуальной коррекции сводно-радикального статуса при бактериальных инфекциях»