Размещено на http://www.allbest.ru/

Алгоритм редукции графов для расчета динамики генных сетей в рамках синхронной булевой модели

Оглавление

• Тезаурус
• Введение
• 1. Описание предметной области
• 2. Постановка задачи
• 3. Алгоритмы поточечной редукции
• 3.1 Редукция вершин-источников
• 3.2 Редукция вершин-стоков
• 3.3 Редукция проводящих вершин
• 3.4 Описание работы программного средства
• 4. Существующие методы декомпозиции
• 4.1 Алгоритм "walktrap" на основе случайных блужданий
• 4.2 Алгоритм на основе определения смежности
• 4.3 Алгоритм "жадной" оптимизации модульности
• 5. Реализация декомпозиции
• 5.1 Актуальность разбиений
• 5.2 Разработка программного средства
• 6. Применение методов
• 7. Подведение итогов
• Литература

Тезаурус

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

Состояние ГС - совокупность состояний всех вершин образующих ГС. В рамках рассматриваемой модели состояние ГС представимо в виде n-мерного булева вектора, где n - размерность сети.

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

Модуль - подсеть исходной сети, подграф. О свойствах модулей речь пойдет ниже.

Модульность - характеристика графа, отражающая его пригодность для разбиения.

Сигнал - влияние, которое один элемент ГС оказывает на другой. При представлении ГС в виде графа эквивалентен дуге.

Многие другие понятия будут определены и пояснены по ходу повествования.

Введение

Тема моей работы: "Алгоритм редукции графов для расчета динамики генных сетей в рамках синхронной булевой модели"

Исследование генных сетей особенно актуально в так называемую постгеномную эпоху, основной задачей которой является интерпретация информации, полученной при расшифровке геномов, выяснение механизмов функционирования генов. Для этого необходимо исследовать не только отдельные гены, но и их взаимодействие, вместе с необходимыми белками. Моделью такой взаимодействующей группы генов и белков как раз и является генная сеть. Концепция ГС позволяет учесть иерархию строения организма: локальные ГС более низкого уровня, решая свои частные задачи, объединяются в сети более высокого уровня. ГС обмениваются друг с другом сигналами.

Рис.1 Пример генной сети: ГС роста лапки дрозофилы

Исследование ГС может помочь в решении следующих задач:

· Понимание механизмов работы организма

· Моделирование различных систем и организма в целом

· Способ дешевой проверки воздействия веществ (лекарств) и других факторов на биосистему

· Изучение влияния мутаций на ГС. Распознавание типа мутации по поведению ГС.

· Конструирование искусственных ГС (трансгенные технологии)

· Обратный инжиниринг (нахождение начальных условий, для получения желаемого результата)

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

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

1. Описание предметной области

Имеется ориентированный n-граф следующего типа:

* вершины принимают значения 0 или 1.

* Дуги (сигналы) двух типов: "+" и "-".

* Если на входе дуги (сигнала) 1, то "сигнал" идет (активен), иначе "сигнал" не идет (неактивен).

В данном графе вершины взаимодействуют друг с другом по следующим правилам:

* Для каждой вершины рассматриваем только входящие дуги.

* Рассматриваем дуги у которых на входе 1.

* Если есть активный сигнал типа "-", то на выходе получаем 0.

* Если нет активных сигналов типа "-" и есть активный сигнал типа "+" то на выходе получаем 1.

* Если нет ни одного активного сигнала любого типа, то выходное значение не меняется.

Формально это можно описать так:

1) Задаем некоторую нумерацию вершин графа от 1 до N.

2) Отождествляем i-ую вершину графа с i-ой компонентой n-мерного булевого вектора V.

Далее формальное описание взаимодействия можно дать двумя способами:

a) n - длина вектора. G - граф. Его можно рассматривать как преобразование некоторого вектора длины N, в вектор длины N, представим его матрицей E размерности N x N, где E[i,j] {-1,0,1} - дуга из вершины i в вершину j, i,j=0..N-1. (i - номер строки, j - номер столбца.) Предполагаем, что в графе нет изолированных вершин (так как они никак не влияют на преобразования). Пусть вектор V длины N задан, тогда можно записать преобразование следующим образом: G(V). Пусть a = (i,j) - дуга из i-той вершины в j-тую. Будем записывать E[a] - это тип данной дуги. Если дуга имеет тип "+", то E[a] = 1; Если дуга имеет тип "-", то E[a] = -1; Если дуги нет, то E[a] = 0;

