Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Сетевая наука
Internet_map_1024.jpg
Теория
Типы сетей
Графики
Функции
Типы
  • Двудольный
  • Полный
  • Режиссер
  • Гипер
  • Мульти
  • Случайный
  • Взвешенный
МетрикиАлгоритмы
  • Центральность
  • Степень
  • Мотив
  • Кластеризация
  • Распределение степеней
  • Ассортативность
  • Расстояние
  • Модульность
  • Эффективность
Модели
Топология
  • Случайный график
  • Эрдеш – Реньи
  • Барабаши – Альберт
  • Фитнес-модель
  • Уоттс-Строгац
  • Экспоненциальный случайный (ERGM)
  • Случайный геометрический (RGG)
  • Гиперболический (HGN)
  • Иерархический
  • Стохастический блок
  • Максимальная энтропия
  • Мягкая конфигурация
  • Тест LFR
Динамика
  • Логическая сеть
  • агент на основе
  • Эпидемия / SIR
СпискиКатегории
  • Темы
  • Программного обеспечения
  • Сетевые ученые
  • Категория: Теория сетей
  • Категория: Теория графов
  • v
  • т
  • е

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

Сетевые мотивы - это подграфы, которые повторяются в конкретной сети или даже среди различных сетей. Каждый из этих подграфов, определяемый конкретным шаблоном взаимодействий между вершинами, может отражать структуру, в которой конкретные функции выполняются эффективно. В самом деле, мотивы имеют важное значение в основном потому, что они могут отражать функциональные свойства. В последнее время они привлекли много внимания как полезная концепция, раскрывающая принципы структурного проектирования сложных сетей. [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 случайных граф равномерно из Q (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' как мотив. В качестве альтернативы, другое измерение в статистической проверки гипотез , которые могут быть рассмотрены в обнаружении мотива является р -значение , учитывая как вероятность F R (G ') ≥ F G (G') ( в качестве нуль-гипотезы), где F R (ГРАММ')указывает частоту 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 ' в сети G относится к отношению к появлению суб-графа в сети к общему п -size неизоморфных подграфов частот, который сформулирован

где индекс 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 г. единственным методом точного подсчета для обнаружения ЯМ был метод грубой силы, предложенный Milo et al . [3] Этот алгоритм оказался успешным для обнаружения небольших мотивов, но использование этого метода для нахождения мотивов даже 5 или 6 размера было невозможно с вычислительной точки зрения. Следовательно, требовался новый подход к этой проблеме.

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

mfinder [ править ]

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

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

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

mfinder
Определения: E s - это набор выбранных ребер. В ы есть множество всех узлов, которые тронутые ребра в E .
Инициализируйте V s и E s как пустые множества.

1. Выберите случайное ребро e 1 = (v i , v j ) . Обновить E s = {e 1 }, V s = {v i , v j }

2. Составьте список L всех соседних ребер E s . Пропустите из L все ребра между элементами V s .

3. Выберите случайное ребро е = {V K , V л } из L . Обновите E s = E s ⋃ {e }, V s = V s ⋃ {v k , v l }.

4. Повторите шаги 2-3 до завершения подграфа из n узлов (до тех пор, пока | V s | = n ).

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

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) показан ниже:

Мависто
Данные: График G , размер целевой последовательности t , частотная концепция F

Результат: Установите R шаблонов размера t с максимальной частотой.

R ← φ , f макс ← 0

P ← начальная строчка p1 размера 1

M p 1 ← все совпадения p 1 в G

Пока P ≠ φ do

 P max ← выбрать все шаблоны из P с максимальным размером.

 P ← выбрать шаблон с максимальной частотой из P max

 Ε = ExtensionLoop (G, p, M p )

 Для каждого шаблона p ∈ E

 Если F = F 1, то f ← size (M p )

 Иначе f ← Максимально независимый набор (F, M p )

 Конец

 Если size (p) = t, то

 Если f = f max, то R ← R ⋃ {p }

 Иначе, если f> f max, то R ← {p }; f max ← f

 Конец

 Еще

 Если F = F 1 или f ≥ f max, то P ← P ⋃ {p }

 Конец

 Конец

 Конец

Конец

ESU (FANMOD) [ править ]

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

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

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

(a) целевой граф размера 5 , (b) ESU-дерево глубины k, которое связано с извлечением подграфов размера 3 в целевом графе . Листья соответствуют набору S3 или всем индуцированным подграфам размера 3 целевого графа (a). Узлы в дереве ESU включают два смежных набора, первый набор содержит смежные узлы, называемые SUB, а второй набор с именем EXT содержит все узлы, которые примыкают по крайней мере к одному из узлов SUB и где их числовые метки больше, чем узлы SUB этикетки. Набор EXT используется алгоритмом для расширения набора SUB до тех пор, пока он не достигнет желаемого размера подграфа, который помещается на самый нижний уровень ESU-Tree (или его листья).
Перечень ESU (FANMOD)
EnumerateSubgraphs (G, k)

Вход: граф G = (V, E) и целое число 1 ≤ k ≤ | V | .

