Дипломная работа
Расчет динамики логических сетей на основе метода декомпозиции, адаптированного для графического процессора
Содержание
1. Введение
2. Предметная область
3. Постановка задачи
4. Алгоритм декомпозиции графов и расчеты динамики логических сетей
· 4.1 Алгоритм декомпозиции
· 4.1.1 Алгоритм «жадной» оптимизации модульности
· 4.2 Преобразование пространства булевых векторов
· 4.3 Анализ динамики
· 4.4 Алгоритм объединения
5. Программная реализация
· 5.1.Формат данных
· 5.2.Описание блоков программной реализации и их взаимодействие.
· 5.3 Тестирование
6. Заключение
7. Список литературы
1. Введение
Все происходящие в организме процессы (биохимические, физиологические и др.) осуществляются за счет координированной экспрессии различных групп генов. Каждая такая группа составляет основу конкретной генной сети, отвечающей за выполнение определенной функции клетки, органа, организма. Под генной сетью при этом понимается совокупность координировано экспрессирующихся генов, их белковых продуктов и взаимосвязей между ними. Важным моментом в функционировании генной сети является ее связь с внешней средой, в том числе и с другими генными сетями. Поэтому в любой генной сети имеются компоненты, обеспечивающие либо восприятие и передачу внешних сигналов, либо способность продуцировать такие сигналы.
В генной сети можно выделить несколько обязательных типов компонентов, таких как:
1). группы координировано экспрессирующихся генов (ядро сети);
2). белки, кодируемые этими генами (выполняющие как определенные структурные, транспортные, биохимические, так и регуляторные функции);
3). отрицательные и положительные обратные связи, стабилизирующие параметры генной сети на определенном уровне или, напротив, отклоняющие их от исходного значения;
4). низкомолекулярные соединения (метаболиты и др.) и различные внешние сигналы, обеспечивающие переключение состояний генной сети.
Все компоненты генной сети разделены на два основных типа: объекты и связи (взаимодействия) между ними. Объектами могут являться органы, ткани, клетки, клеточные компартменты, белки и белковые комплексы, гены, РНК, небелковые регуляторные вещества и продукты метаболизма.
Исследование генных сетей (ГС) особенно актуально в так называемую постгеномную эпоху, основной задачей которой является интерпретация информации, полученной при расшифровке геномов, выяснение механизмов функционирования генов. Для этого необходимо исследовать не только отдельные гены, но и их взаимодействие, вместе с необходимыми белками. Моделью такой взаимодействующей группы генов и белков как раз и является генная сеть. Концепция ГС позволяет учесть иерархию строения организма: локальные ГС более низкого уровня, решая свои частные задачи, объединяются в сети более высокого уровня. ГС обмениваются друг с другом сигналами.
Рис.1. Пример генной сети: ГС роста лапки дрозофилы
Исследование ГС может помочь в решении следующих задач:
Понимание механизмов работы организма.
Моделирование различных систем и организма в целом.
Способ дешевой проверки воздействия веществ (лекарств) и других факторов на биосистему.
Изучение влияния мутаций на ГС. Распознавание типа мутации по поведению ГС.
Конструирование искусственных ГС (трансгенные технологии).
Обратный инжиниринг (нахождение начальных условий, для получения желаемого результата).
Впервые булевы сети были предложены как модель генетической регуляции систем Стюартом Кауффманом в 1969, основанная на том факте, что гены путем экспрессии протеинов могут ингибировать или активировать экспрессию других генов. Значения в вершинах сети означают, активен данный элемент сети или нет. Синхронная булева генная сеть (то есть значения во всех вершинах меняются одновременно и принимают только одно из двух значений (0;1)). С ней можно связать преобразование, действующее на множестве булевых векторов (предварительно задав нумерацию на вершинах и отождествив i-ую вершину с i-ой компонентой вектора). Также это преобразование может быть использовано для описания не только генных сетей, но и описания процессов, протекающих в других типах сетей. Развитие булевой сети задает специальное преобразование.
Пусть V-пространство булевых векторов длины n, и задан ориентированный граф G, в вершинах которого заданы значения 0 или 1. Исходя из этого графа, мы можем построить преобразование F, отображающее V в V. Пусть в момент времени t0 начальные значения вершин сети задаются булевым вектором X(t0) и пусть в моменты времени t1,t2,…. Происходит преобразование по правилу:
X(tn+1)=F(X(tn)) n=0,1,…
Для обработки больших сетей мы будем использовать методы декомпозиции графа на подграфы, чтобы работать с пространствами меньшей размерности и затрачивать меньше времени при выполнении преобразования.
Работа направлена на использование вычислительных мощностей видеоадаптеров, которые зачастую не используются при расчетах, и вся нагрузка ложится на центральный процессор. Подход, изложенный в данном проекте, позволяет ускорить процесс обработки вычислений.
2. Предметная область
Имеется ориентированный n-граф следующего типа:
* Вершины принимают значения 0 или 1.
* Дуги двух типов: «+» и «-».
* Если начало дуги 1, то дуга активна, иначе неактивна.
В данном графе вершины взаимодействуют друг с другом по следующим правилам:
* Для каждой вершины рассматриваем только входящие активные дуги.
* Если нет ни одной входящей активной дуги любого типа, то значение в вершине не меняется
* Значение вершины присваивается значение 0, если существует, хоть одна входящая активная дуга типа «-».
* Иначе задаем значение 1
Формально это можно описать так:
Задаем некоторую нумерацию вершин графа от 1 до n.
Отождествляем i-ую вершину графа с i-ой компонентой n-мерного булевого вектора V.
G – граф. Его можно рассматривать как преобразование некоторого вектора длины n, в вектор длины n, представим его матрицей E размерности n x n, где E[i,j]? {-1,0,1} – дуга из вершины i в вершину j, i,j=0..n-1. (i – номер строки, j – номер столбца.) Предполагаем, что в графе нет изолированных вершин (так как они никак не влияют на преобразования). Пусть вектор V длины n задан, тогда можно записать преобразование следующим образом: F(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, то F(V)[j] =0.
* Если ?a ? A верно, что E[a] = 1, то F(V)[j] = 1.
* Если два предыдущих условия не выполнились, то F(V)[j] = V[j]
Это преобразование мы применяем ко всему пространству n-мерных булевых векторов.
Требуется:
Найти все неподвижные точки, то есть вектора, которые не изменяются после любого количества взаимодействий.
Найти все циклы, то есть вектора, которые после определенного количества взаимодействий снова становятся прежними.
Найти все области притяжения, то есть вектора, которые после определенного количества взаимодействий приходят в циклы, но не принадлежат циклам.
000->000 циклы: нет
001->011 неподвижные точки: 000,010, 011
010->010 области притяжения:
011->011 001,100,101,110,111
100->101
101->011
110->011
111->011
Рис.2 Пример
Рис.3
Конфигурационное пространство графа, изображенного на рис. 2
3. Постановка задачи
В рамках предметной области решено разработать программное средство, которое находит неподвижные точки, циклы и области притяжения на основе реализованных алгоритмов декомпозиции и преобразования графов. Процесс декомпозиции и преобразования необходимо автоматизировать. Это поможет сократить время расчета динамики графа, а также увеличить количество обрабатываемых вершин. Для решения поставленной задачи необходимо:
l Создать программу конвертер для конвертирования входного текстового файла в формат программ декомпозиции и преобразования.
l Модифицировать готовую библиотеку декомпозиции графов в консольный режим.
l Создать программу разбиения, которая на основе массива данных создает текстовые файлы и записывает в них подграфы со значением дуг.
l Создать программу перенумератор, которая будет задавать новую нумерацию каждому подграфу, считать количество вершин в новой нумерации и приводить текстовый файл в формат программы преобразования.
l Создать программу «слияния» динамик на основе алгоритма объединения.
l Автоматизировать вышеописанные программы при помощи команд MS-DOS и получить результат в виде текстового файла с динамикой исходного графа.
Данное программное средство реализовать в среде С++ т.к библиотека декомпозиции графов и программа преобразования пространства булевых векторов реализованы в этой среде.
алгоритм декомпозиция граф логический сеть
4. Алгоритм декомпозиции графов и расчеты динамики логических сетей.
4.1 Алгоритм декомпозиции
Для сокращения времени, затрачиваемого при преобразовании всего пространства булевых векторов, будем работать с пространствами меньшей размерности, чем у исходного. Для достижения данной цели, проведем декомпозицию исходного графа на непересекающиеся подграфы (рис.4).
Рис.4. Декомпозиция на подграфы (разбиение алгоритмом «жадной» оптимизации)
Но при таком подходе мы теряем взаимодействие между вершинами, расположенными в разных подграфах, поэтому для каждого полученного подграфа проделаем операцию присоединения дополнительных вершин. Опишем алгоритм выбора и добавления этих вершин.
Изначально все вершины истинные.
Для каждого подграфа из разбиения
Если ? ориентированное ребро (a,b) в исходном графе, где a не принадлежит подграфу, b?подграфу, то добавляем это ребро в данный подграф, вершину a в данном подграфе помечаем, что она добавленная.
Рис.5. Добавление вершин (добавленные вершины окрашены белым)
Добавленные вершины назовем виртуальными. Теперь вершины каждого подграфа взаимодействуют точно так же, как и в исходном графе (это не распространяется на виртуальные вершины), так как преобразование зависит только от входящих дуг. Но при неудачном разбиении мы рискуем получить большое количество виртуальных вершин (n*(n-1) в худшем случае). Поэтому будем декомпозировать на подграфы, ставя задачу минимизировать количество виртуальных вершин. Для этого будем находить сообщества в графах, и выделять их в качестве нашего разбиения с помощью специальных алгоритмов.
4.1.1 Алгоритм “жадной” оптимизации модульности
Данный алгоритм используется для декомпозиции исходного графа на подграфы. Суть алгоритма сводится к нахождению числа модульности. Подробнее об алгоритме можно прочитать по ссылке [1] в списке литературы.
Предположим, что сеть состоит из вершин. Для частичного деления сети на две группы будем считать , если вершина принадлежит группе 1 и , если она принадлежит группе 2. Также пусть количество ребер между вершинами и будет равно , которое в свою очередь должно быть 0 или 1, хотя большие числа возможны в сетях с несколькими ребрами. (Значения являются элементами, так называемой матрицей смежности) В то же время, ожидаемое количество ребер между вершинами и , если ребра размещены случайным образом равно , где и – степени вершин, а – это общее количество ребер в сети. Таким образом, модульность представляется в виде суммы через все пары вершин и , которые находятся в одной группе. Выходит, что выражение равно 1, если и расположены в одной группе, и 0 в остальных случаях. Можно выразить модульность так:
4.2 Преобразование пространства булевых векторов
После разбиения, каждый подграф (уже с добавленными виртуальными вершинами) тоже задает преобразование на пространстве булевых векторов. Применим каждое преобразование на соответствующее ему пространство булевых векторов. Логично представить наши булевы вектора целым числом, таким, что вектор является двоичным представлением этого числа. Тогда преобразованное пространство можно представить массивом, где на i-ом месте стоит dec(G(bin(i))). Где dec-десятичное представление числа, bin- двоичное.
Рис.8. Схема преобразования данных в программе
Данный алгоритм выполняется на графическом процессоре, сам алгоритм написан на шейдерном языке GLSL. На вход алгоритму поступает массив чисел с плавающей точкой.
Так как фрагментный шейдер выполняется для каждого выходного значения единожды и независимо, то выходные данные представлены в виде массива соответствующей размерности. Для каждого элемента в массиве данный алгоритм производит разбиение числа на биты, и к каждому биту уже применяется алгоритм нелинейного преобразования ровно так, как он описан в предыдущих пунктах. Для проведения преобразования использовалась библиотека gpucalc [2].
Замечание:
Значения в виртуальных вершинах не меняются при применении преобразования, так по построению нет входящих в них ребер.
4.3 Анализ динамики
Как уже описывалось во введении, значения в вершинах сети со временем меняются. Теперь опишем алгоритм нахождения циклов, неподвижных точек и областей притяжения, использовавшийся в проекте.
Алгоритм работает уже на преобразованном пространстве векторов, которое подается на вход как массив, описанный в предыдущем пункте. Разработан алгоритм, позволяющий за O(N2 ln(N)) действий в худшем случае (в произвольном случае за
O(N1+e ln(N)),0 < e< 1)
Задаем дополнительный массив, в котором для каждой точки будем хранить ее тип (принадлежность циклу или неподвижной точке – первый тип (положительные числа), принадлежность области притяжения-второй тип (отрицательные числа)). Изначально массив заполнен специальными значениями, который обозначают, что данная точка еще не была обработана (нулевые значения). Задаем множество посещенных вершин (с логарифмической скоростью поиска элемента), изначально оно пусто. Далее мы выбираем стартовую точку, которая не принадлежит множеству посещенных вершин. После этого мы начинаем применять наше преобразование к этой точке (на данном шаге мы имеем полностью преобразованное пространство векторов, поэтому вся суть преобразования сводится в нахождении значения, которое содержится в данной точке массива:
inew = m[iold])
Смотрим тип новой точки во вспомогательном массиве, если точка обработана, то помечаем всю цепочку типом, который имеет последняя точка (при этом во вспомогательный массив записываем положительное или отрицательное число равное по модулю стартовой точке) если новая точка не обработана, то переходим к предыдущему шагу.
4.4 Алгоритм объединения
Чтобы обобщить полученные данные с каждого подграфа на исходный граф, был предложен алгоритм:
Возьмем из пространства булевых векторов каждого подграфа по вектору. Заводим два вектора размерности n (размерность исходного графа). Если все значения виртуальных вершин равны значению соответствующих им не виртуальных вершин, то в первый вектор записываем значения не виртуальных вершин, а во второй на ту же позицию значения преобразования от данной вершины. Тогда второй вектор будет образом первого при преобразовании. Иначе переходим к следующей группе векторов.
Возьмем из пространства булевых векторов каждого подграфа по вектору.
Заводим Vector1 размерности n (исходная размерность)
Заводим Vector2 (той же размерности)
Для всех i (множество подграфов)
Для vector’а из i-ого подграфа
Для каждой j-ой компоненты этого вектора
Если (status(j,i)==main)
{
Vector1[iold[j]]=vector[j];
Vector2[iold[j]]=Gi(vector[j])
}
Для всех i
Для vector’а из i-ого подграфа
{
Для каждой j-ой компоненты этого вектора
Если (status(j,i)==fake)
{
Если (Vector1[iold[j]]!=vector[j])
Выход из блока;
null vector1;
null vector2;
}
}
G(Vector1)=Vector2;
// Gi-Преобразование i-ым подграфом
//iold[j]-нумерация j-ой вершины i-ого подграфа в исходном графе
//fake-виртуальная, main-не виртуальная
–
Разбиваем на подграфы: 1 и 2, 3 и 4
Добавляем виртуальные вершины
+ + Неподвижные точки: 0000, 0001,0100, 0101,
1000, 1001
–
000->000 001->001 010->010 011->010
– 100->110 101->101 110->110 111->110
+
– 000->000 001->001 010->010 011->010
100->101 101->101 110->111 111->101
+
Рис.9. Пример алгоритма объединения
Проведем «склейку» неподвижных точек:
4’2 1 2’3 4 4 3 2 1
0 0 0 и 0 0 0 = 0 0 0 0
0 0 0 и 0 1 0 = 0 1 0 0
0 0 1 и 0 0 0 = 0 0 0 1
0 0 1 и 0 0 1 = 0 1 0 1
0 1 0 и 1 0 1 = 0 1 1 0
1 0 1 и 0 1 0 = 1 0 0 1
Сравним с исходными и видим, что все неподвижные точки восстановлены. Проведенные эксперименты показали, что циклы также восстанавливаются.
5. Программная реализация
…………..
Рис.10. Блок-схема работы программы
Замечание: Синим цветом отмечены блоки реализованные для решения поставленной задачи
5.1 Формат данных
На вход программе поступает текстовый файл, который описывает ориентированный граф с значением дуг. Он записывается в виде трех столбцов. Первый столбец задает вершины из которых направлена дуга, второй столбец задает вершины в которые направлена дуга и третий столбец задает значение заряда дуги: +1 или -1. Таким образом получается ориентированный граф с значениями дуг, который записан в виде двумерного массива [nx3]. На выходе из программы мы имеем два файла. В первом файле хранится статистика, полученная применением программы преобразования без декомпозиции на подграфы. Во втором файле хранится статистика, полученная применением преобразования к декомпозированному графу.
5.2 Описание блоков программы и их взаимодействие
Ориентированный граф:
На вход программе поступает текстовый файл в таком формате в котором он описан в пункте 5.1.
Формат декомпозиции:
С помощью программы конвертера преобразовываем входной файл для программы декомпозиции графов. Для того, чтобы программа декомпозировала исходный граф, ей на вход нужно подать граф без значений дуг и в специальном формате, т.к они не влияют на разбиение. Формат выглядит следующим образом: в первой строке написано *Vertices n, где n количество вершин в графе, а во второй строке написано *Edges.
Формат преобразования:
Также пришлось конвертировать входной граф и для программы преобразования пространства булевых векторов. Программа декомпозиции ведет счет графа с первой вершины, а программа преобразования с нулевой.
На вход программе, автоматизирующей процесс декомпозиции, преобразования и слияния, поступает граф, в котором счет вершин начинается с единицы. Для программы преобразования приходится отнимать от каждой вершины единицу и делать табуляцию между столбцами, т.к именно с таким форматом работает программа, а в самой первой строке указать количество вершин в графе.
Таким образом на вход программе-конвертеру поступает ориентированный граф со значениями дуг, на выходе из программы получаем два текстовых файла: для программы декомпозиции и для программы преобразования в их поддерживаемом формате.
Разбиение на подграф :
Программа декомпозиции графов изначально была сделана в графическом интерфейсе. Для того, чтобы автоматизировать процесс декомпозиции, преобразования и слияния нам нужна консольная версия программы. Как выяснилось программа из исходных кодов не компилировалась, а графический интерфейс работал только с *exe файла. Для запуска программы необходимо было указать в поле EditBox путь к файлу в котором описан граф, а также указать в какой файл записать результат работы программы и нажать на кнопку «proceed». Запустить программу из командной строки, не имея работающего исходного кода практически невозможно. Для модификации программы в консольную версию пришлось изучить библиотеку igraph, которая декомпозирует граф алгоритмом «жадной» оптимизации. Затем была произведена модификация программы, а по сути собрана заново, но уже в консольную версию, входными параметрами которой стали: имя входного файла в котором описан граф и имя файла в который записывается результат работы программы. На выходе из программы получаем массив номеров подграфов, где на i-ом месте стоит номер подграфа, которому принадлежит i-ая вершина.
Создание текстовых файлов, добавление значений дуг:
Следующая программа на основе массива номеров, разбивает исходный граф на подграфы, затем заполняет подграфы виртуальными вершинами и добавляет значения дуг к каждой паре вершин, которые соответствуют исходному графу. Теперь мы имеем полноценную декомпозицию исходного графа на подграфы с значениями дуг и виртуальными вершинами.
Перенумерация вершин, формат преобразования:
Программа перенумерации подграфов производит в каждом подграфе подсчет количества вершин, перенумеровывает вершины со старой нумерации на новую, отнимает единицу от каждой вершины и делает табуляцию между столбцами. Таким образом после применения к каждому подграфу программ добавления дуг, виртуальных вершин и перенумерации мы получаем нужный формат для программы преобразования.
Применение преобразования, порожденного подграфом:
Имеем n текстовых файлов нужного формата, в каждом из которых содержится подграф. Далее применяем программу преобразования пространства булевых векторов к каждому подграфу.
Анализ динамики:
На выходе из программы преобразования получаем по три текстовых файла с каждого файла подграфа. В первом файле записывается время исполнения программы, во втором статистика, а в третьем количество неподвижных точек, циклов и областей притяжения. Для объединения результатов программы преобразования нам требуется файл статистики. В этом файле записаны в первой строке циклы, включающие в себя неподвижные точки, в виде целых чисел через запятую, и во второй строке области притяжения, так же через запятую и числами. В таком формате мы подаем файлы статистики в программу объединения результатов.
Объединение результатов:
Программа «слияния» результатов выполняет слияние статистик полученных после преобразования примененного к каждому подграфу, на основе алгоритма объединения. В итоге мы получаем один текстовый файл, в котором записана статистика, состоящая из циклов и областей притяжения. Теперь сравниваем результаты полученные применением программы преобразования на изначальный входной файл, в котором описан ориентированный граф, и результаты полученные методом декомпозиции. Файлы должны быть идентичны.
Автоматизация:
Все вышеописанные пункты автоматизированны в единый процесс при помощи команд MS-DOC и записаны в *bat файле. На вход программе подается текстовый файл, описанный в пункте 5.1 . На выходе получаем два текстовых файла формата описанного в пункте 5.1.
5.3 Тестирование
Программное средство тестировалось на разных серийных видеокартах Nvidia т.к программа преобразования работает на графических видеоадаптерах только этой фирмы серии не ниже 6600 с объемом памяти желательно хотя бы 128 Мб и свежей версией драйверов. Тест происходил на двух видеокартах. Первая видеокарта GT260 — последнего поколения с объемом памяти в 512Мб и предпоследней версией драйверов показала эффективность метода декомпозиции, уменьшив время обработки графа почти в 5,5 раз. Вторая видеокарта GF 7300 с объемом памяти 128Мб и не очень новой версией драйверов показала эффективность метода декомпозиции, уменьшив время обработки в 2,5 раза.
Таким образом эффективность метода декомпозиции доказана на практике.
Программы: конвертер, декомпозиции, разбиения, перенумерации и слияния тестировались на двадцати текстовых файлах на обычном компьютере без специальной видеокарты. Программы показали свою надежность и адекватную работоспособность при условии адекватного описания входного графа т.е вершины должны быть пронумерованы по порядку начиная с единицы и значения дуг только 1 или -1 иначе программное средство даст сбой.
6. Заключение
При выполнении дипломной работы были получены следующие результаты:
Разработана программа конвертер;
Модифицирована библиотека для декомпозиции графов в консольный режим;
Разработана программа разбиения;
Разработана программа перенумерации вершин;
Разработана программа «слияния» статистик на основе алгоритма объединения;
Выполнены расчеты на модельных и реальных логических сетях. Анализ результатов расчетов показал эффективность метода декомпозиции для расчета динамики логических сетей при разбиении на большое количество подграфов;
Автоматизирован процесс нахождения неподвижных точек, циклов и областей притяжения в рамках описанной предметной области;
Проведено тестирование программного продукта;
7. Список литературы
www.igraph.sourceforge.net -библиотека для работы с графами
http://gpucalc.sourceforge.net – библиотека для работы с графическими процессорами
«Phase transitions in logic networks», B.K. Sawhill, S.A.Kauffman
«Genetic control of flower morphogenesis in Arabidopsis thaliana: logic analysis», Luiz Mendoza, Denis Thieffry, Elena R. Alvarez-Buylla