Зафиксируем вершину в векторе V с номером j.

* Рассматриваем только входящие дуги, то есть все дуги a = (i,j),

i [0..N-1], для которых E[a]= 0

* Пусть a = (i,j) - дуга. Рассматриваем только те дуги, для которых

V[i] = 1.

* Пусть A = {a = (i,j)}, i [0..N-1] список всех дуг, удовлетворяющий первым двум свойствам, тогда если a A такой, что E[a]= -1, то G(V)[j] =0.

* Если a A верно, что E[a] = 1, то G(V)[j] = 1.

* Если два предыдущих условия не выполнились, то G(V)[j] = V[j]

b) G(V[i])=

Это преобразование мы применяем ко всему пространству n-мерных булевых векторов.

Требуется:

Найти все неподвижные точки, то есть вектора, которые не изменяются после любого количества взаимодействий.

Найти все циклы, то есть вектора, которые после определенного количества взаимодействий снова становятся прежними.

Найти все центры притяжения, то есть вектора, которые после определенного количества взаимодействий приходят в циклы, но не принадлежат циклам.

2. Постановка задачи

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

Основными требованиями к алгоритмам стали:

1) Снижение временных и машинных затрат при расчете динамики генных сетей.

2) Применимость алгоритмов для как можно более широкого спектра генных сетей.

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

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

5) Возможность анализа полученных результатов для различных целей.

6) Возможность выборочного восстановления результатов до исходных размерностей генной сети.

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

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

Декомпозиция представляет собой разделение графа на модули для последующего их последовательного разрешения.

3. Алгоритмы поточечной редукции

Генные сети изобилуют вершинами, расчет которых необязателен в рамках всей сети. В силу своей особенной организации в цикл они могут входить только статично (то есть не меняя значения), а значит, ее состояние можно восстановить по значениям связанных с ней вершин, а саму ее не рассчитывать. Наиболее актуальными объектами для поточечной редукции стали три типа вершин: источники, стоки и проводящие вершины.

3.1 Редукция вершин-источников

А является вершиной-источником, если:

1) Не существует дуг ведущих в А.

2) Не существует отрицательных дуг из А.

3) Любая вершина В, такая что А->В, не имеет отрицательных входящих дуг.

Рис. 2 Пример вершины-источника.

генный редукция декомпозиция алгоритм

Зависимость состояния А от состояния {B} можно выразить в виде теоремы:

Если A - источник, A -> {B} и в {B} не входят "-" сигналы, тогда A ? 1 или 0, если все B[i,j] = 1, i=1..p (p - количество дуг из А),

j=1..q (q - длина цикла),

иначе A ? 0.

Доказательство: нулевое значение вершина А может принимать при любых комбинациях значений вершин В (при этом она просто не будет на них влиять), а учитывая статичность вершины А и отсутствие входящих отрицательных дуг в В, очевидно что при единичном значении, вершина А на каждой итерации цикла должна присваивать всем вершинам В значение "1". Таким образом А=1 все B[i,j] = 1.

3.2 Редукция вершин-стоков

Z является вершиной-стоком если:

1) Не существует дуг, ведущих из Z.

2) Все дуги, ведущие в Z, одного знака.

Рис. 3 Пример вершин-стоков.

Зависимость состояния вершины Z от значений вершин множества {A} также представимо в виде теоремы:

Пусть Z - сток и {A} -> Z, тогда

Z ? 1, если существует A[i,j] = 1, i=1..p (p - количество дуг в Z),

j=1..q (q - длина цикла) ,

иначе Z ? 0 или 1.

Доказательство: в силу того, что вершина Z не влияет ни на какие другие вершины и отсутствуют отрицательные входящие в Z дуги, единичное значение она может принимать при любых комбинациях состояний вершин множества {A}. Основанием для присвоения вершине Z нулевого значения может быть только отсутствие среди вершин {A} единичных значений на любой итерации цикла, так как в противном случае вершина Z должны была бы принять значение "1".

3.3 Редукция проводящих вершин

В является проводящей вершиной если:

1) В нее входит только одна положительная дуга (А->B).

2) Из нее выходит только одна положительная дуга (B->C).

3) В А,В и С нет входящих отрицательных дуг.

Рис. 4 пример проводящей вершины.

Для редукции проводящей вершины В применима следующая теорема:

Пусть B - проводящая вершина и A -> B -> C, в А, В и С нет входящих "-" сигналов, тогда

1) A -> B -> C можно упростить до вида A -> C и

2) если (А,С) = (1,1), то В ? 1;

если (А,С) = (0,0), то В ? 0;

если (А,С) = (0,1), то В ? 0 или 1.

Доказательство: в силу статичности всех трех вершин теорема может быть доказана прямым перебором всех возможных состояний вершин А и С. Очевидно, что (А,С) не может принимать значение (1,0) в теле цикла, так как при последующем преобразовании оно перейдет в состояние (1,1). Каждому из трех оставшихся состояний для (А,С) соответствует определенное значение вершины В: то есть между единицами и нулями может стоять только единица или ноль соответственно, а для (А,С) = (0,1), В принимает любое постоянное значение.

3.4 Описание работы программного средства

Для разработки программы был выбран язык С++, среда разработки Microsoft Visual Studio 2008. Для визуализации графов послужила программа GraphViz 2.26.3

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

0 - вершина не редуцируема;

1 - вершина редуцируема как источник +;

2 - вершина редуцируема как сток + ;

3 - вершина нередуцируема как источник - ;

4 - вершина редуцируема как сток - ;

5 - вершина редуцируема как проводящая.

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

Принцип работы программы представим в виде блок-схемы:



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

Пусть генная сеть имеет вид:

И задается таким входным файлом:

После анализа вершины 3, 4 ,5, 7, 8, 9 были помечены индексом "0" как нередуцируемые, а вершинам 1, 2, 10, 6 были назначены метки 2, 4, 1 и 5 соответственно, согласно применимых для них типов поточечной редукции.

Таким образом на выходе были получены:

Новая сеть: Редукция: Ассоциации:

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

Частным решением такой сети является, например, цикл "101110". После восстановления этого результата до исходной размерности, становится понятно, что он порождает четыре различных решения:

1110111100

1110111101

1010111100

1010111101

Результаты применения метода "редукция-вычисление-восстановление" совпадают с решением без применения редукции.

4. Существующие методы декомпозиции

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

1) Выделенный алгоритмом модуль должен был иметь только выходящие дуги вовне.

2) Алгоритм должен был предоставлять различные варианты разбиения, чтобы было возможно выделить модуль подходящего размера.

3) Сложность алгоритма не должна быть велика.

4) Алгоритм должен уметь обозначить граф как неделимый.

4.1 Алгоритм "walktrap" на основе случайных блужданий

Подход основан на следующем: случайные блуждания по графу имеют тенденцию "попадать в ловушку" в тесно связанные части, соответствующие сообществам. Поэтому мы начинаем с некоторых свойств случайных блужданий по графам. Используя их, мы определяем измерение структурного подобия между вершинами и между сообществами, таким образом определяя расстояние. Мы связываем это расстояние с существующими спектральными подходами проблемы. Но наше расстояние имеет важное преимущество на этих методах: оно эффективно вычислимо, и может использоваться в иерархическом алгоритме объединения в кластеры (постепенно сливающиеся вершины в сообщества). Каждый получает этот путь иерархической структурой сообщества, которая может быть представлена как дерево, названное древовидной диаграммой. Мы используем такой алгоритм, названный Walktrap, который вычисляет структуру сообщества вовремя O(mnH), где H - высота соответствующей древовидной диаграммы. В худшем случае - O (mn²). Но большинство сложных сетей реального мира редки (m = O (n)) и, как уже замечено, H является вообще маленьким и имеет тенденцию к самому благоприятному случаю, в котором уравновешена древовидная диаграмма (H =O(log n)). В этом случае, сложность - O (n²log n). Наконец мы оцениваем работу нашего алгоритма с различными экспериментами, которые показывают, что этот алгоритм превосходит предварительно предложенные алгоритмы в большинстве случаев.

Временная сложность: O(|E||V|²) в худшем случае, O(|V|²log|V|) типично, |V| - количество вершин, |E| - количество ребер.

