stringtranslate.com

Сетевой мотив

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

Сетевые мотивы — это подграфы, которые повторяются в определенной сети или даже среди различных сетей. Каждый из этих подграфов, определяемый определенным шаблоном взаимодействий между вершинами, может отражать структуру, в которой конкретные функции достигаются эффективно. Действительно, мотивы имеют важное значение в значительной степени потому, что они могут отражать функциональные свойства. Недавно [ когда? ] они привлекли большое внимание как полезная концепция для раскрытия структурных принципов проектирования сложных сетей. [1] Хотя сетевые мотивы могут обеспечить глубокое понимание функциональных возможностей сети, их обнаружение является вычислительно сложным.

Определения

Пусть G = (V, E) и G′ = (V′, E′) — два графа. Граф G′ является подграфом графа G (записывается как G′ ⊆ G ), если V′ ⊆ V и E′ ⊆ E ∩ (V′ × V′) . Если G′ ⊆ G и G′ содержит все ребра ⟨u, v⟩ ∈ E с u, v ∈ V′ , то G′ является индуцированным подграфом графа G . Мы называем G′ и G изоморфными (записывается как G′ ↔ G ), если существует биекция (взаимно-однозначное соответствие) f:V′ → V с ⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E для всех u, v ∈ V′ . Отображение f называется изоморфизмом между G и G′ . [2]

Когда G″ ⊂ G и существует изоморфизм между подграфом G″ и графом G′ , это отображение представляет появление G ′ в G . Количество появлений графа G′ в G называется частотой F G G ′ в G . Граф называется рекуррентным (или частым ) в G , когда его частота F G (G′) превышает предопределенный порог или пороговое значение. В этом обзоре мы используем термины шаблон и частый подграф как взаимозаменяемые. Существует ансамбль Ω(G) случайных графов, соответствующих нулевой модели, связанной с G . Мы должны выбрать N случайных графов равномерно из Ω(G) и вычислить частоту для конкретного частого подграфа G′ в G . Если частота G′ в G выше, чем его средняя арифметическая частота в N случайных графах R i , где 1 ≤ i ≤ N , мы называем этот повторяющийся шаблон значимым и, следовательно, рассматриваем G′ как сетевой мотив для G . Для небольшого графа G′ , сети G и набора рандомизированных сетей R(G) ⊆ Ω(R) , где R(G) = N , Z-оценка частоты G′ определяется как

где μ R (G′) и σ R (G′) обозначают среднее и стандартное отклонение частоты в наборе R(G) , соответственно. [3] [4] [5] [6] [7] [8] Чем больше Z(G′) , тем более значимым является подграф G′ как мотив. В качестве альтернативы, другим измерением в статистической проверке гипотез, которое можно рассматривать при обнаружении мотива, является p -значение , заданное как вероятность F R (G′) ≥ F G (G′) (как его нулевая гипотеза), где F R (G′) указывает частоту G' в рандомизированной сети. [6] Подграф со значением p меньше порогового значения (обычно 0,01 или 0,05) будет рассматриваться как значимый шаблон. P -значение для частоты G′ определяется как

Различные вхождения подграфа в граф . (M1 – M4) – это различные вхождения подграфа (b) в граф (a). Для частотного понятия F 1 набор M1, M2, M3, M4 представляет все совпадения, поэтому F 1 = 4. Для F 2 один из двух наборов M1, M4 или M2, M3 являются возможными совпадениями, F 2 = 2. Наконец, для частотного понятия F 3 допускается только одно из совпадений (M1 – M4), поэтому F 3 = 1. Частота этих трех частотных понятий уменьшается по мере ограничения использования сетевых элементов.

где N указывает количество рандомизированных сетей, i определяется по ансамблю рандомизированных сетей, а дельта-функция Кронекера δ(c(i)) равна единице, если выполняется условие c(i) . Концентрация [9] [10] конкретного подграфа G′ размера n в сети G относится к отношению появления подграфа в сети к общим частотам неизоморфных подграфов размера n , которое формулируется как

где индекс i определяется по множеству всех неизоморфных графов размера n. Другое статистическое измерение определено для оценки сетевых мотивов, но оно редко используется в известных алгоритмах. Это измерение введено Пикардом и др. в 2008 году и использовало распределение Пуассона, а не нормальное распределение Гаусса, которое неявно использовалось выше. [11]

Кроме того, были предложены три конкретных концепции частоты подграфа. [12] Как показано на рисунке, первая концепция частоты F 1 рассматривает все совпадения графа в исходной сети. Это определение похоже на то, что мы ввели выше. Вторая концепция F 2 определяется как максимальное количество непересекающихся по ребрам экземпляров данного графа в исходной сети. И, наконец, концепция частоты F 3 подразумевает совпадения с непересекающимися ребрами и узлами. Таким образом, две концепции F 2 и F 3 ограничивают использование элементов графа, и, как можно сделать вывод, частота подграфа снижается за счет наложения ограничений на использование элементов сети. В результате алгоритм обнаружения сетевого мотива пропустит больше подграфов-кандидатов, если мы будем настаивать на концепциях частоты F 2 и F 3 .

История

Изучение сетевых мотивов было начато Холландом и Лейнхардтом [13] [14] [15] [16], которые ввели концепцию триадной переписи сетей. Они ввели методы для подсчета различных типов конфигураций подграфов и проверки того, отличаются ли статистически подсчеты подграфов от ожидаемых в случайных сетях.

Эта идея была далее обобщена в 2002 году Ури Алоном и его группой [17], когда сетевые мотивы были обнаружены в сети регуляции генов ( транскрипции ) бактерий E. coli , а затем в большом наборе естественных сетей. С тех пор было проведено значительное количество исследований по этой теме. Некоторые из этих исследований сосредоточены на биологических приложениях, в то время как другие сосредоточены на вычислительной теории сетевых мотивов.

Биологические исследования пытаются интерпретировать мотивы, обнаруженные для биологических сетей. Например, в следующей работе [17] сетевые мотивы, обнаруженные в E. coli, были обнаружены в транскрипционных сетях других бактерий [18], а также дрожжей [19] [20] и высших организмов. [21] [22] [23] Отдельный набор сетевых мотивов был идентифицирован в других типах биологических сетей, таких как нейронные сети и сети взаимодействия белков. [5] [24] [25]

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

Совсем недавно был выпущен инструмент acc-MOTIF для обнаружения сетевых мотивов. [26]

Алгоритмы обнаружения мотивов

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

До 2004 года единственным точным методом подсчета для обнаружения NM был метод грубой силы, предложенный Майло и др . [3] Этот алгоритм оказался успешным для обнаружения небольших мотивов, но использование этого метода для поиска даже мотивов размером 5 или 6 было вычислительно нецелесообразно. Следовательно, требовался новый подход к этой проблеме.

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


Классификация алгоритмов

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

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

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

mfinder

В 2004 году Каштан и др. опубликовали mfinder — первый инструмент для поиска мотивов. [9] Он реализует два вида алгоритмов поиска мотивов: полный перебор и первый метод выборки.

Их алгоритм обнаружения выборки был основан на выборке ребер по всей сети. Этот алгоритм оценивает концентрации индуцированных подграфов и может быть использован для обнаружения мотивов в направленных или ненаправленных сетях. Процедура выборки алгоритма начинается с произвольного ребра сети, которое приводит к подграфу размера два, а затем расширяет подграф, выбирая случайное ребро, инцидентное текущему подграфу. После этого он продолжает выбирать случайные соседние ребра, пока не будет получен подграф размера n. Наконец, выбранный подграф расширяется, чтобы включить все ребра, которые существуют в сети между этими n узлами. Когда алгоритм использует подход выборки, получение несмещенных выборок является наиболее важной проблемой, которую алгоритм может решить. Однако процедура выборки не берет выборки равномерно, и поэтому Каштан и др. предложили схему взвешивания, которая назначает разные веса разным подграфам в сети. [9] Основной принцип распределения веса заключается в использовании информации о вероятности выборки для каждого подграфа, т. е. вероятные подграфы получат сравнительно меньшие веса по сравнению с маловероятными подграфами; следовательно, алгоритм должен вычислить вероятность выборки каждого подграфа, который был выбран. Этот метод взвешивания помогает mfinder беспристрастно определять концентрации подграфов.