Вывод: Все размерно K подграфы в G .

для каждой вершины v ∈ V делаем

 VExtension ← {u ∈ N ({v}) | u> v }

 вызвать ExtendSubgraph ({v}, VExtension, v)

конец

ExtendSubgraph (VSubgraph, VExtension, v)

если | VSПодграф | = k, затем вывести G [VSubgraph] и вернуть

в то время как VExtension ∅ ∅ do

 Удалить произвольно выбранную вершину w из VExtension

 VExtension ′ ← VExtension ∪ {u ∈ N excl (w, VSubgraph) | u> v }

 вызвать ExtendSubgraph (VSubgraph ∪ {w}, VExtension ′, v)

возвращаться

NeMoFinder [ править ]

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

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

NeMoFinder
Вход:

G - сеть PPI;

N - количество рандомизированных сетей;

K - максимальный размер сетевого мотива;

F - порог частоты;

S - Порог уникальности;

Выход:

U - повторяющийся и уникальный набор сетевых мотивов;

D ← ∅ ;

для мотивов размером k от 3 до K сделать

 T ← FindRepeatedTrees (k) ;

 GD k ← GraphPartition (G, T)

 D ← D ∪ T ;

 D ′ ← T ;

 i ← k ;

 а D ′ ≠ ∅ и i ≤ k × (k - 1) / 2 делают

 D ′ ← FindRepeatedGraphs (k, i, D ′) ;

 D ← D ∪ D ′ ;

 я ← я + 1 ;

 конец пока

конец для

для счетчика i от 1 до N сделать

 G rand ← RandomizedNetworkGeneration () ;

 для каждого g ∈ D do

 GetRandFrequency (g, G rand ) ;

 конец для

конец для

U ← ∅ ;

для каждого g ∈ D do

 s ← GetUniqunessValue (g) ;

 если s ≥ S, то

 U ← U ∪ {g };

 конец, если

конец для

вернуть U ;

Грохов-Келлис [ править ]

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

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

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

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

Цветовое кодирование [ править ]

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

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

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

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

MODA [ править ]

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

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

Вот основная идея: с помощью простого критерия можно обобщить отображение графа размера k в сеть на его суперграфы того же размера. Например, предположим, что есть отображение f (G) графа G с k узлами в сеть, и у нас есть граф G 'того же размера с еще одним ребром & lang, v⟩ ; f G отобразит G ′ в сеть, если в сети есть ребро ⟨f G (u), f G (v)⟩ . В результате мы можем использовать набор отображений графа для определения частот его суперграфов того же порядка просто в O (1)время без проведения проверки изоморфизма подграфов. Алгоритм изобретательно начинается с минимально связных графов запросов размера 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]
MODA
Вход: G : входной график, k : размер подграфика , Δ : пороговое значение

Выход: Частый подграф Список: Список всех часта к -размер подграфов

Примечание: F G : набор отображений из G во входном графе G

получить T k

