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

В этом примере показано, как 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® для работы с разреженными матрицами. spy функционируйте отображения как * везде, где существует ненулевой элемент матрицы.

spy(g)

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

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

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

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

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');

Пересечение графика

Другая типичная проблема с графиками находит эффективный способ пересечь график путем перемещения между смежными узлами. 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, свинцом и 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 и Leibler, S., "Синтетическая колебательная сеть транскрипционных регуляторов", природа, 403 (6767):335-8, 2000.

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