В расширенном виде, чтобы включить резкий контраст с исчерпывающим поиском, вычислительное время алгоритма на удивление асимптотически не зависит от размера сети. Анализ вычислительного времени алгоритма показал, что он берет O(n n ) для каждой выборки подграфа размера n из сети. С другой стороны, в [9] нет анализа времени классификации выборочных подграфов, который требует решения проблемы изоморфизма графов для каждой выборки подграфа. Кроме того, на алгоритм накладываются дополнительные вычислительные усилия из-за вычисления веса подграфа. Но неизбежно сказать, что алгоритм может выбирать один и тот же подграф несколько раз — тратя время без сбора какой-либо информации. [10] В заключение, используя преимущества выборки, алгоритм работает более эффективно, чем алгоритм исчерпывающего поиска; однако он определяет только приблизительно концентрации подграфов. Этот алгоритм может находить мотивы до размера 6 из-за своей основной реализации, и в результате он выдает наиболее значимый мотив, а не все остальные. Также необходимо отметить, что данный инструмент не имеет возможности визуального представления. Алгоритм выборки показан кратко:

FPF (Мависто)

Шрайбер и Швёббермейер [12] предложили алгоритм, названный гибким поисковиком шаблонов (FPF), для извлечения частых подграфов входной сети и реализовали его в системе под названием Mavisto . [27] Их алгоритм использует свойство нисходящего замыкания , которое применимо к частотным концепциям F 2 и F 3 . Свойство нисходящего замыкания утверждает, что частота для подграфов монотонно уменьшается с увеличением размера подграфов; однако это свойство не обязательно выполняется для частотной концепции F 1 . FPF основан на дереве шаблонов (см. рисунок), состоящем из узлов, которые представляют различные графы (или шаблоны), где родительский узел каждого узла является подграфом его дочерних узлов; другими словами, соответствующий граф каждого узла дерева шаблонов расширяется путем добавления нового ребра к графу его родительского узла.

Иллюстрация дерева шаблонов в алгоритме FPF . [12]

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

Преимущество алгоритма в том, что он не рассматривает редкие подграфы и пытается завершить процесс перечисления как можно скорее; поэтому он тратит время только на перспективные узлы в дереве шаблонов и отбрасывает все остальные узлы. В качестве дополнительного бонуса понятие дерева шаблонов позволяет реализовать и выполнить FPF параллельно, поскольку можно независимо пройти каждый путь дерева шаблонов. Однако FPF наиболее полезен для частотных концепций F 2 и F 3 , поскольку нисходящее замыкание неприменимо к F 1 . Тем не менее, дерево шаблонов по-прежнему практично для F 1 , если алгоритм работает параллельно. Еще одним преимуществом алгоритма является то, что реализация этого алгоритма не имеет ограничений на размер мотива, что делает его более податливым к улучшениям. Ниже показан псевдокод FPF (Mavisto):

ЕСУ (FANMOD)

Смещение выборки Каштана и др. [9] дало большой толчок для разработки лучших алгоритмов для проблемы обнаружения NM. Хотя Каштан и др. пытались решить этот недостаток с помощью схемы взвешивания, этот метод налагал нежелательные накладные расходы на время выполнения, а также более сложную реализацию. Этот инструмент является одним из самых полезных, поскольку он поддерживает визуальные опции, а также является эффективным алгоритмом с точки зрения времени. Но он имеет ограничение по размеру мотива, поскольку не позволяет искать мотивы размером 9 или выше из-за способа реализации инструмента.

Вернике [10] представил алгоритм под названием RAND-ESU , который обеспечивает значительное улучшение по сравнению с mfinder . [9] Этот алгоритм, основанный на точном алгоритме перечисления ESU , был реализован в виде приложения под названием FANMOD . [10] RAND-ESU — это алгоритм обнаружения NM, применимый как для направленных, так и для ненаправленных сетей, эффективно использующий несмещенную выборку узлов по всей сети и предотвращающий пересчет подграфов более одного раза. Кроме того, RAND-ESU использует новый аналитический подход под названием DIRECT для определения значимости подграфа вместо использования ансамбля случайных сетей в качестве нулевой модели. Метод DIRECT оценивает концентрацию подграфа без явной генерации случайных сетей. [10] Эмпирически метод DIRECT более эффективен по сравнению со случайным сетевым ансамблем в случае подграфов с очень низкой концентрацией; однако классическая нулевая модель быстрее метода DIRECT для высококонцентрированных подграфов. [3] [10] Далее мы подробно рассмотрим алгоритм ESU , а затем покажем, как этот точный алгоритм можно эффективно модифицировать до RAND-ESU , который оценивает концентрации подграфов.

Алгоритмы ESU и RAND-ESU довольно просты и, следовательно, легко реализуемы. Сначала ESU находит множество всех индуцированных подграфов размера k , пусть S k будет этим множеством. ESU может быть реализована как рекурсивная функция; выполнение этой функции может быть отображено в виде древовидной структуры глубины k , называемой ESU-Tree (см. рисунок). Каждый из узлов ESU-Tree указывает на статус рекурсивной функции, которая влечет за собой два последовательных множества SUB и EXT. SUB относится к узлам в целевой сети, которые являются смежными и устанавливают частичный подграф размера |SUB| ≤ k . Если |SUB| = k , алгоритм нашел индуцированный полный подграф, поэтому S k = SUB ∪ S k . Однако, если |SUB| < k , алгоритм должен расширить SUB для достижения мощности k . Это делается набором EXT, который содержит все узлы, удовлетворяющие двум условиям: во-первых, каждый из узлов в EXT должен быть смежным по крайней мере с одним из узлов в SUB; во-вторых, их числовые метки должны быть больше, чем метка первого элемента в SUB. Первое условие гарантирует, что расширение узлов SUB дает связный граф, а второе условие заставляет листья ESU-Tree (см. рисунок) быть различными; в результате это предотвращает пересчет. Обратите внимание, что набор EXT не является статическим набором, поэтому на каждом шаге он может расширяться некоторыми новыми узлами, которые не нарушают два условия. Следующий шаг ESU включает классификацию подграфов, размещенных в листьях ESU-Tree, в неизоморфные классы графов размера k ; следовательно, ESU определяет частоты и концентрации подграфов. Этот этап был реализован просто с использованием алгоритма Маккея Nauty [28] [29] , который классифицирует каждый подграф, выполняя тест на изоморфизм графов. Таким образом, ESU находит набор всех индуцированных подграфов размера k в целевом графе с помощью рекурсивного алгоритма, а затем определяет их частоту с помощью эффективного инструмента.

Процедура реализации RAND-ESU довольно проста и является одним из главных преимуществ FANMOD . Можно изменить алгоритм ESU , чтобы исследовать только часть листьев ESU-Tree, применив значение вероятности 0 ≤ p d ≤ 1 для каждого уровня ESU-Tree и обязать ESU проходить каждый дочерний узел узла на уровне d-1 с вероятностью p d . Этот новый алгоритм называется RAND-ESU . Очевидно, что когда p d = 1 для всех уровней, RAND-ESU действует как ESU . При p d = 0 алгоритм ничего не находит. Обратите внимание, что эта процедура гарантирует, что шансы посещения каждого листа ESU-Tree одинаковы, что приводит к несмещенной выборке подграфов через сеть. Вероятность посещения каждого листа равна Π d p d , и это одинаково для всех листьев ESU-Tree; поэтому этот метод гарантирует несмещенную выборку подграфов из сети. Тем не менее, определение значения p d для 1 ≤ d ≤ k является еще одной проблемой, которая должна быть определена вручную экспертом для получения точных результатов концентраций подграфов. [8] Хотя нет четкого предписания по этому вопросу, Вернике дает некоторые общие наблюдения, которые могут помочь в определении значений p_d. Подводя итог, можно сказать, что RAND-ESU является очень быстрым алгоритмом для обнаружения NM в случае индуцированных подграфов, поддерживающим метод несмещенной выборки. Хотя основной алгоритм ESU и, следовательно, инструмент FANMOD известны тем, что обнаруживают индуцированные подграфы, существует тривиальная модификация ESU , которая позволяет также находить неиндуцированные подграфы. Ниже показан псевдокод ESU (FANMOD) :