Рис. 5 Пример разбиения данным алгоритмом.

4.2 Алгоритм на основе определения смежности

Перевод названия этого метода с английского языка на русский: "Определение сообществ, основанное на смежности ребер".

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

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

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

Алгоритм, который мы предлагаем для того, чтобы идентифицировать сообщества, описывается так:

1. Вычислить смежность для всех ребер в сети.

2. Удалить ребро с самой высокой смежностью.

3. Повторно вычислить смежность для всех ребер, затронутых удалением.

4. Повторять от шага 2, пока не останется никаких ребер.

Временная сложность: O(|E|+|V|log|V|), |V| - количество вершин, |E| - количество ребер.

Тестовый граф разбивается точно так же, как и первым алгоритмом.

4.3 Алгоритм "жадной" оптимизации модульности

Предположим, что наша сеть состоит из вершин. Для частичного деления нашей сети на две группы будем считать , если вершина принадлежит группе 1 и , если она принадлежит группе 2. Также пусть количество ребер между вершинами и будет равно , которое в свою очередь должно быть 0 или 1, хотя большие числа возможны в сетях с несколькими ребрами. (Значения являются элементами, так называемой матрицей смежности.) В тоже время, ожидаемое количество ребер между вершинами и , если ребра размещены случайным образом равно , где и - степени вершин, а - это общее количество ребер в сети. Таким образом, модульность представляется в виде суммы через все пары вершин и , которые находятся в одной группе. Выходит, что выражение равно 1, если и расположены в одной группе, и 0 в остальных случаях. Мы можем выразить модульность так:

,

Где второе равенство следует из следующего: . Значение включено в равенство для совместимости с определением модульности.

Модульность может быть записана в матричной форме:

,

где - вектор колонки, чьи элементы являются и мы определили симметричную матрицу с элементами

,

которую называем матрицей модульности. Сразу же заметим, что сумма элементов для каждых строки и столбца равно нулю, поэтому эта матрица всегда имеет собственный вектор (1,1,1,…) с собственным значением равным нулю. Это замечание представляет собой матрицу, известную как граф Лаплация, который является основой для одного из самых известных методов дробления графа, спектрального дробления, и имеет те же свойства. Методы, представленные здесь, имеют некоторые значительные отличия, далее мы это увидим.

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

,

где - собственное число соответствующее собственному вектору .

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

К сожалению, существует ограничение элементов к значениям , которые означают, что не может быть выбрано обычно параллельно . Мы должны сделать эти значения близко параллельными, насколько это возможно, что эквивалентно максимизации скалярного произведения . Несложно заметить, что максимум достигается при , если соответствующий элемент положителен, а при в остальных случаях. Другими словами все вершины, чьи соответствующие элементы положительны, попадают в одну группу, а все остальные попадают в другую группу. Это и дает нам алгоритм деления сети: мы рассчитываем лидирующий собственный вектор матрицы модульности и делим вершины на две группы в зависимости от знаков элементов этого вектора.

Сразу видны некоторые положительные возможности этого метода. Первое, чтобы было понятно, этот метод работает даже если размеры сообществ не указаны. В отличии от обычных методов дробления, которые уменьшают количество ребер между группами, не нужно больше ограничивать размеры групп или специально запрещать - тривиальное решение со всеми вершинами в одиночное группе. Существует собственный вектор (1,1,1,…), отвечающий этому простому решению, но его собственное число равно нулю. Все остальные собственные вектора ортогональны этому и следовательно должно обладать обеими, положительными и отрицательными, элементами. Таким образом, до тех пор, пока есть любое положительное собственное значение, этот метод не будет определять все вершины в одну группу.

Однако, может и вовсе не быть положительных собственных значений в матрице модульности. В этом случае лидирующий собственный вектор является вектор (1,1,1,…), соответствующий всем вершинам в одиночной группе вместе. Но это абсолютно точный результат: в этом случае нет деления сети, что выражается в положительном значении модульности, что можно заметить из уравнения. Модульность неделенной сети равна нулю, является наилучшим достижимым значением. Это очень важная часть алгоритма. Алгоритм имеет возможность не только эффективно делить сеть, но и отказываться от ее деления, когда нет хорошего деления. Сеть в таком случае называется неделимой, т.е. если матрица модульности не содержит положительных собственных значении. Эта идея сыграет решающую роль в дальнейших разработках.