делать

 G ′ = Get-Next-BFS (T k ) // G ′ - граф запроса

 если | E (G ′) | = (к - 1)

  модуль отображения вызовов (G ', G)

 еще

 вызвать Enumerating-Module (G ′, G, T k )

 конец, если

 сохранить F 2

 если | F G | > Δ, то

 добавить G ' в список частых подграфов

 конец, если

Пока | E (G ') | = (к - 1) / 2

вернуть список часто встречающихся подграфов

Кавош [ править ]

Недавно представленный алгоритм под названием Kavosh [39] направлен на улучшение использования основной памяти. Кавош может использоваться для обнаружения ЯМ как в направленных, так и в ненаправленных сетях. Основная идея перечисления аналогична алгоритмам 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. . Перечислительная часть алгоритма Кавоша представлена ​​ниже:

Перечисление Кавошей
Enumerate_Vertex (G, u, S, остаток, i)

Вход: G : Входной граф u : Корневая вершина S : выбор ( S = {S 0 , S 1 , ..., S k-1 } - это массив множества всех S i ) Остаток : количество оставшихся вершин для быть выбранным i : Текущая глубина дерева. Выход: все подграфы размера k графа G с корнем в u .
 
 
 
 

если Remainder = 0, то вернуть else ValList ← Validate (G, S i-1 , u) n i ← Min (| ValList |, Remainder) для k i = от 1 до n i do C ← Initial_Comb (ValList, k i ) ( Сделайте первый выбор комбинации вершин в соответствии с) repeat S i ← C Enumerate_Vertex (G, u, S, Remainder-k i , i + 1) Next_Comb (ValList, k i )
 

 
 
 
 
 
 
 
 
 
 (Сделайте выбор следующей комбинации вершин в соответствии) до тех пор, пока C = NILL end для каждого v ∈ ValList do Visited [v] ← false end for end if
 
 
 
 
 

Подтвердить (G, родители, u)

Вход: G : входной граф, Родители : выбранные вершины последнего слоя, u : Корневая вершина.
Выход: действительные вершины текущего уровня.

ValList ← NILL
для каждого V ∈ Родители делают для каждого W ∈ Neighbor [и] делать , если метка [и] <метка [ш] И НЕ посещаемые [ш] затем посетили [ш] ← верно ValList = ValList + ш конец , если конец для конец для возврата ValList
 
 
 
 
 
 


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

G-Tries [ править ]

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

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

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

ParaMODA и NemoMap [ править ]

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

Сравнение [ править ]

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

Время выполнения Grochow – Kellis, mfinder, FANMOD, FPF и MODA для подграфов от трех до девяти узлов . [36]
Время выполнения Grochow – Kellis, FANMOD и G-Trie для подграфов от трех до девяти узлов в пяти различных сетях. [41]
СетьРазмерИсходная сеть переписиСредняя перепись в случайных сетях
FANMODGKG-TrieFANMODGKG-Trie
Дельфины50,070,030,010,130,040,01
60,480,280,041.140,350,07
73,023,440,238,343,550,46
819,4473,161,6967,9437,314,03
9100,862984,226,98493,98366,7924,84
Схема60,490,410,030,550,240,03
73,283,730,223,531,340,17
817,7848.001,5221,427,911.06
Социальное30,310,110,020,350,110,02
47,781,370,5613,271,860,57
5208,3031,8514,88531,6562,6622.11
Дрожжи30,470,330,020,570,350,02
410.072,040,3612,902,250,41
5268,5134,1012,73400,1347,1614,98
Мощность30,511,460,000,911,370,01
41,384,340,023,014,400,03
54,6816,950,1012,3817,540,14
620,3695,580,5567,6592,740,88
7101,04765,913,36408,15630,655,17
Время работы mfinder, FANMOD, Mavisto и Kavosh для подграфов от трех узлов до десяти узлов в трех разных сетях. [39]
 Размер →345678910
Сети ↓Алгоритмы ↓
Кишечная палочкаКавош0,301,8414,91141,981374,013173,7121110,31120560,1
FANMOD0,812,5315,71132,241205,99256,6--
Мависто13532-------
Mfinder31,029723671-----
ЭлектронныйКавош0,080,368,0211,3977,22422,62823,718037,5
FANMOD0,531.064,3424,24160967,99--
Мависто210,01727------
Mfinder714109,82020.2----
СоциальноеКавош0,040,231,6310,4869,43415,662594,1914611,23
FANMOD0,460,843,0717,63117,43845,93--
Мависто3931492------
Mfinder1249798181077----

Классификация алгоритмов [ править ]

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

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

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

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

Классификация алгоритмов обнаружения мотивов
Метод подсчетаОсноваИмяНаправленный / неориентированныйИндуцированный / Неиндуцированный
ТочныйСетевая ориентацияmfinderОбеИндуцированный
ESU (FANMOD)ОбеИндуцированный
Кавош (используется в CytoKavosh )ОбеИндуцированный
G-TriesОбеИндуцированный
PGDНеориентированныйИндуцированный
Подграф-центрическийFPF (Мависто)ОбеИндуцированный
NeMoFinderНеориентированныйИндуцированный
Грохов – КеллисОбеОбе
MODAОбеОбе
Оценка / выборкаПодход цветового кодированияN. Alon et al. АлгоритмНеориентированныйНеиндуцированный
Другие подходыmfinderОбеИндуцированный
ESU (FANMOD)ОбеИндуцированный
Адреса разработчиков алгоритмов
АлгоритмНазвание лаборатории / отделаДепартамент / ШколаИнститутАдресЭлектронное письмо
mfinderГруппа Ури АлонаКафедра молекулярной клеточной биологииИнститут науки ВейцманаРеховот, Израиль, Вольфсон, Rm. 607уриалон на weizmann.ac.il
FPF (Мависто)--------Leibniz-Institut für Pflanzengenetik und Kulturpflanzenforschung (IPK)Corrensstraße 3, D-06466 Stadt Seeland, OT Gatersleben, Deutschlandschreibe на ipk-gatersleben.de
ESU (FANMOD)Lehrstuhl Theoretische Informatik IInstitut für InformatikЙенский университет им. Фридриха ШиллераErnst-Abbe-Platz 2, D-07743 Jena, Deutschlandsebastian.wernicke на gmail.com
NeMoFinder----Школа вычислительной техникиНациональный университет СингапураСингапур 119077chenjin на comp.nus.edu.sg
Грохов – КеллисCS Theory Group и Complex Systems GroupИнформатикаКолорадский университет, Боулдер1111 Engineering Dr. ECOT 717, 430 UCB Boulder, CO 80309-0430 СШАjgrochow на colorado.edu
N. Alon et al. АлгоритмКафедра чистой математикиШкола математических наукТель-авивский университетТель-Авив 69978, Израильногаа на post.tau.ac.il
MODAЛаборатория системной биологии и биоинформатики (ЛББ)Институт биохимии и биофизики (IBB)Тегеранский университетEnghelab Square, Enghelab Ave, Тегеран, Иранamasoudin на ibb.ut.ac.ir
Кавош (используется в CytoKavosh )Лаборатория системной биологии и биоинформатики (ЛББ)Институт биохимии и биофизики (IBB)Тегеранский университетEnghelab Square, Enghelab Ave, Тегеран, Иранamasoudin на ibb.ut.ac.ir
G-TriesЦентр исследований перспективных вычислительных системИнформатикаУниверситет ПортуRua Campo Alegre 1021/1055, Порту, Португалияpribeiro на dcc.fc.up.pt
PGDЛаборатория сетевого обучения и открытияДепартамент компьютерных наукУниверситет ПердьюУниверситет Пердью, 305 N University St, West Lafayette, IN 47907[email protected]

Хорошо зарекомендовавшие себя мотивы и их функции [ править ]

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

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

Отрицательное саморегулирование (NAR) [ править ]

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

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

Положительное саморегулирование (PAR) [ править ]

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

Петли с прямой связью (FFL) [ править ]

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

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

Когерентный тип 1 FFL (C1-FFL) [ править ]

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

Некогерентный тип 1 FFL (I1-FFL) [ править ]

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

FFL с несколькими выходами [ править ]

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

Модули с одним входом (SIM) [ править ]

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

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

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

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

Мотивы деятельности [ править ]

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

Социально-технические мотивы [ править ]

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

Социально-экономические мотивы [ править ]

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

Критика [ править ]

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

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

В то время как изучение мотивов в основном применялось к статическим сложным сетям, исследование временных сложных сетей [78] предложило значительную переинтерпретацию сетевых мотивов и ввело концепцию временных сетевых мотивов . Браха и Бар-Ям [79]изучили динамику структуры локальных мотивов в зависимых от времени / темпоральных сетях и нашли повторяющиеся паттерны, которые могли бы предоставить эмпирические доказательства циклов социального взаимодействия. Вопреки перспективе стабильных мотивов и профилей мотивов в сложных сетях, они продемонстрировали, что для временных сетей локальная структура зависит от времени и может со временем развиваться. Браха и Бар-Ям далее предположили, что анализ временной локальной структуры может предоставить важную информацию о динамике задач и функций системного уровня.

См. Также [ править ]

  • Клика (теория графов)
  • Графическая модель

Ссылки [ править ]

  1. ^ Масуди-Неджад A, F Schreiber, Razaghi MK Z (2012). "Строительные блоки биологических сетей: обзор основных алгоритмов обнаружения сетевых мотивов". Системная биология ИЭПП . 6 (5): 164–74. DOI : 10,1049 / МТВ-syb.2011.0011 . PMID  23101871 .
  2. ^ Diestel R (2005). «Теория графов (выпускные тексты по математике)». 173 . Нью-Йорк: Springer-Verlag Heidelberg. Cite journal requires |journal= (help)
  3. ^ a b c Майло Р., Шен-Орр С.С., Ицковиц С., Каштан Н., Чкловский Д., Алон Ю. (2002). «Сетевые мотивы: простые строительные блоки сложных сетей». Наука . 298 (5594): 824–827. Bibcode : 2002Sci ... 298..824M . CiteSeerX 10.1.1.225.8750 . DOI : 10.1126 / science.298.5594.824 . PMID 12399590 .  
  4. ^ Альберт R, Barabási AL (2002). «Статистическая механика сложных сетей». Обзоры современной физики . 74 (1): 47–49. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47 . CiteSeerX 10.1.1.242.4753 . DOI : 10.1103 / RevModPhys.74.47 . S2CID 60545 .  
  5. ^ a b Майло Р., Ицковиц С., Каштан Н., Левитт Р., Шен-Орр С., Айзенштат И., Шеффер М., Алон Ю. (2004). «Суперсемейства спроектированных и развитых сетей» . Наука . 303 (5663): 1538–1542. Bibcode : 2004Sci ... 303.1538M . DOI : 10.1126 / science.1089167 . PMID 15001784 . S2CID 14760882 .  
  6. ^ a b Schwöbbermeyer, H (2008). «Сетевые мотивы». В Junker BH, Schreiber F (ed.). Анализ биологических сетей . Хобокен, Нью-Джерси: John Wiley & Sons. С. 85–108.
  7. ^ Борнхольдт, S; Шустер, HG (2003). «Справочник по графам и сетям: от генома к Интернету». Справочник по графам и сетям: от генома к Интернету . п. 417. Bibcode : 2003hgnf.book ..... B .
  8. ^ a b c Сириелло Дж., Герра С. (2008). «Обзор моделей и алгоритмов обнаружения мотивов в сетях белок-белковых взаимодействий» . Брифинги по функциональной геномике и протеомике . 7 (2): 147–156. DOI : 10.1093 / bfgp / eln015 . PMID 18443014 . 
  9. ^ a b c d e f Каштан Н., Ицковиц С., Майло Р., Алон Ю. (2004). «Эффективный алгоритм выборки для оценки концентраций подграфов и обнаружения сетевых мотивов» . Биоинформатика . 20 (11): 1746–1758. DOI : 10.1093 / биоинформатики / bth163 . PMID 15001476 . 
  10. ^ Б с д е е 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. ^ Пикара 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. ^ a b c Schreiber F, Schwöbbermeyer H (2005). «Частотные концепции и обнаружение паттернов для анализа мотивов в сетях». Труды по вычислительной системной биологии III . Конспект лекций по информатике. 3737 . С. 89–104. CiteSeerX 10.1.1.73.1130 . DOI : 10.1007 / 11599128_7 . ISBN  978-3-540-30883-6. Отсутствует или пусто |title=( справка )
  13. ^ Holland, PW, и Leinhardt, S. (1974). Статистический анализ локальной структуры в социальных сетях. Рабочий документ № 44, Национальное бюро экономических исследований.
  14. Перейти ↑ Hollandi, P., & Leinhardt, S. (1975). Статистический анализ локальных. Структура в социальных сетях. Социологическая методология, Дэвид Хейз, изд. Сан-Франциско: Джози-Басс.
  15. ^ Holland, PW, и Leinhardt, S. (1976). Локальная структура в социальных сетях. Социологическая методология, 7, 1-45.
  16. ^ Holland, PW, и Leinhardt, S. (1977). Метод определения структуры социометрических данных. В социальных сетях (стр. 411-432). Академическая пресса.
  17. ^ a b c Шен-Орр СС, Майло Р., Манган С., Алон У. (май 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 Биология . 2 (10): e328. DOI : 10.1371 / journal.pbio.0020328 . PMC 517825 . PMID 15383836 .  
  19. ^ Milo R, Шен-Орр S, Itzkovitz S, Каштан N, Chklovskii D, Алон U (октябрь 2002). «Сетевые мотивы: простые строительные блоки сложных сетей». Наука . 298 (5594): 824–7. Bibcode : 2002Sci ... 298..824M . CiteSeerX 10.1.1.225.8750 . DOI : 10.1126 / science.298.5594.824 . PMID 12399590 .  
  20. ^ Ли Т.И., Ринальди Нью-Джерси, Роберт Ф. и др. (Октябрь 2002 г.). «Транскрипционные регуляторные сети в Saccharomyces cerevisiae». Наука . 298 (5594): 799–804. Bibcode : 2002Sci ... 298..799L . DOI : 10.1126 / science.1075090 . PMID 12399584 . S2CID 4841222 .  
  21. ^ Odom DT, Zizlsperger N, Gordon DB и др. (Февраль 2004 г.). «Контроль экспрессии генов поджелудочной железы и печени факторами транскрипции HNF» . Наука . 303 (5662): 1378–81. Bibcode : 2004Sci ... 303.1378O . DOI : 10.1126 / science.1089769 . PMC 3012624 . PMID 14988562 .  
  22. ^ a b Бойер Л.А., Ли Т.И., Коул М.Ф. и др. (Сентябрь 2005 г.). «Основные схемы регуляции транскрипции в человеческих эмбриональных стволовых клетках» . Cell . 122 (6): 947–56. DOI : 10.1016 / j.cell.2005.08.020 . PMC 3006442 . PMID 16153702 .  
  23. ^ Iranfar N Фуллер D, Loomis WF (февраль 2006). «Регуляция транскрипции постагрегационных генов в Dictyostelium с помощью петли прямой связи с участием GBF и LagC» . Dev. Биол . 290 (2): 460–9. DOI : 10.1016 / j.ydbio.2005.11.035 . PMID 16386729 . 
  24. ^ Ma'ayan A, Jenkins SL, Neves S и др. (Август 2005 г.). «Формирование регуляторных паттернов во время распространения сигнала в сотовой сети млекопитающих» . Наука . 309 (5737): 1078–83. Bibcode : 2005Sci ... 309.1078M . DOI : 10.1126 / science.1108876 . PMC 3032439 . PMID 16099987 .  
  25. ^ Птачек Дж, Девган Дж, Мишо Дж и др. (Декабрь 2005 г.). «Глобальный анализ фосфорилирования белков в дрожжах» (PDF) . Природа (Представленная рукопись). 438 (7068): 679–84. Bibcode : 2005Natur.438..679P . DOI : 10,1038 / природа04187 . PMID 16319894 . S2CID 4332381 .   
  26. ^ «Acc-Motif: ускоренное обнаружение мотивов» .
  27. ^ Schreiber F, Schwobbermeyer H (2005). «MAVisto: инструмент для исследования сетевых мотивов» . Биоинформатика . 21 (17): 3572–3574. DOI : 10.1093 / биоинформатики / bti556 . PMID 16020473 . 
  28. ^ a b c McKay BD (1981). «Практический изоморфизм графов». Congressus Numerantium . 30 : 45–87. arXiv : 1301,1493 . Bibcode : 2013arXiv1301.1493M .
  29. ↑ a b c McKay BD (1998). «Исчерпывающее поколение без изоморфов». Журнал алгоритмов . 26 (2): 306–324. DOI : 10.1006 / jagm.1997.0898 .
  30. ^ а б Чен Дж, Хсу В., Ли Ли М. и др. (2006). NeMoFinder: анализ белок-белковых взаимодействий в масштабе всего генома с помощью сетевых мотивов мезомасштаба . 12-я международная конференция ACM SIGKDD по открытию знаний и интеллектуальному анализу данных. Филадельфия, Пенсильвания, США. С. 106–115.
  31. ^ Хуан Дж, Ван В, Принс Дж и др. (2004). SPIN: добыча максимально частых подграфов из графовых баз данных . 10-я международная конференция ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. С. 581–586.
  32. ^ Uetz P, Giot L, Cagney G и др. (2000). «Комплексный анализ белок-белковых взаимодействий в Saccharomyces cerevisiae». Природа . 403 (6770): 623–627. Bibcode : 2000Natur.403..623U . DOI : 10.1038 / 35001009 . PMID 10688190 . S2CID 4352495 .  
  33. ^ a b c d Grochow JA, Kellis M (2007). Обнаружение сетевых мотивов с использованием перечисления подграфов и нарушения симметрии (PDF) . РЕКОМБ. С. 92–106. DOI : 10.1007 / 978-3-540-71681-5_7 .
  34. ^ a b Grochow JA (2006). О структуре и эволюции сетей взаимодействия белков (PDF) . Диссертация, магистр технических наук, Массачусетский технологический институт, кафедра электротехники и информатики.
  35. ^ a b c Алон Н; Дао П; Хаджирасулиха I; Хормоздиари Ф; Сахиналп СК (2008). «Подсчет и обнаружение мотивов биомолекулярной сети с помощью цветового кодирования» . Биоинформатика . 24 (13): i241 – i249. DOI : 10.1093 / биоинформатики / btn163 . PMC 2718641 . PMID 18586721 .  
  36. ^ a b c d e Омиди С., Шрайбер Ф., Масуди-Нежад А. (2009). «MODA: эффективный алгоритм обнаружения сетевых мотивов в биологических сетях» . Genes Genet Syst . 84 (5): 385–395. DOI : 10,1266 / ggs.84.385 . PMID 20154426 . 
  37. ^ Barabasi AL, Альберт R (1999). «Возникновение масштабирования в случайных сетях». Наука . 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. ^ a b c d Kashani ZR, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A (2009). «Кавош: новый алгоритм поиска сетевых мотивов» . BMC Bioinformatics . 10 (318): 318. DOI : 10,1186 / 1471-2105-10-318 . PMC 2765973 . PMID 19799800 .  
  40. ^ Али Масуди-Неджад; Митра Анасариола; Али Салехзаде-Язди; Саханд Хакабимамагани (2012). «CytoKavosh: плагин Cytoscape для поиска сетевых мотивов в больших биологических сетях» . PLOS ONE . 7 (8): e43287. Bibcode : 2012PLoSO ... 743287M . DOI : 10.1371 / journal.pone.0043287 . PMC 3430699 . PMID 22952659 .  
  41. ^ а б в г Рибейро П., Сильва Ф (2010). G-Tries: эффективная структура данных для обнаружения сетевых мотивов . 25-й симпозиум ACM по прикладным вычислениям - трек по биоинформатике. Сиерре, Швейцария. С. 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 .
  43. ^ «NemoMap: Улучшенный алгоритм обнаружения сетевых мотивов, ориентированный на мотив» . Журнал "Достижения науки, технологий и инженерных систем" . 2018 . Проверено 11 сентября 2020 .
  44. ^ Патра, Сабьясачи; Мохапатра, Анджали (2020). «Обзор инструментов и алгоритмов обнаружения сетевых мотивов в биологических сетях» . Системная биология ИЭПП . 14 (4): 171–189. DOI : 10,1049 / МТВ-syb.2020.0004 . ISSN 1751-8849 . PMID 32737276 .  
  45. ^ a b Бабу М.М., Ласкомб Н.М., Аравинд Л., Герштейн М., Тейхманн С.А. (июнь 2004 г.). «Структура и эволюция сетей регуляции транскрипции». Текущее мнение в структурной биологии . 14 (3): 283–91. CiteSeerX 10.1.1.471.9692 . DOI : 10.1016 / j.sbi.2004.05.004 . PMID 15193307 .  
  46. ^ a b Conant GC, Wagner A (июль 2003 г.). «Конвергентная эволюция генных цепей». Nat. Genet . 34 (3): 264–6. DOI : 10.1038 / ng1181 . PMID 12819781 . S2CID 959172 .  
  47. ^ Dekel E Алон U (июль 2005). «Оптимальность и эволюционная настройка уровня экспрессии белка». Природа . 436 (7050): 588–92. Bibcode : 2005Natur.436..588D . DOI : 10,1038 / природа03842 . PMID 16049495 . S2CID 2528841 .  
  48. ^ Забет NR (сентябрь 2011). «Отрицательная обратная связь и физические пределы генов». Журнал теоретической биологии . 284 (1): 82–91. arXiv : 1408,1869 . CiteSeerX 10.1.1.759.5418 . DOI : 10.1016 / j.jtbi.2011.06.021 . PMID 21723295 . S2CID 14274912 .   
  49. ^ Rosenfeld N, Elowitz MB, Алон U (ноябрь 2002). «Отрицательная ауторегуляция ускоряет время отклика сетей транскрипции». J. Mol. Биол . 323 (5): 785–93. CiteSeerX 10.1.1.126.2604 . DOI : 10.1016 / S0022-2836 (02) 00994-4 . PMID 12417193 .  
  50. ^ Camas FM, Blazquez J, Poyatos JF (август 2006). «Аутогенный и неаутогенный контроль ответа в генетической сети» . Proc. Natl. Акад. Sci. США . 103 (34): 12718–23. Bibcode : 2006PNAS..10312718C . DOI : 10.1073 / pnas.0602119103 . PMC 1568915 . PMID 16908855 .  
  51. ^ Becskei A, L Serrano (июнь 2000). «Инженерная устойчивость в генных сетях за счет авторегуляции». Природа . 405 (6786): 590–3. Bibcode : 2000Natur.405..590B . DOI : 10.1038 / 35014651 . PMID 10850721 . S2CID 4407358 .  
  52. ^ Dublanche Y, Michalodimitrakis К, Kummerer Н, Foglierini М, Серрано л (2006). «Шум в петлях отрицательной обратной связи транскрипции: моделирование и экспериментальный анализ» . Мол. Syst. Биол . 2 (1): 41. DOI : 10.1038 / msb4100081 . PMC 1681513 . PMID 16883354 .  
  53. ^ Shimoga В, Белый J, Li Y, Сонтаг Е, Bleris L (2013). «Синтетическая ауторегуляция трансгена млекопитающих» . Мол. Syst. Биол . 9 : 670. DOI : 10.1038 / msb.2013.27 . PMC 3964311 . PMID 23736683 .  
  54. ^ Maeda YT Сано M (июнь 2006). «Регуляторная динамика синтетических генных сетей с положительной обратной связью». J. Mol. Биол . 359 (4): 1107–24. DOI : 10.1016 / j.jmb.2006.03.064 . PMID 16701695 . 
  55. ^ Becskei A, B Серафин, Serrano L (май 2001). «Положительная обратная связь в эукариотических генных сетях: дифференциация клеток путем преобразования бинарного ответа» . EMBO J . 20 (10): 2528–35. DOI : 10.1093 / emboj / 20.10.2528 . PMC 125456 . PMID 11350942 .  
  56. ^ a b c Манган С., Алон У. (октябрь 2003 г.). «Структура и функция петли прямой связи» . Proc. Natl. Акад. Sci. США . 100 (21): 11980–5. Bibcode : 2003PNAS..10011980M . DOI : 10.1073 / pnas.2133841100 . PMC 218699 . PMID 14530388 .  
  57. ^ Ма HW, Кумар В, Ditges U, Gunzer Ж, Буэр Дж, Цзэн А.П. (2004). «Расширенная транскрипционная регуляторная сеть Escherichia coli и анализ ее иерархической структуры и сетевых мотивов» . Nucleic Acids Res . 32 (22): 6643–9. DOI : 10.1093 / NAR / gkh1009 . PMC 545451 . PMID 15604458 .  
  58. ^ Mangan S, Zaslaver A, Алон U (ноябрь 2003). «Связанная петля прямой связи служит чувствительным к знаку элементом задержки в сетях транскрипции». J. Mol. Биол . 334 (2): 197–204. CiteSeerX 10.1.1.110.4629 . DOI : 10.1016 / j.jmb.2003.09.049 . PMID 14607112 .  
  59. ^ Kalir S, Mangan S, Алон U (2005). «Связанная петля с прямой связью с функцией ввода СУММ продлевает экспрессию жгутиков у Escherichia coli » . Мол. Syst. Биол . 1 (1): E1 – E6. DOI : 10.1038 / msb4100010 . PMC 1681456 . PMID 16729041 .  
  60. ^ Сюн, Кун; Ланкастер, Алекс К .; Siegal, Mark L .; Масел, Джоанна (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, Алон U (март 2006). «Некогерентная петля с прямой связью ускоряет время отклика Gal-системы Escherichia coli ». J. Mol. Биол . 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, Сауро HM (август 2007). «Разработка и реализация трех биологических датчиков концентрации на основе некогерентных мотивов с прямой связью» . Syst Synth Biol . 1 (3): 119–28. DOI : 10.1007 / s11693-007-9008-6 . PMC 2398716 . PMID 19003446 .  
  63. Перейти ↑ Kaplan S, Bren A, Dekel E, Alon U (2008). «Некогерентная петля прямой связи может генерировать немонотонные входные функции для генов» . Мол. Syst. Биол . 4 (1): 203. DOI : 10.1038 / msb.2008.43 . PMC 2516365 . PMID 18628744 .  
  64. ^ a b Bleris L, Xie Z, Glass D, Adadey A, Sontag E, Benenson Y (2011). «Синтетические некогерентные цепи прямой связи демонстрируют адаптацию к количеству своего генетического шаблона» . Мол. Syst. Биол . 7 (1): 519. DOI : 10.1038 / msb.2011.49 . PMC 3202791 . PMID 21811230 .  
  65. ^ Калир S, МакКлюр Дж, Паббараджу К. и др. (Июнь 2001 г.). «Упорядочивание генов в пути жгутиков путем анализа кинетики экспрессии живых бактерий». Наука . 292 (5524): 2080–3. DOI : 10.1126 / science.1058758 . PMID 11408658 . S2CID 14396458 .  
  66. ^ Zaslaver А, Mayo А.Е., Розенберг Р. и др. (Май 2004 г.). «Своевременная программа транскрипции метаболических путей» . Nat. Genet . 36 (5): 486–91. DOI : 10.1038 / ng1348 . PMID 15107854 . 
  67. ^ Konagurthu AS, Lesk AM (2008). «Модули с одним и несколькими входами в регулирующих сетях». Белки . 73 (2): 320–324. DOI : 10.1002 / prot.22053 . PMID 18433061 . S2CID 35715566 .  
  68. ^ Каплан S, Брен A, Zaslaver A, E Dekel Алон U (март 2008). «Различные двумерные входные функции контролируют бактериальные гены сахара» . Мол. Cell . 29 (6): 786–92. DOI : 10.1016 / j.molcel.2008.01.021 . PMC 2366073 . PMID 18374652 .  
  69. ^ Чечик О, О , Е, Rando О, Вайсман Дж, Регев А, Д Коллер (ноябрь 2008 г.). «Мотивы активности раскрывают принципы времени в транскрипционном контроле метаболической сети дрожжей» . Nat. Biotechnol . 26 (11): 1251–9. DOI : 10.1038 / nbt.1499 . PMC 2651818 . PMID 18953355 .  
  70. ^ Браха, Д. (2020). Паттерны связей в сетях решения проблем и их динамические свойства . Научные отчеты, 10 (1), 1-22.
  71. Перейти ↑ X. Zhang, S. Shao, HE Stanley, S. Havlin (2014). «Динамические мотивы в социально-экономических сетях». Europhys. Lett . 108 (5): 58001. Bibcode : 2014EL .... 10858001Z . DOI : 10.1209 / 0295-5075 / 108/58001 .CS1 maint: multiple names: authors list (link)
  72. ^ Ingram PJ, Штумпф MP, Старк J (2006). «Сетевые мотивы: структура не определяет функцию» . BMC Genomics . 7 : 108. DOI : 10.1186 / 1471-2164-7-108 . PMC 1488845 . PMID 16677373 .  
  73. Перейти ↑ Voigt CA, Wolf DM, Arkin AP (март 2005 г.). « Оперон Bacillus subtilis sin: эволюционирующий сетевой мотив» . Генетика . 169 (3): 1187–202. DOI : 10.1534 / genetics.104.031955 . PMC 1449569 . PMID 15466432 .  
  74. ^ Кнабе JF, Nehaniv CL, Schilstra MJ (2008). «Отражают ли мотивы развитую функцию? - Нет конвергентной эволюции топологий подграфов генетической регуляторной сети». Биосистемы . 94 (1–2): 68–74. DOI : 10.1016 / j.biosystems.2008.05.012 . PMID 18611431 . 
  75. Перейти ↑ Taylor D, Restrepo JG (2011). «Подключение к сети во время слияний и роста: Оптимизация добавления модуля». Physical Review E . 83 (6): 66112. arXiv : 1102.4876 . Bibcode : 2011PhRvE..83f6112T . DOI : 10.1103 / PhysRevE.83.066112 . PMID 21797446 . S2CID 415932 .  
  76. ^ Konagurthu, Arun S .; Леск, Артур М. (23 апреля 2008 г.). «Модули с одним и несколькими входами в регулирующих сетях». Белки: структура, функции и биоинформатика . 73 (2): 320–324. DOI : 10.1002 / prot.22053 . PMID 18433061 . S2CID 35715566 .  
  77. ^ Konagurthu AS, Lesk AM (2008). «О происхождении закономерностей распределения мотивов в биологических сетях» . BMC Syst Biol . 2 : 73. DOI : 10,1186 / 1752-0509-2-73 . PMC 2538512 . PMID 18700017 .  
  78. ^ Браха, D., & Bar-Yam, Y. (2006). От центральности к временной известности: динамическое центральное положение в сложных сетях . Сложность, 12 (2), 59-63.
  79. ^ Браха Д., Бар-Ям Ю. (2009) Зависящие от времени сложные сети: динамическая центральность, динамические мотивы и циклы социальных взаимодействий . В: Гросс Т., Саяма Х. (ред.) Адаптивные сети. Понимание сложных систем. Шпрингер, Берлин, Гейдельберг

Внешние ссылки [ править ]

  • Программный инструмент, который может обнаруживать сетевые мотивы
  • bio-Physics-wiki СЕТЕВЫЕ МОТИВЫ
  • FANMOD: инструмент для быстрого обнаружения сетевых мотивов
  • MAVisto: инструмент анализа и визуализации сетевых мотивов
  • NeMoFinder
  • Грохов – Келлис
  • MODA
  • Кавош
  • ЦитоКавош
  • G-Tries
  • средство обнаружения acc-MOTIF