NeMoFinder

Чен и др. [30] представили новый алгоритм обнаружения NM под названием NeMoFinder , который адаптирует идею в SPIN [31] для извлечения частых деревьев и после этого расширяет их в неизоморфные графы. [8] NeMoFinder использует частые деревья размера n для разбиения входной сети на коллекцию графов размера n , после чего находит частые подграфы размера n путем расширения частых деревьев по ребрам до получения полного графа размера n K n . Алгоритм находит NM в неориентированных сетях и не ограничивается извлечением только индуцированных подграфов. Кроме того, NeMoFinder является точным алгоритмом перечисления и не основан на методе выборки. Как утверждают Чен и др. , NeMoFinder применим для обнаружения относительно больших NM, например, для поиска NM размером до 12 из всей сети PPI S. cerevisiae (дрожжи), как утверждают авторы. [32]

NeMoFinder состоит из трех основных шагов. Во-первых, поиск частых деревьев размера n , затем использование повторяющихся деревьев размера n для разделения всей сети на коллекцию графов размера n , наконец, выполнение операций соединения подграфов для поиска частых подграфов размера n. [30] На первом шаге алгоритм обнаруживает все неизоморфные деревья размера n и отображения из дерева в сеть. На втором шаге диапазоны этих отображений используются для разделения сети на графы размера n. До этого шага нет различия между NeMoFinder и методом точного перечисления. Однако большая часть неизоморфных графов размера n все еще остается. NeMoFinder использует эвристику для перечисления недеревянных графов размера n с помощью полученной информации из предыдущих шагов. Главное преимущество алгоритма заключается в третьем шаге, который генерирует подграфы-кандидаты из ранее перечисленных подграфов. Это создание новых подграфов размера n выполняется путем соединения каждого предыдущего подграфа с производными подграфами от него самого, называемыми подграфами кузенов . Эти новые подграфы содержат одно дополнительное ребро по сравнению с предыдущими подграфами. Однако существуют некоторые проблемы при создании новых подграфов: нет четкого метода для получения кузенов из графа, соединение подграфа с его кузенами приводит к избыточности при создании конкретного подграфа более одного раза, а определение кузенов выполняется с помощью канонического представления матрицы смежности, которая не замкнута при операции соединения. NeMoFinder является эффективным алгоритмом поиска сетевых мотивов для мотивов размером до 12 только для сетей взаимодействия белок-белок, которые представлены в виде неориентированных графов. И он не может работать с направленными сетями, которые так важны в области сложных и биологических сетей. Ниже показан псевдокод NeMoFinder :

Грохов–Келлис

Грохов и Келлис [33] предложили точный алгоритм для перечисления появлений подграфов. Алгоритм основан на мотивно-центрическом подходе, что означает, что частота данного подграфа, называемого графом запроса , исчерпывающе определяется путем поиска всех возможных отображений из графа запроса в более крупную сеть. Утверждается [33] , что мотивно-центрический метод по сравнению с сетецентрическими методами имеет некоторые полезные особенности. Прежде всего, он позволяет избежать повышенной сложности перечисления подграфов. Кроме того, используя отображение вместо перечисления, он позволяет улучшить тест на изоморфизм. Чтобы улучшить производительность алгоритма, поскольку это неэффективный алгоритм точного перечисления, авторы ввели быстрый метод, который называется условиями нарушения симметрии . Во время простых тестов на изоморфизм подграфов подграф может быть отображен в один и тот же подграф графа запроса несколько раз. В алгоритме Грохова–Келлиса (GK) нарушение симметрии используется для того, чтобы избежать таких множественных отображений. Здесь мы представляем алгоритм GK и условие нарушения симметрии, которое устраняет избыточные проверки изоморфизма.

(a) граф G , (b) иллюстрация всех автоморфизмов G, показанная в (a) . Из множества AutG мы можем получить набор условий нарушения симметрии G, заданных SymG в (c). Только первое отображение в AutG удовлетворяет условиям SynG; в результате, применяя SymG в модуле расширения изоморфизма, алгоритм перечисляет каждый сопоставляемый подграф в сети для G только один раз. Обратите внимание, что SynG не обязательно является уникальным набором для произвольного графа G.

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

Как упоминалось выше, техника нарушения симметрии — это простой механизм, который исключает необходимость тратить время на поиск подграфа более одного раза из-за его симметрий. [33] [34] Обратите внимание, что вычисление условий нарушения симметрии требует нахождения всех автоморфизмов заданного графа запроса. Несмотря на то, что не существует эффективного (или полиномиального по времени) алгоритма для задачи автоморфизма графа, эта задача может быть эффективно решена на практике с помощью инструментов Маккея. [28] [29] Как утверждается, использование условий нарушения симметрии при обнаружении NM приводит к значительной экономии времени выполнения. Более того, из результатов в [33] [34] можно сделать вывод , что использование условий нарушения симметрии приводит к высокой эффективности, особенно для направленных сетей по сравнению с ненаправленными сетями. Условия нарушения симметрии, используемые в алгоритме GK, аналогичны ограничению, которое алгоритм ESU применяет к меткам в наборах EXT и SUB. В заключение, алгоритм GK вычисляет точное число появлений заданного графа запроса в большой сложной сети, а использование условий нарушения симметрии улучшает производительность алгоритма. Кроме того, алгоритм GK является одним из известных алгоритмов, не имеющих ограничений на размер мотива в реализации, и потенциально он может находить мотивы любого размера.

Подход к цветовому кодированию

Большинство алгоритмов в области обнаружения NM используются для поиска индуцированных подграфов сети. В 2008 году Нога Алон и др. [35] представили подход для поиска также неиндуцированных подграфов. Их метод работает на неориентированных сетях, таких как PPI. Кроме того, он подсчитывает неиндуцированные деревья и ограниченные по древовидной ширине подграфы. Этот метод применяется для подграфов размером до 10.

Этот алгоритм подсчитывает количество неиндуцированных вхождений дерева T с k = O(logn) вершинами в сеть G с n вершинами следующим образом:

  1. Цветовое кодирование. Раскрасить каждую вершину входной сети G независимо и равномерно случайным образом одним из k цветов.
  2. Подсчет. Применить динамическую процедуру программирования для подсчета количества неиндуцированных вхождений T , в которых каждая вершина имеет уникальный цвет. Более подробную информацию об этом шаге см. в [35].
  3. Повторите два предыдущих шага O(e k ) раз и сложите количество появлений T , чтобы получить оценку количества его появлений в G .

Поскольку доступные сети PPI далеки от полноты и отсутствия ошибок, этот подход подходит для обнаружения NM для таких сетей. Поскольку алгоритм Грохова–Келлиса и этот являются популярными для неиндуцированных подграфов, стоит упомянуть, что алгоритм, представленный Алоном и др., требует меньше времени, чем алгоритм Грохова–Келлиса. [35]

МОДА

Омиди и др. [36] представили новый алгоритм обнаружения мотивов под названием MODA , который применим для индуцированного и неиндуцированного обнаружения NM в ненаправленных сетях. Он основан на мотив-центрическом подходе, обсуждаемом в разделе алгоритма Грохова–Келлиса. Очень важно различать мотив-центрические алгоритмы, такие как алгоритм MODA и GK, из-за их способности работать как алгоритмы поиска запросов. Эта особенность позволяет таким алгоритмам находить один запрос мотива или небольшое количество запросов мотива (не все возможные подграфы заданного размера) с большими размерами. Поскольку количество возможных неизоморфных подграфов увеличивается экспоненциально с размером подграфа, для мотивов большого размера (даже больше 10) сетецентрические алгоритмы, те, которые ищут все возможные подграфы, сталкиваются с проблемой. Хотя алгоритмы, ориентированные на мотивы, также испытывают трудности с обнаружением всех возможных подграфов большого размера, их способность находить небольшое их количество иногда является важным свойством.