Временная сложность: O(|E||V|log|V|) в худшем случае, O(|E|+|V|log^2|V|) типично, |V| - количество вершин, |E| - количество ребер.

Рис.6 Пример разбиения орграфа данным методом.

5. Реализация декомпозиции

Из всех представленных методов только алгоритм жадной оптимизации модульности отвечал всем предъявленным требованиям. За вполне приемлемое время этот алгоритм в состоянии предоставить на выбор несколько разбиений или обозначить граф как неделимый. Именно алгоритм жадной оптимизации модульности был взят за основу дальнейших разбиений генных сетей. Нужно заметить, что полученное разбиение далеко не всегда окажется подходящим для дальнейшего расчета динамики. Помимо проверки направлений дуг из модуля в модуль, и проверки размерности стартового модуля, необходимо признать это разбиение эффективным. Дело в том, что при расчете следующего модуля к нему присоединяются также все вершины предыдущего, которые на него влияют, только значения в них изменяются согласно циклам рассчитанным ранее. Такой подход позволяет избежать потери циклов при декомпозиции. Иными словами, чем больше разница размера стартового модуля и количества вершин влияющих на следующий модуль, тем выше эффективность разбиения, тем сильнее облегчается граф. Основная проблема выбора самого эффективного разбиения заключалась в том, что подходящий с одной точки зрения вариант оказывался не очень хорош с другой стороны. Решением этой проблемы стала возможность вывода нескольких удовлетворяющих условиям вариантов.

5.1 Актуальность разбиений

Чтобы показать целесообразность применения декомпозиции, вручную была создана сеть из 25 вершин, имеющая очевидные сильно-связные области.



Рис. 7 Тестовая сеть из 25 вершин.

Таб. 1 Сравнительные затраты ресурсов при различных разбиениях.

Были рассчитаны сложности вычислений для неразбитой сети, для сети разбитой на 3 и 5 модулей. Результаты всех расчетов совпали, а временные и машинные затраты для каждого случая представлены в таблице:

Из таблицы хорошо видно, что применение декомпозиции с разбиением на 5 модулей позволяет сократить временные затраты более чем в 200 раз, а затраты памяти более чем 400 раз.

5.2 Разработка программного средства

Для реализации декомпозиции графа были выбраны те же инструменты, что и для редукции. А именно язык С++ среды Microsoft Visual Studio 2008 для написания программного средства и GraphViz 2.26.3 для визуализации полученных результатов.

Входные данные для полученного программного средства предоставляет текстовый файл, записанный в уже знакомом нам формате:

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

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

Стартовый модуль определяется как подграф, в который нет внешних вхождений.

Стартовый модуль не должен превышать размерности 27, это максимальное количество вершин, которое возможно рассчитать на домашнем компьютере.

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

Работа программы схематично представлена ниже:

Из схемы видно, что сам граф не претерпевает никаких изменений. Непосредственным результатом выполнения программы является файл mask. Для представленного случая он имеет вид:

В нем содержится информация о полученных модулях: размер и номера вершин соответственно.

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

6. Применение методов

Для апробации комбинированного подхода к редукции генных сетей было принято решение применить комбинацию поточечной редукции и декомпозиции для исследования генной сети стрессового ответа кишечной палочки (e.coli).

Рис. 8 Генная сеть реакции на стресс e.coli.

После построения синхронной булевой модели по этой сети был получен граф из 73 вершин. Понятно, что количество состояний такой сети равняется 2⁷³ ? 10²¹



Рис. 9 орграф, представляющий упомянутую генную сеть.

Результатом применения алгоритмов поточечной редукции к этой сети стал граф, в котором осталось всего 46 вершин, то есть от 27 вершин удалось избавиться уже на первом этапе.

Рис. 10 Граф, полученный после применения поточечной редукции.

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

Рис. 11 Выделение первого модуля.

Он содержит всего 18 вершин и рассчитывается за t<20 секунд. Было выявлено 228 циклов длины 1.

В следующий этап переходит информация о поведении только 35, 49, 52 и 68 вершин и граф принимает следующий вид:

Рис. 12 Результаты редукции первого модуля.

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

Рис. 13 Выделение второго модуля.

В нем 12 вершин и его расчет занимает ~760 секунд. Такое время обусловлено как раз тем, что на предыдущем модуле было выявлено 228 циклов. На этом этапе было найдено уже 3802 цикла. Все также длины 1.

Исследуемый граф принял такой вид:

Рис. 14 Результаты редукции второго модуля.

Эффективное разбиение такого графа оказалось невозможным, поэтому к нему была применена очередная поточечная редукция:



Рис. 15 Последний рассчитываемый модуль - результат поточечной редукции.

Это и есть последний рассчитываемый модуль. В нем 10 вершин и результаты были получены через ~460 секунд и было найдено 134582 цикла длины 1.

Последние строки консоли:

--- running search for cycle #3799

--- running search for cycle #3800

--- running search for cycle #3801

17:19:39 # next module done...

cycles found: 134582

.. where length > 1: 0

17:19:42 # done!

17:19:42 # writing results...

17:19:42 # done!

cycles count: 134582

N: 46

Выходной файл имел размер порядка 20 Мб и состоял из строк вида:

56579:

***010**00001000*10*0*00010000*11000111000**11

То есть номер цикла и непосредственно сам цикл. Звездами помечены вершины редуцированные на последнем этапе.

Любое такое решение можно расширить до исходной размерности N=73 и получить искомый цикл.

Пример:

1111000010000000000100001111101011011000100011110000100010100001010000011

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

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

Рис. 16 Последний модуль в альтернативном представлении.

7. Подведение итогов

В ходе проведенной работы были осуществлены следующие действия:

1) Подготовлен обзор предметной области.

2) Разработаны алгоритмы поточечной редукции графа, доказана корректность этих алгоритмов.

3) Рассмотрены различные алгоритмы декомпозиции графов.

4) Усовершенствован алгоритм жадной оптимизации модульности для возможности его применения в рамках исследования динамики генных сетей.

5) Разработаны программные средства, реализующие эти алгоритмы.

6) Проведено тестирование программных средств как на искусственно сгенерированных сетях, так и на реально существующих.

7) Получены результаты динамики генной сети стресс-ответа кишечной палочки.

8) Сформулированы перспективы развития в этой области.

Алгоритмы, представленные в этой работе, полностью соответствуют всем поставленным задачам:

1) Временные и машинные затраты при расчете динамики генных сетей удалось сократить в несколько раз.

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

3) На каждом этапе редукции есть возможность выбора алгоритма, наиболее применимого в данный момент.

4) Результаты расчета динамики генных сетей представляются компактно. Даже результаты расчета сетей больших размерностей занимают приемлемый объем.

5) Результаты, полученные в ходе расчетов, могут быть легко использованы для различных исследований, имеющих прикладной смысл.

6) Любой из полученных результатов с легкостью может быть восстановлен до исходных размерностей генной сети.

Результаты этой работы были представлены на XLIX Международной Научной Студенческой Конференции в рамках подсекции биоинформатика.

К перспективам использования исследованных методов можно отнести:

1) Применение параллельных вычислений на тех или иных этапах редукции или расчета для ускорения работы комплекса в целом.

2) Интеграция представленных методов в имеющиеся инструменты по исследованию генных сетей.

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

4) Расширение спектра задач, решаемых алгоритмом, на другие проблемы, представимые в рамках синхронной булевой модели.

5) Разработка новых алгоритмов поточечной редукции для других характерных формаций участков генных сетей.

Литература

· www.graphviz.org - инструмент для визуализации графов

· www.igraph.sourceforge.net - библиотека для работы с графами

· http://www.boost.org - библиотека для работы с графами на языке C++

· Харари Ф. - Теория графов. М.: Мир, 1973.

· Оре О. - Теория графов. М.: Наука, 1968.

· Кормен Т. - Часть VI. Алгоритмы для работы с графами.

· Материалы XLIX МНСК - Биология. Новосибирск: НГУ 2011.

· Luiz Mendoza, Denis Thieffry, Elena R. Alvarez-Buylla. Genetic control of flower morphogenesis in Arabidopsis thaliana: logic analysis. Journal of Theoretical Biology, 1999

Размещено на Allbest.ru