Работа с функциями теории графиков

Этот пример показов, как Bioinformatics Toolbox™ может использоваться для работы и визуализации графиков.

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

Создание графика из модели SimBiology ®

Функции теории графиков в Bioinformatics Toolbox работают с разреженными матрицами. Единственным ограничением является то, что матрица является квадратной. В этом примере график был создан из модели SimBiology ® осцилляционной сети Repressilator [1]. В этой модели белок A подавляет белок B, белок B подавляет белок C, который в свою очередь подавляет белок A.

load oscillatorgraph

Существует две переменные: g, разреженная матрица и names, список имен узлов графика.

whos g names
  Name        Size            Bytes  Class     Attributes

  g          65x65             2544  double    sparse    
  names      65x1              7820  cell                

Если у вас есть SimBiology, вы можете создать график с помощью следующих команд:

% sbioloadproject oscillator
% class(m1)
% Now get the adjacency matrix
% [g,names] = getadjacencymatrix(m1);

Визуализация графика

В MATLAB ® существует много функций для работы с разреженными матрицами. The spy функция отображается как * везде, где есть ненулевой элемент матрицы.

spy(g)

Это дает некоторое указание на количество ребер графика, а также показывает, что график не симметричен и, следовательно, является ориентированным графом. Однако трудно визуализировать, что происходит. The biograph объект является другим способом представления графика в Bioinformatics Toolbox.

gObj = biograph(g,names)
Biograph object with 65 nodes and 123 edges.

The view метод выкладывает график и отображает его на рисунке.

gObj = view(gObj);

Взаимодействовать с графиком можно с помощью мыши. Можно также программно изменить способ отображения графика.

% find the nodes pA, pB, and pC
pANode = find(strcmp('pA', names));
pBNode = find(strcmp('pB',names));
pCNode = find(strcmp('pC', names));
% Color these red, green, and blue
gObj.nodes(pANode).Color = [1 0 0];
gObj.nodes(pANode).Size = [40 30];
gObj.nodes(pBNode).Color = [0 1 0];
gObj.nodes(pBNode).Size = [40 30];
gObj.nodes(pCNode).Color = [0 0 1];
gObj.nodes(pCNode).Size = [40 30];
dolayout(gObj);

Использование функций теории графиков

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

graphisdag(g)
ans =

  logical

   0

Существуют также соответствующие методы объекта биографика. Они имеют имена, подобные функциям для работы с разреженными матрицами, но без префикса 'graph'.

isdag(gObj)
ans =

  logical

   0

Нахождение кратчайшего пути между узлами pA и pC

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

[dist,path,pred] = shortestpath(gObj,pANode,pCNode);

Окрашивайте узлы и ребра самого короткого пути

set(gObj.Nodes(path),'Color',[1 0.4 0.4])
edges = getedgesbynodeid(gObj,get(gObj.Nodes(path),'ID'));
set(edges,'LineColor',[1 0 0])
set(edges,'LineWidth',1.5)

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

allShortest = allshortestpaths(gObj);

Тепловая карта этих расстояний показывает некоторые интересные шаблоны.

imagesc(allShortest)
colormap(pink);
colorbar
title('All Shortest Paths for Oscillator Model');

Прохождение по графику

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

order = traverse(gObj,pANode);

Значение возврата order показывает порядок прохождения узлов, начиная с pA. Можно использовать это для поиска альтернативного пути от pA до pC.

alternatePath = order(1:find(order == pCNode));
set(gObj.Nodes(alternatePath),'Color',[0.4 0.4 1])
edges = getedgesbynodeid(gObj,get(gObj.Nodes(alternatePath),'ID'));
set(edges,'LineColor',[0 0 1])
set(edges,'LineWidth',1.5)

Нахождение связанных компонентов в графике

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

[S,C] = conncomp(gObj);

% Mark the nodes for each component with different color
colors = flipud(jet(S));
for i = 1:numel(gObj.nodes)
    gObj.Nodes(i).Color = colors(C(i),:);
end

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

Симуляция выбивания реакции

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

Найдите узлы, в которых вы заинтересованы.

r1Node = find(strcmp( 'Reaction1', names));
r2Node = find(strcmp( 'Reaction2', names));

Создайте копии разреженной матрицы и удалите все ребра, связанные с реакциями.

gNoR1 = g;
gNoR1(r1Node,:) = 0;
gNoR1(:,r1Node) = 0;
gNoR2 = g;
gNoR2(r2Node,:) = 0;
gNoR2(:,r2Node) = 0;

В случае, когда мы удаляем Reaction2, все еще существуют пути от pA до pC и назад, и структура не очень сильно изменилась.

distNoR2CA = graphshortestpath(gNoR2,pCNode,pANode)
distNoR2AC = graphshortestpath(gNoR2,pANode,pCNode)
% Display the graph from which Reaction2 was removed.
gNoR2Obj = view(biograph(gNoR2,names));
[S,C] = conncomp(gNoR2Obj);
% Mark the nodes for each component with different color
colors = flipud(jet(S));
for i = 1:numel(gNoR2Obj.nodes)
    gNoR2Obj.Nodes(i).Color = colors(C(i),:);
end
distNoR2CA =

    10


distNoR2AC =

    14

Однако в случае, когда мы удаляем Reaction1, пути от pC к pA больше нет.

distNoR1AC = graphshortestpath(gNoR1,pANode,pCNode)
distNoR1CA = graphshortestpath(gNoR1,pCNode,pANode)
distNoR1AC =

    14


distNoR1CA =

   Inf

Когда вы визуализируете график, из которого Reaction1 был удален, вы увидите значительное изменение структуры графа.

% Display the graph from which Reaction1 was removed.
gNoR1Obj = view(biograph(gNoR1,names));
[S,C] = conncomp(gNoR1Obj);
% Mark the nodes for each component with different color
colors = flipud(jet(S));
for i = 1:numel(gNoR1Obj.nodes)
    gNoR1Obj.Nodes(i).Color = colors(C(i),:);
end

Ссылки

[1] Elowitz, M.B, and Leibler, S., «A Synthetic Assillator Network of Transcriptional Regulators», Nature, 403 (6767): 335-8, 2000.

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