Используя иерархическую структуру, называемую деревом расширения , алгоритм MODA способен извлекать NM заданного размера систематически и аналогично FPF , что позволяет избежать перечисления бесперспективных подграфов; MODA учитывает потенциальные запросы (или кандидаты на подграфы), которые могут привести к частым подграфам. Несмотря на то, что MODA напоминает FPF в использовании древовидной структуры, дерево расширения применимо только для вычисления частотного понятия F 1 . Как мы обсудим далее, преимущество этого алгоритма заключается в том, что он не выполняет тест изоморфизма подграфов для недревовидных графов запросов. Кроме того, он использует метод выборки для ускорения времени выполнения алгоритма.

Вот основная идея: с помощью простого критерия можно обобщить отображение графа размера k в сеть на его суперграфы того же размера. Например, предположим, что есть отображение f(G) графа G с k узлами в сеть, и у нас есть граф того же размера G′ с одним ребром &langu, v⟩ ; f G отобразит G′ в сеть, если в сети есть ребро ⟨f G (u), f G (v)⟩ . В результате мы можем использовать набор отображений графа для определения частот его суперграфов того же порядка просто за время O(1) без проведения проверки изоморфизма подграфов. Алгоритм гениально начинается с минимально связанных графов запросов размера k и находит их отображения в сети с помощью изоморфизма подграфов. После этого, с сохранением размера графа, он расширяет ранее рассмотренные графы запросов ребро за ребром и вычисляет частоту этих расширенных графов, как упомянуто выше. Процесс расширения продолжается до тех пор, пока не будет достигнут полный граф K k (полностью связанный с k(k-1) ⁄ 2 ребром).

Как обсуждалось выше, алгоритм начинается с вычисления частот поддеревьев в сети, а затем расширяет поддеревья по ребрам. Один из способов реализации этой идеи называется деревом расширения T k для каждого k . На рисунке показано дерево расширения для подграфов размера 4. T k организует текущий процесс и предоставляет графы запросов иерархическим образом. Строго говоря, дерево расширения T k представляет собой просто направленный ациклический граф или DAG, в котором его корневой номер k указывает размер графа, существующего в дереве расширения, а каждый из его других узлов содержит матрицу смежности отдельного графа запросов размера k. Узлы на первом уровне T k представляют собой все отдельные деревья размера k и при обходе T k в глубину графы запросов расширяются на одно ребро на каждом уровне. Граф запроса в узле представляет собой подграф графа запроса в дочернем узле узла с разницей в одно ребро. Самый длинный путь в T k состоит из (k 2 -3k+4)/2 ребер и является путем от корня до листового узла, содержащего полный граф. Генерация деревьев расширения может быть выполнена с помощью простой процедуры, которая объясняется в [36] .

MODA проходит T k и, когда он извлекает деревья запросов из первого уровня T k , он вычисляет их наборы отображений и сохраняет эти отображения для следующего шага. Для недеревных запросов из T k алгоритм извлекает отображения, связанные с родительским узлом в T k , и определяет, какие из этих отображений могут поддерживать текущие графы запросов. Процесс будет продолжаться до тех пор, пока алгоритм не получит полный граф запросов. Отображения деревьев запросов извлекаются с помощью алгоритма Грохова–Келлиса. Для вычисления частоты недеревных графов запросов алгоритм использует простую процедуру, которая занимает O(1) шагов. Кроме того, MODA использует метод выборки, при котором выборка каждого узла в сети линейно пропорциональна степени узла, распределение вероятностей в точности похоже на хорошо известную модель предпочтительного присоединения Барабаши-Альберта в области сложных сетей. [37] Этот подход генерирует приближения; однако результаты почти стабильны в различных исполнениях, поскольку подграфы агрегируются вокруг высокосвязанных узлов. [38] Псевдокод MODA показан ниже:

Иллюстрация дерева расширения T4 для 4-узловых графов запросов . На первом уровне находятся неизоморфные деревья размера k, и на каждом уровне к родительскому графу добавляется ребро для формирования дочернего графа. На втором уровне находится граф с двумя альтернативными ребрами, который показан пунктирным красным ребром. Фактически, этот узел представляет два расширенных графа, которые изоморфны. [36]

Кавош

Недавно представленный алгоритм Kavosh [39] нацелен на улучшение использования основной памяти. Kavosh может использоваться для обнаружения NM как в направленных, так и в ненаправленных сетях. Основная идея перечисления похожа на алгоритмы GK и MODA , которые сначала находят все подграфы размера k , в которых участвовал определенный узел, затем удаляют узел, а затем повторяют этот процесс для оставшихся узлов. [39]

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

Протокол извлечения подграфов использует композиции целого числа. Для извлечения подграфов размера k необходимо рассмотреть все возможные композиции целого числа k-1 . Композиции k-1 состоят из всех возможных способов выражения k-1 как суммы положительных целых чисел. Суммы, в которых порядок слагаемых отличается, считаются различными. Композиция может быть выражена как k 2 ,k 3 ,...,k m , где k 2 + k 3 + ... + k m = k-1 . Для подсчета подграфов на основе композиции выбираются k i узлов из i -го уровня дерева, которые будут узлами подграфов ( i = 2,3,...,m ). Выбранные k-1 узлов вместе с узлом в корне определяют подграф в сети. После обнаружения подграфа, вовлеченного в качестве соответствия в целевой сети, для того, чтобы иметь возможность оценить размер каждого класса в соответствии с целевой сетью, Кавош использует алгоритм nauty [28] [29] таким же образом, как и FANMOD . Перечислительная часть алгоритма Кавоша показана ниже:

Недавно для этого программного обеспечения был разработан плагин Cytoscape под названием CytoKavosh [40] . Он доступен на веб-странице Cytoscape [1].

G-Tries

В 2010 году Педро Рибейро и Фернандо Силва предложили новую структуру данных для хранения коллекции подграфов, называемую g-trie . [41] Эта структура данных, которая концептуально похожа на префиксное дерево, хранит подграфы в соответствии с их структурами и находит вхождения каждого из этих подграфов в более крупном графе. Одним из заметных аспектов этой структуры данных является то, что при обнаружении сетевого мотива необходимо оценить подграфы в основной сети. Таким образом, нет необходимости находить те в случайной сети, которые не находятся в основной сети. Это может быть одной из трудоемких частей в алгоритмах, в которых выводятся все подграфы в случайных сетях.

G -trie — это многоканальное дерево, которое может хранить коллекцию графов. Каждый узел дерева содержит информацию об одной вершине графа и ее соответствующих ребрах к узлам-предкам. Путь от корня к листу соответствует одному графу. Потомки узла g-trie имеют общий подграф. Построение g -trie хорошо описано в. [41] После построения g-trie происходит подсчет. Основная идея в процессе подсчета — откат по всем возможным подграфам, но в то же время выполнение тестов на изоморфизм. Этот метод отката по сути является тем же методом, который используется другими подходами, ориентированными на мотивы, такими как алгоритмы MODA и GK . Использование общих подструктур в том смысле, что в данный момент времени существует частичное изоморфное соответствие для нескольких различных подграфов-кандидатов.

Среди упомянутых алгоритмов G-Tries является самым быстрым. Однако недостатком этого алгоритма является чрезмерное использование памяти, что может ограничить размер обнаруживаемых мотивов персональным компьютером со средней памятью.

ПараМОДА и НемоМап

ParaMODA [42] и NemoMap [43] — быстрые алгоритмы, опубликованные в 2017 и 2018 годах соответственно. Они не так масштабируемы, как многие другие. [44]

Сравнение

Таблицы и рисунок ниже показывают результаты запуска упомянутых алгоритмов на различных стандартных сетях. Эти результаты взяты из соответствующих источников, [36] [39] [41], поэтому их следует рассматривать индивидуально.

Время выполнения алгоритмов Грохова–Келлиса, mfinder, FANMOD, FPF и MODA для подграфов от трех до девяти узлов . [36]

