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

Скачать 0.49 Mb.

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

100-bal.ru > Биология > Отчет

1 2 3 4 5 6 7 8 9 10 11

2.3Метод кластеризации узлов графа ассоциативных генных сетей

Структурным модулем или кластером ассоциативной генной сети называется подграф ассоциативной генной сети, обладающий следующими свойствами:

элементы подграфа сильно связаны между собой и слабо связаны с элементами ассоциативной генной сети не входящими в данный подграф;
подграф ассоциативной генной сети выполняет биологически интерпретируемую функцию в рамках функционирования молекулярно-генетической системы, описываемой ассоциативной генной сетью.

В отличие от структурных путей структурные модули имеют большую размерность и более сложную структуру. В связи с этим, для выявления структурных модулей используются принципиально другие алгоритмы, чем для выявления структурных путей.

Существующие методы кластеризации можно разделить на иерархические и разделяющие. Иерархические методы предоставляют структурную информацию, такую как дендрограммы, но применимы только для небольших наборов данных. С увеличением размеров вычислительные затраты растут вследствие необходимости считать матрицу близости, когда каждый сравнивается с каждым. Разделяющие методы несколько менее требовательны к ресурсам. К таким методам относятся метод К-средних, самоорганизующиеся карты Кохонена, спектральный анализ графов.

В рамках настоящего проекта был разработан метод кластерного анализа ассоциативных генных сетей, основанный на анализе спектра матрицы Лапласа для графа ассоциативной генной сети, поскольку он не требует знания количества кластеров, которое определяется из структуры графа.

Изначально спектральный анализ графов применялся в электротехнике, коммуникационных и компьютерных сетях. Спектральный анализ использовался для нахождения минимальных путей (в смысле их длины и стоимости), распределения «центров», покрывающих заданную область (задачи размещения телевизионных или радиопередающих станций, предприятий, центров торговли и т.п.) и задач классификации (отнесение определенного объекта к одному из нескольких попарно не пересекающихся множеств). Алгоритм спектрального анализа предназначен для работы с взвешенным планарным неориентированным графом связности. Кластеризация сводится к поиску собственных значений матрицы Лапласа.

Коротко алгоритм может быть описан следующим образом. На первом шаге ассоциативная генная сеть преобразуется во взвешенный планарный неориентированный граф. Все объекты в сети задаются как вершины одного типа. Все связи в сети также задаются как связь одного типа. Тип связи и типы объектов учитываются при определении веса для связи между вершинами. Вес связи является входным параметром метода и задается пользователем. По умолчанию веса для всех типов связей являются одинаковыми. Для преобразованного графа ассоциативной генной сети строится матрица смежности А и матрица степеней D. По ним вычисляется матрица Лапласа L. Для каждой вершины графа по матрице Лапласа степенным методом и методом Якоби ищутся собственные значения и соответствующие им собственные векторы. Собственный вектор, соответствующий наименьшему собственному значению дает вырожденное (нулевое) решение. Второе по величине наименьшее собственное значение и соответствующий ему собственный вектор дают желаемую информацию о кластеризации (K.V. Brinda, N. Kannan. Journal of teoretica and computational chemistry. Protein structure: insights from graph theory. V 1, No. 1, 2002). Все вершины, имеющие одинаковые компоненты в этом векторе, объединяются в кластер.

Пусть задан граф связности

. Две вершины

считаются связанными ребром

, если существует связь заданного уровня в ассоциативной сети. Связью первого уровня считаются все непосредственные связи между объектами, связь второго уровня определяется в том случае если два объекта связаны через одного общего посредника, связь третьего уровня через двух посредников и т.д. Таким образом, имеем для ассоциативной генной сети взвешенный неориентированный планарный граф связности, характеризующийся симметричной

матрицей инцидентности (смежности)

где

;

– уровень связи или наикротчайшее расстояния между

объектами сети.

В простейшем случае рассматриваются связи только первого уровня, так что α_ij= 0 либо 1.

Далее по матрице

строится матрица степеней D:

(1)
Матрица Лапласа

имеет вид

и обладает следующими свойствами:

, то есть, является симметрической и положительно определенной

Минимальное собственное значение матрицы равно нулю и достигается на векторе

, где

размерность матрицы

Для получения информации о кластерах требуется найти такой вектор

, который минимизирует взвешенную сумму

квадратов расстояний между точками (причем тривиальное решение

не учитывается).

(2)
где

– количество вершин в графе

При условии

,

где штрихи означают транспонирование

Равенство (2) можно переписать в терминах матрицы Лапласа:

(3)
Действительно,

Учитывая (1), имеем

Таким образом (3) доказано.

Методом неопределенных множителей Лагранжа с условиями ограниченности (2) ищем

– многочлен Лагранжа
Получаем систему

Таким образом, задача минимизации

сводится к поиску собственных значений матрицы

.

Для поиска второго по минимальности собственного значения и соответствующего ему собственного вектора используются два алгоритма: метод Якоби и степенной метод. Метод Якоби использовался, в основном, для тестирования программы в течение ее разработки. Этот метод поиска спектра всегда применим для действительных, симметричных матриц. Алгоритм Якоби значительно проще других, более эффективных методов, но для матриц порядка больше 10 он более медленный. Таким образом, его удобно было использовать для небольших тестовых расчетов, когда время выполнения не являлось критическим. С другой стороны метод Якоби позволяет выявить ситуацию с кратными собственными значениями матрицы и исследовать зависимость результата от выбора одного или другого собственного вектора соответствующего данному собственному значению. (Как показали исследования, кратность второго по минимальности собственного значения на результат не влияет.) Степенной метод, как правило, используется для поиска максимального собственного значения симметричной, положительно определенной матрицы. Применяя ортогонализацию метода можно последовательно получить все собственные значения матрицы.

На рисунке 2.2 представлены результаты поиска кластеров на примере искусственной сети.

Рис. 2.2. Пример кластеризации в графе искусственной сети. Объекты, входящие в разные кластеры выделены разным цветом.

1 2 3 4 5 6 7 8 9 10 11

Похожие:

	Отчет о научно-исследовательской работе по Государственному контракту... Этап второй: «Выбор направлений исследований и этап предварительных исследований по мембранным коллоидным системам»		Список основных исполнителей по Государственному контракту 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)		Отчет о научно-исследовательской работе по теме: «Разработка научно... «Институт законодательства и сравнительного правоведения при Правительстве Российской Федерации» (ИЗиСП)
	Отчет о научно-исследовательской работе «Разработка моделей и образцов... «Разработка моделей бакалавра по специальности и магистра по специальности. Реализация моделей по группам специальностей»		Отчет о научно-исследовательской работе в рамках федеральной целевой... «Разработка новых методов индивидуальной коррекции сводно-радикального статуса при бактериальных инфекциях»

Школьные материалы