Устоявшиеся мотивы и их функции

Много экспериментальных работ было посвящено пониманию сетевых мотивов в сетях регуляции генов . Эти сети контролируют, какие гены экспрессируются в клетке в ответ на биологические сигналы. Сеть определяется таким образом, что гены являются узлами, а направленные ребра представляют собой контроль одного гена фактором транскрипции (регуляторным белком, который связывает ДНК), кодируемым другим геном. Таким образом, сетевые мотивы представляют собой шаблоны генов, регулирующих скорость транскрипции друг друга. При анализе сетей транскрипции видно, что одни и те же сетевые мотивы появляются снова и снова в различных организмах от бактерий до человека. Например, сеть транскрипции E. coli и дрожжей состоит из трех основных семейств мотивов, которые составляют почти всю сеть. Основная гипотеза заключается в том, что сетевой мотив был независимо выбран эволюционными процессами в конвергентной манере, [45] [46], поскольку создание или устранение регуляторных взаимодействий происходит быстро в эволюционной шкале времени относительно скорости изменения генов, [45] [46] [47] Кроме того, эксперименты по динамике, генерируемой сетевыми мотивами в живых клетках, указывают на то, что они имеют характерные динамические функции. Это предполагает, что сетевой мотив служит строительным блоком в регуляторных сетях генов, которые полезны для организма.

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

Отрицательная ауторегуляция (НАР)

Схематическое изображение мотива саморегуляции

Одним из самых простых и распространенных сетевых мотивов в E. coli является отрицательная авторегуляция, при которой фактор транскрипции (TF) подавляет собственную транскрипцию. Было показано, что этот мотив выполняет две важные функции. Первая функция — ускорение реакции. Было показано, что NAR ускоряет реакцию на сигналы как теоретически [48] , так и экспериментально. Это было впервые показано в синтетической транскрипционной сети [49], а затем в естественном контексте в системе репарации ДНК SOS E. coli. [50] Вторая функция — повышенная стабильность концентрации продукта авторегулируемого гена по отношению к стохастическому шуму, тем самым уменьшая различия в уровнях белка между различными клетками. [51] [52] [53]

Положительная ауторегуляция (PAR)

Положительная авторегуляция (PAR) происходит, когда фактор транскрипции увеличивает собственную скорость производства. В отличие от мотива NAR этот мотив замедляет время реакции по сравнению с простой регуляцией. [54] В случае сильного PAR мотив может привести к бимодальному распределению уровней белка в популяциях клеток. [55]

Контуры прямой связи (FFL)

Схематическое изображение мотива прямой связи

Этот мотив обычно встречается во многих генных системах и организмах. Мотив состоит из трех генов и трех регуляторных взаимодействий. Целевой ген C регулируется двумя ТФ A и B, а ТФ B также регулируется ТФ A. Поскольку каждое из регуляторных взаимодействий может быть как положительным, так и отрицательным, возможно, существует восемь типов мотивов FFL. [56] Два из этих восьми типов: когерентный тип 1 FFL (C1-FFL) (где все взаимодействия положительны) и некогерентный тип 1 FFL (I1-FFL) (A активирует C, а также активирует B, который подавляет C) встречаются в транскрипционной сети E. coli и дрожжей гораздо чаще, чем другие шесть типов. [56] [57] В дополнение к структуре схемы следует также учитывать способ, которым сигналы от A и B интегрируются промотором C. В большинстве случаев FFL представляет собой либо вентиль И (для активации C требуются A и B), либо вентиль ИЛИ (для активации C достаточно A или B), но возможны и другие функции входа.

Когерентный тип 1 FFL (C1-FFL)

Было показано, что C1-FFL с вентилем AND выполняет функцию элемента «чувствительной к знаку задержки» и детектора устойчивости как теоретически [56] , так и экспериментально [58] с арабинозной системой E. coli . Это означает, что этот мотив может обеспечить фильтрацию импульсов, при которой короткие импульсы сигнала не будут генерировать ответ, но постоянные сигналы будут генерировать ответ после короткой задержки. Выключение выхода при окончании постоянного импульса будет быстрым. Противоположное поведение возникает в случае суммирующего вентиля с быстрым ответом и отложенным выключением, как было продемонстрировано в системе жгутиков E. coli . [59] Эволюция de novo C1-FFL в сетях регуляции генов была продемонстрирована вычислительно в ответ на отбор для фильтрации идеализированного короткого импульса сигнала, но для неидеализированного шума вместо этого была выбрана система динамической прямой регуляции с другой топологией. [60]

Некогерентный тип 1 ФФЛ (I1-ФФЛ)

I1-FFL является генератором импульсов и ускорителем ответа. Два сигнальных пути I1-FFL действуют в противоположных направлениях, где один путь активирует Z, а другой подавляет его. Когда репрессия завершена, это приводит к импульсоподобной динамике. Также было экспериментально продемонстрировано, что I1-FFL может служить ускорителем ответа способом, который аналогичен мотиву NAR. Разница в том, что I1-FFL может ускорять ответ любого гена, а не обязательно гена фактора транскрипции. [61] Дополнительная функция была назначена сетевому мотиву I1-FFL: было показано и теоретически, и экспериментально, что I1-FFL может генерировать немонотонную входную функцию как в синтетических [62] , так и в нативных системах. [63] Наконец, единицы экспрессии, которые включают некогерентный прямой контроль продукта гена, обеспечивают адаптацию к количеству шаблона ДНК и могут превосходить простые комбинации конститутивных промоторов. [64] Прямая регуляция показала лучшую адаптацию, чем отрицательная обратная связь , и схемы, основанные на интерференции РНК, оказались наиболее устойчивыми к изменению количества ДНК-шаблонов. [64] Эволюция de novo I1-FFL в сетях регуляции генов была продемонстрирована вычислительно в ответ на отбор для генерации импульса, при этом I1-FFL были более эволюционно доступны, но не превосходили альтернативный мотив, в котором репрессор активируется выходом, а не входом. [65]

Многовыходные FFL

В некоторых случаях одни и те же регуляторы X и Y регулируют несколько генов Z одной и той же системы. Было показано, что, регулируя силу взаимодействий, этот мотив определяет временной порядок активации генов. Это было экспериментально продемонстрировано в системе жгутиков E. coli . [66]

Модули с одним входом (SIM)

Этот мотив возникает, когда один регулятор регулирует набор генов без дополнительной регуляции. Это полезно, когда гены кооперативно выполняют определенную функцию и поэтому всегда должны активироваться синхронно. Регулируя силу взаимодействий, он может создать временную программу экспрессии генов, которые он регулирует. [67]

В литературе Multiple-input modules (MIM) возник как обобщение SIM. Однако точные определения SIM и MIM были источником непоследовательности. Существуют попытки предоставить ортогональные определения для канонических мотивов в биологических сетях и алгоритмов для их перечисления, особенно SIM, MIM и Bi-Fan (2x2 MIM). [68]

Плотно перекрывающиеся регулоны (DOR)

Этот мотив возникает в случае, когда несколько регуляторов комбинаторно контролируют набор генов с различными регуляторными комбинациями. Этот мотив был обнаружен в E. coli в различных системах, таких как утилизация углерода, анаэробный рост, реакция на стресс и другие. [17] [22] Чтобы лучше понять функцию этого мотива, необходимо получить больше информации о том, как множественные входы интегрируются генами. Каплан и др. [69] составили карту входных функций генов утилизации сахара в E. coli , показав различные формы.

Мотивы деятельности

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

Критика

Предположение (иногда более иногда менее неявное) в основе сохранения топологической подструктуры заключается в том, что она имеет особое функциональное значение. Это предположение недавно было подвергнуто сомнению. Некоторые авторы утверждали, что мотивы, такие как мотивы би-веера , могут показывать разнообразие в зависимости от контекста сети, и поэтому [71] структура мотива не обязательно определяет функцию. Структура сети, безусловно, не всегда указывает на функцию; эта идея существует уже некоторое время, например, см. оперон Sin. [72]

Большинство анализов функции мотива проводятся с учетом мотива, работающего изолированно. Недавние исследования [73] дают убедительные доказательства того, что сетевой контекст, т. е. связи мотива с остальной частью сети, слишком важен, чтобы делать выводы о функции только из локальной структуры — в цитируемой статье также рассматриваются критические замечания и альтернативные объяснения наблюдаемых данных. Анализ влияния одного модуля мотива на глобальную динамику сети изучается в. [74] Еще одна недавняя работа предполагает, что определенные топологические особенности биологических сетей естественным образом приводят к общему появлению канонических мотивов, тем самым подвергая сомнению, являются ли частоты появления разумным доказательством того, что структуры мотивов выбираются по их функциональному вкладу в работу сетей. [75] [76]

Смотрите также

Ссылки

  1. ^ Масуди-Неджад А., Шрайбер Ф., Разаги МК З. (2012). «Строительные блоки биологических сетей: обзор основных алгоритмов обнаружения сетевых мотивов». IET Systems Biology . 6 (5): 164–74. doi :10.1049/iet-syb.2011.0011. PMID  23101871.
  2. ^ Дистель, Рейнхард (2005). Теория графов (3-е изд.). Берлин: Springer. ISBN 9783540261827.
  3. ^ abc Milo R, Shen-Orr SS, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002). «Сетевые мотивы: простые строительные блоки сложных сетей». Science . 298 (5594): 824–827. Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
  4. ^ Альберт Р., Барабаши АЛ (2002). «Статистическая механика сложных сетей». Обзоры современной физики . 74 (1): 47–49. arXiv : cond-mat/0106096 . Bibcode :2002RvMP...74...47A. CiteSeerX 10.1.1.242.4753 . doi :10.1103/RevModPhys.74.47. S2CID  60545. 
  5. ^ ab Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004). «Суперсемейства спроектированных и эволюционировавших сетей». Science . 303 (5663): 1538–1542. Bibcode :2004Sci...303.1538M. doi :10.1126/science.1089167. PMID  15001784. S2CID  14760882.
  6. ^ ab Schwöbbermeyer, H (2008). «Сетевые мотивы». В Junker BH, Schreiber F (ред.). Анализ биологических сетей . Хобокен, Нью-Джерси: John Wiley & Sons. стр. 85–108.
  7. ^ Борнхольдт, С.; Шустер, Х.Г. (2003). Справочник по графикам и сетям: от генома до Интернета . стр. 417. Bibcode :2003hgnf.book.....B. {{cite encyclopedia}}: |journal=проигнорировано ( помощь )
  8. ^ abc Ciriello G, Guerra C (2008). «Обзор моделей и алгоритмов для обнаружения мотивов в сетях белок-белкового взаимодействия». Briefings in Functional Genomics and Proteomics . 7 (2): 147–156. doi : 10.1093/bfgp/eln015 . PMID  18443014.
  9. ^ abcdef Каштан Н., Ицковиц С., Мило Р., Алон У. (2004). «Эффективный алгоритм выборки для оценки концентраций подграфов и обнаружения сетевых мотивов». Биоинформатика . 20 (11): 1746–1758. doi : 10.1093/bioinformatics/bth163 . PMID  15001476.
  10. ^ abcdef Wernicke S (2006). «Эффективное обнаружение сетевых мотивов». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 3 (4): 347–359. CiteSeerX 10.1.1.304.2576 . doi :10.1109/tcbb.2006.51. PMID  17085844. S2CID  6188339. 
  11. ^ Picard F, Daudin JJ, Schbath S , Robin S (2005). «Оценка исключительности сетевых мотивов». J. Comp. Bio . 15 (1): 1–20. CiteSeerX 10.1.1.475.4300 . doi :10.1089/cmb.2007.0137. PMID  18257674. 
  12. ^ abc Schreiber F, Schwöbbermeyer H (2005). "Концепции частот и обнаружение шаблонов для анализа мотивов в сетях". Transactions on Computational Systems Biology III . Lecture Notes in Computer Science. Vol. 3737. pp. 89–104. CiteSeerX 10.1.1.73.1130 . doi :10.1007/11599128_7. ISBN  978-3-540-30883-6.
  13. ^ Холланд, П. В. и Лейнхардт, С. (1974). Статистический анализ локальной структуры в социальных сетях. Рабочий документ № 44, Национальное бюро экономических исследований.
  14. ^ Холланд, П. и Лейнхардт, С. (1975). Статистический анализ локальной. структуры в социальных сетях. Социологическая методология, Дэвид Хайзе, ред. Сан-Франциско: Josey-Bass.
  15. ^ Холланд, П. В. и Лейнхардт, С. (1976). Локальная структура в социальных сетях. Социологическая методология, 7, 1-45.
  16. ^ Холланд, П. В. и Лейнхардт, С. (1977). Метод обнаружения структуры в социометрических данных. В Social Networks (стр. 411-432). Academic Press.
  17. ^ abc Shen-Orr SS, Milo R, Mangan S, Alon U (май 2002 г.). «Сетевые мотивы в сети регуляции транскрипции Escherichia coli». Nat. Genet . 31 (1): 64–8. doi : 10.1038/ng881 . PMID  11967538. S2CID  2180121.
  18. ^ Eichenberger P, Fujita M, Jensen ST и др. (октябрь 2004 г.). «Программа транскрипции генов для одного дифференцирующегося типа клеток во время споруляции у Bacillus subtilis». PLOS Biology . 2 (10): e328. doi : 10.1371/journal.pbio.0020328 . PMC 517825. PMID  15383836 .  Значок открытого доступа
  19. ^ Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (октябрь 2002 г.). «Сетевые мотивы: простые строительные блоки сложных сетей». Science . 298 (5594): 824–7. Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
  20. ^ Lee TI, Rinaldi NJ, Robert F и др. (октябрь 2002 г.). «Транскрипционные регуляторные сети в Saccharomyces cerevisiae». Science . 298 (5594): 799–804. Bibcode :2002Sci...298..799L. doi :10.1126/science.1075090. PMID  12399584. S2CID  4841222.
  21. ^ Odom DT, Zizlsperger N, Gordon DB, et al. (Февраль 2004). «Контроль экспрессии генов поджелудочной железы и печени с помощью факторов транскрипции HNF». Science . 303 (5662): 1378–81. Bibcode :2004Sci...303.1378O. doi :10.1126/science.1089769. PMC 3012624 . PMID  14988562. 
  22. ^ ab Boyer LA, Lee TI, Cole MF и др. (сентябрь 2005 г.). «Основная схема регуляции транскрипции в эмбриональных стволовых клетках человека». Cell . 122 (6): 947–56. doi :10.1016/j.cell.2005.08.020. PMC 3006442 . PMID  16153702. 
  23. ^ Iranfar N, Fuller D, Loomis WF (февраль 2006 г.). «Транскрипционная регуляция постагрегационных генов у Dictyostelium с помощью петли прямой связи с участием GBF и LagC». Dev. Biol . 290 (2): 460–9. doi : 10.1016/j.ydbio.2005.11.035 . PMID  16386729.
  24. ^ Ma'ayan A, Jenkins SL, Neves S, et al. (август 2005 г.). «Формирование регуляторных паттернов во время распространения сигнала в клеточной сети млекопитающих». Science . 309 (5737): 1078–83. Bibcode :2005Sci...309.1078M. doi :10.1126/science.1108876. PMC 3032439 . PMID  16099987. 
  25. ^ Ptacek J, Devgan G, Michaud G, et al. (декабрь 2005 г.). «Глобальный анализ фосфорилирования белков в дрожжах» (PDF) . Nature (Представленная рукопись). 438 (7068): 679–84. Bibcode :2005Natur.438..679P. doi :10.1038/nature04187. PMID  16319894. S2CID  4332381.
  26. ^ «Acc-Motif: Ускоренное обнаружение мотива».
  27. ^ Шрайбер Ф., Швоббермейер Х. (2005). «MAVisto: инструмент для исследования сетевых мотивов». Биоинформатика . 21 (17): 3572–3574. doi : 10.1093/bioinformatics/bti556 . PMID  16020473.
  28. ^ abc McKay BD (1981). «Практический изоморфизм графов». Congressus Numerantium . 30 : 45–87. arXiv : 1301.1493 . Bibcode : 2013arXiv1301.1493M.
  29. ^ abc McKay BD (1998). «Исчерпывающая генерация без изоморфов». Журнал алгоритмов . 26 (2): 306–324. doi :10.1006/jagm.1997.0898.
  30. ^ ab Chen J, Hsu W, Li Lee M и др. (2006). NeMoFinder: анализ взаимодействий белок-белок в масштабе генома с мотивами мезомасштабных сетей . 12-я международная конференция ACM SIGKDD по открытию знаний и добыче данных. Филадельфия, Пенсильвания, США. стр. 106–115.
  31. ^ Хуан Дж., Ван В., Принс Дж. и др. (2004). SPIN: извлечение максимально частых подграфов из баз данных графов . 10-я международная конференция ACM SIGKDD по обнаружению знаний и добыче данных. стр. 581–586.
  32. ^ Uetz P, Giot L, Cagney G, et al. (2000). «Комплексный анализ белок-белковых взаимодействий в Saccharomyces cerevisiae». Nature . 403 (6770): 623–627. Bibcode :2000Natur.403..623U. doi :10.1038/35001009. PMID  10688190. S2CID  4352495.
  33. ^ abcd Grochow JA, Kellis M (2007). Обнаружение сетевых мотивов с использованием перечисления подграфов и нарушения симметрии (PDF) . RECOMB. стр. 92–106. doi :10.1007/978-3-540-71681-5_7.
  34. ^ ab Grochow JA (2006). О структуре и эволюции сетей взаимодействия белков (PDF) . Диссертация M. Eng., Массачусетский технологический институт, кафедра электротехники и компьютерных наук.
  35. ^ abc Alon N; Dao P; Hajirasouliha I; Hormozdiari F; Sahinalp SC (2008). «Подсчет и обнаружение мотивов биомолекулярной сети с помощью цветового кодирования». Биоинформатика . 24 (13): i241–i249. doi :10.1093/bioinformatics/btn163. PMC 2718641. PMID  18586721 . 
  36. ^ abcde Омиди С., Шрайбер Ф., Масуди-Неджад А. (2009). «MODA: эффективный алгоритм обнаружения сетевых мотивов в биологических сетях». Genes Genet Syst . 84 (5): 385–395. doi : 10.1266/ggs.84.385 . PMID  20154426.
  37. ^ Barabasi AL, Albert R (1999). «Возникновение масштабирования в случайных сетях». Science . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Bibcode :1999Sci...286..509B. doi :10.1126/science.286.5439.509. PMID  10521342. S2CID  524106.
  38. ^ Васкес А., Добрин Р., Серджи Д. и др. (2004). «Топологическая связь между крупномасштабными атрибутами и локальными моделями взаимодействия сложных сетей». PNAS . 101 (52): 17940–17945. arXiv : cond-mat/0408431 . Bibcode :2004PNAS..10117940V. doi : 10.1073/pnas.0406024101 . PMC 539752 . PMID  15598746. 
  39. ^ abcd Кашани З.Р., Ахрабиан Х., Элахи Э., Новзари-Далини А., Ансари Э.С., Асади С., Мохаммади С., Шрайбер Ф., Масуди-Неджад А. (2009). «Кавош: новый алгоритм поиска сетевых мотивов». БМК Биоинформатика . 10 (318): 318. дои : 10.1186/1471-2105-10-318 . ПМК 2765973 . ПМИД  19799800.  Значок открытого доступа
  40. ^ Али Масуди-Неджад; Митра Анасариола; Али Салехзаде-Язди; Саханд Хакабимамагани (2012). «CytoKavosh: плагин Cytoscape для поиска сетевых мотивов в больших биологических сетях». PLOS ONE . 7 (8): e43287. Bibcode : 2012PLoSO...743287M. doi : 10.1371/journal.pone.0043287 . PMC 3430699. PMID  22952659 .  Значок открытого доступа
  41. ^ abcd Рибейро П., Сильва Ф. (2010). G-Tries: эффективная структура данных для обнаружения сетевых мотивов. ACM 25th Symposium On Applied Computing - Bioinformatics Track. Сьерре, Швейцария. С. 1559–1566.
  42. ^ Мбадиве, Сомадина; Ким, Уён (ноябрь 2017 г.). «ParaMODA: улучшение поиска шаблонов подграфов, ориентированных на мотивы, в сетях PPI». Международная конференция IEEE по биоинформатике и биомедицине (BIBM) 2017 г. стр. 1723–1730. doi :10.1109/BIBM.2017.8217920. ISBN 978-1-5090-3050-7. S2CID  5806529. Архивировано из оригинала 2023-02-04 . Получено 2020-09-11 .
  43. ^ "NemoMap: улучшенный алгоритм обнаружения мотивов на основе сети, ориентированной на мотивы". Журнал Advances in Science, Technology and Engineering Systems . 2018. Архивировано из оригинала 2023-02-04 . Получено 2020-09-11 .
  44. ^ Патра, Сабьясачи; Мохапатра, Анджали (2020). «Обзор инструментов и алгоритмов для обнаружения сетевых мотивов в биологических сетях». IET Systems Biology . 14 (4): 171–189. doi : 10.1049/iet-syb.2020.0004 . ISSN  1751-8849. PMC 8687426. PMID 32737276  . 
  45. ^ ab Babu MM, Luscombe NM, Aravind L, Gerstein M, Teichmann SA (июнь 2004 г.). «Структура и эволюция сетей регуляции транскрипции». Current Opinion in Structural Biology . 14 (3): 283–91. CiteSeerX 10.1.1.471.9692 . doi :10.1016/j.sbi.2004.05.004. PMID  15193307. 
  46. ^ ab Conant GC, Wagner A (июль 2003 г.). «Конвергентная эволюция генных цепей». Nat. Genet . 34 (3): 264–6. doi :10.1038/ng1181. PMID  12819781. S2CID  959172.
  47. ^ Dekel E, Alon U (июль 2005 г.). «Оптимальность и эволюционная настройка уровня экспрессии белка». Nature . 436 (7050): 588–92. Bibcode :2005Natur.436..588D. doi :10.1038/nature03842. PMID  16049495. S2CID  2528841.
  48. ^ Zabet NR (сентябрь 2011 г.). «Отрицательная обратная связь и физические пределы генов». Журнал теоретической биологии . 284 (1): 82–91. arXiv : 1408.1869 . Bibcode : 2011JThBi.284...82Z. CiteSeerX 10.1.1.759.5418 . doi : 10.1016/j.jtbi.2011.06.021. PMID  21723295. S2CID  14274912. 
  49. ^ Rosenfeld N, Elowitz MB, Alon U (ноябрь 2002 г.). «Отрицательная авторегуляция ускоряет время реакции сетей транскрипции». J. Mol. Biol . 323 (5): 785–93. CiteSeerX 10.1.1.126.2604 . doi :10.1016/S0022-2836(02)00994-4. PMID  12417193. 
  50. ^ Camas FM, Blázquez J, Poyatos JF (август 2006 г.). «Аутогенный и неаутогенный контроль ответа в генетической сети». Proc. Natl. Acad. Sci. USA . 103 (34): 12718–23. Bibcode : 2006PNAS..10312718C. doi : 10.1073/pnas.0602119103 . PMC 1568915. PMID  16908855 . 
  51. ^ Бескей А., Серрано Л. (июнь 2000 г.). «Инженерная стабильность в генных сетях с помощью авторегуляции». Nature . 405 (6786): 590–3. Bibcode :2000Natur.405..590B. doi :10.1038/35014651. PMID  10850721. S2CID  4407358.
  52. ^ Dublanche Y, Michalodimitrakis K, Kümmerer N, Foglierini M, Serrano L (2006). "Шум в петлях отрицательной обратной связи транскрипции: моделирование и экспериментальный анализ". Mol. Syst. Biol . 2 (1): 41. doi :10.1038/msb4100081. PMC 1681513 . PMID  16883354. 
  53. ^ Шимога В., Уайт Дж., Ли И., Зонтаг Э., Блерис Л. (2013). «Отрицательная ауторегуляция синтетического трансгена млекопитающих». Mol. Syst. Biol . 9 : 670. doi : 10.1038/msb.2013.27. PMC 3964311. PMID  23736683 . 
  54. ^ Maeda YT, Sano M (июнь 2006 г.). «Регуляторная динамика синтетических генных сетей с положительной обратной связью». J. Mol. Biol . 359 (4): 1107–24. doi :10.1016/j.jmb.2006.03.064. PMID  16701695.
  55. ^ Becskei A, Séraphin B, Serrano L (май 2001 г.). «Положительная обратная связь в сетях генов эукариот: дифференциация клеток путем преобразования градуированного в бинарный ответ». EMBO J . 20 (10): 2528–35. doi :10.1093/emboj/20.10.2528. PMC 125456 . PMID  11350942. 
  56. ^ abc Mangan S, Alon U (октябрь 2003 г.). "Структура и функция сетевого мотива петли прямой связи". Proc. Natl. Acad. Sci. USA . 100 (21): 11980–5. Bibcode :2003PNAS..10011980M. doi : 10.1073/pnas.2133841100 . PMC 218699 . PMID  14530388. 
  57. ^ Ma HW, Kumar B, Ditges U, Gunzer F, Buer J, Zeng AP (2004). «Расширенная транскрипционная регуляторная сеть Escherichia coli и анализ ее иерархической структуры и сетевых мотивов». Nucleic Acids Res . 32 (22): 6643–9. doi :10.1093/nar/gkh1009. PMC 545451. PMID  15604458 . 
  58. ^ Mangan S, Zaslaver A, Alon U (ноябрь 2003 г.). «Когерентная петля прямой связи служит чувствительным к знаку элементом задержки в сетях транскрипции». J. Mol. Biol . 334 (2): 197–204. CiteSeerX 10.1.1.110.4629 . doi :10.1016/j.jmb.2003.09.049. PMID  14607112. 
  59. ^ Калир С., Манган С., Алон У. (2005). «Когерентная петля прямой связи с функцией ввода SUM продлевает экспрессию жгутиков в Escherichia coli». Mol. Syst. Biol . 1 (1): E1–E6. doi :10.1038/msb4100010. PMC 1681456. PMID  16729041 . 
  60. ^ Сюн, Кун; Ланкастер, Алекс К.; Сигал, Марк Л.; Масел, Джоанна (3 июня 2019 г.). «Регулирование прямой связи адаптивно развивается через динамику, а не топологию, когда есть собственный шум». Nature Communications . 10 (1): 2418. Bibcode :2019NatCo..10.2418X. doi :10.1038/s41467-019-10388-6. PMC 6546794 . PMID  31160574. 
  61. ^ Mangan S, Itzkovitz S, Zaslaver A, Alon U (март 2006 г.). «Некогерентная петля прямой связи ускоряет время реакции системы gal Escherichia coli ». J. Mol. Biol . 356 (5): 1073–81. CiteSeerX 10.1.1.184.8360 . doi :10.1016/j.jmb.2005.12.003. PMID  16406067. 
  62. ^ Entus R, Aufderheide B, Sauro HM (август 2007 г.). «Проектирование и реализация трех некогерентных биологических датчиков концентрации на основе мотивов прямой связи». Syst Synth Biol . 1 (3): 119–28. doi :10.1007/s11693-007-9008-6. PMC 2398716. PMID  19003446 . 
  63. ^ Каплан С., Брен А., Декель Э., Алон У. (2008). «Некогерентная петля прямой связи может генерировать немонотонные входные функции для генов». Mol. Syst. Biol . 4 (1): 203. doi :10.1038/msb.2008.43. PMC 2516365. PMID  18628744 . 
  64. ^ ab Bleris L, Xie Z, Glass D, Adadey A, Sontag E, Benenson Y (2011). "Синтетические некогерентные цепи прямой связи демонстрируют адаптацию к количеству их генетического шаблона". Mol. Syst. Biol . 7 (1): 519. doi :10.1038/msb.2011.49. PMC 3202791. PMID  21811230 . 
  65. ^ Сюн, Кун; Герштейн, Марк; Масел, Джоанна (5 ноября 2021 г.). «Различия в эволюционной доступности определяют, какой одинаково эффективный регуляторный мотив эволюционирует для генерации импульсов». Генетика . 219 (3): iyab140. doi :10.1093/genetics/iyab140. PMC 8570775 . PMID  34740240. 
  66. ^ Калир С., МакКлур Дж., Паббараджу К. и др. (июнь 2001 г.). «Упорядочение генов в пути жгутиков путем анализа кинетики экспрессии у живых бактерий». Science . 292 (5524): 2080–3. doi :10.1126/science.1058758. PMID  11408658. S2CID  14396458.
  67. ^ Zaslaver A, Mayo AE, Rosenberg R, et al. (Май 2004). «Программа транскрипции «точно в срок» в метаболических путях». Nat. Genet . 36 (5): 486–91. doi : 10.1038/ng1348 . PMID  15107854.
  68. ^ Konagurthu AS, Lesk AM (2008). «Одиночные и множественные входные модули в регуляторных сетях». Белки . 73 (2): 320–324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
  69. ^ Kaplan S, Bren A, Zaslaver A, Dekel E, Alon U (март 2008). «Различные двумерные входные функции контролируют бактериальные гены сахара». Mol. Cell . 29 (6): 786–92. doi :10.1016/j.molcel.2008.01.021. PMC 2366073 . PMID  18374652. 
  70. ^ Chechik G, Oh E, Rando O, Weissman J, Regev A, Koller D (ноябрь 2008 г.). «Мотивы активности раскрывают принципы синхронизации в транскрипционном контроле метаболической сети дрожжей». Nat. Biotechnol . 26 (11): 1251–9. doi :10.1038/nbt.1499. PMC 2651818. PMID 18953355  . 
  71. ^ Ingram PJ, Stumpf MP, Stark J (2006). «Сетевые мотивы: структура не определяет функцию». BMC Genomics . 7 : 108. doi : 10.1186/1471-2164-7-108 . PMC 1488845. PMID  16677373 .  Значок открытого доступа
  72. ^ Voigt CA, Wolf DM, Arkin AP (март 2005 г.). «Оперон Bacillus subtilis sin: эволюционирующий сетевой мотив». Genetics . 169 (3): 1187–202. doi :10.1534/genetics.104.031955. PMC 1449569 . PMID  15466432. Архивировано из оригинала 2023-02-04 . Получено 2011-02-26 . 
  73. ^ Knabe JF, Nehaniv CL, Schilstra MJ (2008). «Мотивы отражают эволюционировавшую функцию? — Нет конвергентной эволюции топологий подграфов генетических регуляторных сетей». BioSystems . 94 (1–2): 68–74. Bibcode :2008BiSys..94...68K. doi :10.1016/j.biosystems.2008.05.012. PMID  18611431.
  74. ^ Тейлор Д., Рестрепо Дж. Г. (2011). «Сетевое подключение во время слияний и роста: оптимизация добавления модуля». Physical Review E. 83 ( 6): 66112. arXiv : 1102.4876 . Bibcode : 2011PhRvE..83f6112T. doi : 10.1103/PhysRevE.83.066112. PMID  21797446. S2CID  415932.
  75. ^ Konagurthu, Arun S.; Lesk, Arthur M. (23 апреля 2008 г.). «Одиночные и множественные входные модули в регуляторных сетях». Белки: структура, функция и биоинформатика . 73 (2): 320–324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
  76. ^ Konagurthu AS, Lesk AM (2008). «О происхождении закономерностей распределения мотивов в биологических сетях». BMC Syst Biol . 2 : 73. doi : 10.1186/1752-0509-2-73 . PMC 2538512. PMID  18700017 .  Значок открытого доступа

Внешние ссылки