Надсемействa выделенных и спланированных сетей

Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Sher-Orr, Inbal Ayzenshtat, Michal Sheffer, Uri Alon

Сложные биологические, технологические и социологические сети могут быть очень разных размеров и иметь различную связность, что делает трудным сравнение их структур. Здесь мы представляем подход к системному изучению сходства в локальных структурах сетей, основанный на смысловом профиле (significance profile, ) мелких подграфов сети в сравнении со случайными сетями. Мы нашли надсемействa сетей, ранее не имеющих отношение друг к другу, с очень похожими . Одно надсемейство, включающее в себя сети транскрипций микроорганизмов, представляет сети с ограниченной скоростью обработки информации, которые сильно ограничены во времени отклика своих компонентов. Другое надсемейство включает в себя сети оповещения протеинов, связанные с развитием генов, и нейронных схем. Еще есть надсемействa, включающие в себя сети энергосистемы, сети структур протеинов, геометрические сети, сеть Всемирной Паутины, социальные сети и сети связности слов на разных языках.

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

Для понимания принципов построения сложных сетей, важно сравнить локальные структуры сетей из различных областей. Основной трудностью является то, что эти сети могут быть очень разных размеров (например, сеть Всемирной Паутины (WWW) с миллионами узлов и социальные сети с десятками узлов) и иметь очень разные степенные последовательности. Здесь мы представляем подход для сравнения локальных структур сетей, который базируется на (significance profile). Для расчета сети, сеть сравнивается с ансамблем случайных сетей, которые имеют ту же степенную последовательностью. Сравнение со случайными сетями компенсирует эффекты, обусловленные размером сети и степенной последовательностью. Для каждого подграфа статистическая значимость описывается посредством показателя :

где - это число появлений -того подграфа в сети, - это среднее значение появлений -того подграфа в ансамбле случайных сетей, а - это стандартное отклонение появлений -того подграфа в ансамбле случайных сетей. – это вектор показателей , нормированных по длине 1:

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

На Рис.1 мы представляем 13 возможных триад направленных связей (triad significance profile, ) для сетей из различных областей. этих сетей почти всегда нечувствительны к удалению 30% ребер или к добавлению 50% новых ребер случайным образом, этим демонстрируя, что является устойчивым к потере данных или к случайным ошибкам в данных (SOM Text).

Рис.1. для сетей из различных областей.

показывает нормированные показатели для каждого из 13 триад. Сети с аналогичными сгруппированы в надсемейства. Линии, соединяющие смысловые значения служат руководством для глаз. Рассмотрены следующие сети (N и E являются количеством узлов и ребер соответственно): (i) Прямые транскрипции взаимодействий в бактерии кишечной палочки (TRANSC-E.COLI N = 424, E = 519), бацилле 'subtilis' (TRANSC-B.SUBTILIS N = 516, E = 577) и дрожжи сахаромицетов (TRANC-YEAST N = 685, E = 1052 и TRANC-YEAST-2 N = 2341, E = 3969). (ii) Отношение сигнал трансдукции взаимодействий в клетках млекопитающих, основанной на знаниях трансдукции сигнала окружающей среды (SIGNAL-TRANSDUCTION N = 491, E = 989), сети транскрипций, которые определяют развитие плодовой мухи (TRANSC-DROSOPHILA N = 110, E = 307), развитие морского ежа (TRANSC-SEAURCHIN N = 45, E = 83), и синаптических связей между нейронами (NEURONS N = 280, E = 2170). (iii) WWW гиперссылки между страницами в сайте www.nd.edu (WWW-1 N = 325729, E = 1469678 ), страницы с информацией по литературоведению Шекспира (WWW-2 N = 277114, E = 927400), а также страницы, связанные с танго, с конкретно музыкой Пьяццолло (WWW-3 N = 47870, E = 235441); и социальных сетей, в том числе людей, заключенных в тюрьмах (SOCIAL-1 N = 67, E = 182), первокурсников (SOCIAL-2 N = 28, E = 110), и студентов в курсе о лидерстве (SOCIAL-3 N = 32, E = 96). (IV), сети связности слов в тексте на английском языке (ENGLISH N = 7724, E = 46281), французском (FRENCH N = 9424, E = 24295), испанском (SPANISH N = 12642, E = 45129), японском (JAPANESE N = 3177, E = 8300) и сеть двусторонней модели графа с двумя группами узлов размерами N1 = 1000 и N2 = 10, для которых вероятность появления направленного ребра между узлами различных групп P = 0,06 и Q = 0,003 соответственно, и нет ребер между узлами в пределах одной и той же группы (BIPARTITE N = 1010, E = 1261).

Из этих анализов появляются некоторые надсемейства сетей с аналогичными . Одно надсемейство включает в себя сети сенсорной транскрипции (считывание генетического кода), которые контролируют выражение гена в бактериях и в дрожжи в ответ на внешние стимуляции. В этих сетях транскрипций узлами являются гены или опероны (генетическая функциональная единица), а ребрами являются прямые транскрипционные нормы. Были проанализированы сети из трех микроорганизмов: бактерий кишечной палочки, бацилл 'subtilis' и дрожжей сахаромицетов (род дрожжевых грибов). Эти сети имеют очень похожие (коэффициент корреляции). Они выявляют один сильный фрагмент, триаду под номером 7, которая называется “многомерной петлей”. Эти многомерные петли рассматриваются теоретически и экспериментально для выполнения задач обработки сигналов, таких, как выявление персистенций, генерация импульсов, ускорение транскрипционных ответов. Триада под номером 3, является анти - фрагментом (в значительно низкой степени представленный подграф), соответствующим поверхностной архитектуре этих сетей, которые имеют мало длинных каскадов. Эти сети являются "сенсорными сетями", для которых необходимо иметь отклик в течении минуты для кратковременных сигналов, таких как стрессы и питательные вещества. Минимальное время, необходимое для отклика (для первых протеинов, которые будут выданы) должен быть порядка минуты. Если информация должна пройти дополнительные шаги (регулятор протеина должен быть выдан и скрещен с началом ее активации для включения гена), то время отклика намного дольше. Экспериментальным и теоретическим путем показано, что время отклика на каждом каскадном шаге должна быть порядка продолжительности жизни ген продукта, что часто длится в десятки минут. Таким образом, эти сети являются "сетями с ограниченной скоростью" (“rate-limited networks”), в которых эталонное (желаемое) время отклика соизмерима с коротким временем отклика сетевых компонентов.

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

Мы нашли различные надсемейства, которые включают три вида биологической сетей: сеть сигналов трансдукций взаимодействия в клетках млекопитающих, основанных на Signal Transduction Knowledge Environment (STKE), сеть развития транскрипций, которые ведут развитие плодовой мушки, морского ежа, и сеть синаптической проводки между нейронов в 'Caenorhabditis elegans'. Эти сети показывают триады 7, 9 и 10 с положительными , и триады 1, 2, 4 и 5 с негативными (Рис.1). В отличие от сетей с сенсорной транскрипцией микроорганизмов, эти сети выявляют двух узловые обратные связи, которые регулируют или регулируются третьим узлом (триады 10, 9), и менее наклонны к каскадам (триада 3). Общей чертой этого надсемейства информационных сетей (information – processing networks) является то, что время отклика на каждом шаге, как правило, значительно короче, чем требуемое время отклика для биологических функций сети. Сети протеинов трансдукции сигнала часто нуждаются в отклике в течение часа или больше, но каждое взаимодействие может занять несколько минут или меньше. Шаги каскада в развивающих сетях может иметь время отклика в десятки минут, но контролирующие их процессы происходят гораздо медленнее, упорядочение животных по клеточному делению, может занять несколько часов. Для нейронных сетей, как правило, необходим отклик в течение одной секунды, но время отклика нейрона короче, чем 100 мс. Таким образом, показано, что это надсемейство представляет биологические информационные сети, которые не являются сетями с ограниченной скоростью.

Далее, мы проанализировали три сети WWW гиперссылок между Web -страницами, связанные с университетом, литературой или музыкой. были очень похожи ( до ). Триады 9, 10, 12 и 13 имели самые высокиe значения, a 4, 5 и 6 - самые низкиe. В высокой степени представленные триады имеют много тройных транзитивных взаимодействий, где если и , то . Например, триада 13, которая называется "клик", имеет шесть транзитивных взаимодействий, что является самой высокой возможной транзитивностью в триаде. В более низкой степени представленные триады 6, 8 и 11 являются сильно не транзитивными.

Мы также проанализировали три социальные сети, в которых узлами являются люди в группе, а ребрами - позитивный настрой одного члена группы к другому, основанный на вопросах анкет. трех социальных сетей были очень похожи ( до ). Примечательно то, что их были довольно близки к сети WWW ( до 0,9). Это предполагает, что сети WWW и социальные сети могут быть частью надсемейства. Тенденция социальных сетей к выявлению транзитивных взаимодействий и транзитивных триад хорошо установлена. Сходство WWW и социальных сетей показывает, что классические модели социальной структурной организации также могут быть использованы для понимания структуры WWW.

Тексты также могут быть представлены в виде сетей. Мы изучили сети связности слов, в которых каждый узел представляет собой слово, а направленная связь возникает, когда одно слово непосредственно следует за другим в текст. текстов на различных языках и различных размеров близки (Рис.1 сравнивает тексты на английском, французском, испанском и японском языках). Основной отличительной особенностью является низкий степень представления треугольно-образных триад под номерами 7 до 13. Это связано со структурой языков, в которых слова принадлежат категориям, а слова из одной категории, как правило, последуют словам из другой категории. Например, наиболее связанными словами являются предлоги, которые обычно используются с существительным. Рис.1 показывает также для сети двусторонней модели графа, в котором узлы принадлежат к двум группам, и связи образуются между этими группами, а не в рамках группы. Сеть двусторонней модели графа показывает близкий к сетей связности слов в языках.

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

демонстрируют определенные консервативные отношения между типами подграфов. Например, сети с избытком треугольно-образных триад как правило, имеют дефицит в V-образных триад. Мы обнаружили, что существует несколько правил сохранения триад в сетях, которые сохраняют степень последовательности из одиночных и смежных ребер (SOM Text). В результате, 13 значений определяются лишь семью степенями свободы. Интуитивно можно интерпретировать эти законы сохранения с точки зрения реакций, которые конвертируют V-образные подграфы в треугольно-образные, сохраняя степени всех участвующих узлов. Анализ этих реакций, протекающих в каждой сети, позволяет компактно описать разницу между сетями и их случайными дубликатами (Текст SOM).

Рис.2. Матрица коэффициентов корреляции для направленных сетей из Рис.1.

Теперь рассмотрим ненаправленные сети, в которых ребра не имеют направление. Поскольку ненаправленные сети могут иметь только два типа триад (V и треугольник), мы проанализировали профили шести типов тетрад ненаправленных связей (четырех узловые подграфы). В отличие от триад, нормированный показатель для тетрад показывает значительную зависимость от размера сети. Таким образом, вместо , который базируется на показателе , мы используем распространенность для каждого подграфа относительно случайных сетей:

где гарантирует, что || не сильно сбивается, когда данный подграф редко появляется как в реальной сети, так и в случайных сетях (здесь = 4). (subgraph ratio profile) – это вектор нормированный к длине 1:

Ненаправленная сеть представляющая энергосистему запада США выявил с высокой степенью представления тетрад 3, 4, 5 и 6 (Рис.3). Ненаправленная сеть структуры протеина, где узлы - это элементы вторичных структур ( спирали и нити), и два узла связаны, если их расстояние меньше 10A, имеет аналогичные с высокой степенью представления тетрад 3, 5 и 6. Мы сравнили эти сети для моделирования сетей, в которых связи определяются на решетке (lattice) геометрических соседей. В этих геометрически ограниченных сетях узлы выстраиваются на решетке (линия в одном измерении, плоскость в двух измерениях и т.д.). Точки, которые на решетке расположены ближе, чем на расстояние , связаны с вероятностью . Точки расположенные на большем расстоянии, чем , несвязанны. В результате распределения подграфов в этих сетях и соответствующих им случайных сетях могут быть аналитически рассчитаны. Мы нашли хорошее совпадение между сети структуры протеинов, сети энергосистемы и соответствующими геометрическим моделям с тем же числом узлов, ребер и коэффициента кластеризации (Рис.3).

Рис.3. для разных ненаправленных сетей.

Рассматриваются следующие сети: (I) Энергосистема запада США (Power-Grid N = 4941, Е = 6594) и геометрическая модель с тем же коэффициентом кластеризации (GEO-MODEL-PG N = 5000, Е = 7499). (II) Сети элементов вторичных структур для нескольких крупных протеинов; 1A4J, иммуноглобулин (PROTEIN-STRUCTURE-1 N = 95, Е = 213); 1EAW, серин ингибитор протеазы (PROTEIN-STRUCTURE-2 N = 53, Е = 123); 1AOR, оксидоредуктаза (PROTEIN-STRUCTURE-3 N = 99, Е = 212)] и геометрическая модель с тем же коэффициентом кластеризации (GEO-MODEL-PS N = 53, Е = 136). (III) Интернет на уровне автономной системы (AUTONOMOUS-SYSTEMS-1 до -6, N = 3015, 3522, 4517, 5357, 7956, 10515; E = 5156, 6324, 8376, 10328, 15943, 21455). (IV) Сети, которые растут в соответствии с BA моделью с m = 1 или m = 10 ребер для каждой новой вершины (BA m = 1, 10; N = 1000, 3000, 1000, 3000; E =1000, 3000, 9901, 29901).

Отдельное семейство было найдено для сети Интернета на уровне ненаправленных связей между автономными системами (AS, которые содержат группы компьютеров, внутри которых сети управляются локально, и между которыми данные передвигаются в рамках глобального Интернета). Мы изучили примеры структур AS сетей в различные моменты времени с 1997 по 2001 год. для AS сетей были аналогичны, несмотря на их разные размеры. Мы нашли, что этих сетей очень отличается от геометрически ограниченных надсемейств, тем, что имеют низкий степень представления тетрад 2, 3 и 4 и высокий степень представления тетрады 5.

Наконец, мы изучили модель Barabasi и Альберта (BA), которая широко используется для изучения эволюции сетей. В модели BA, ненаправленные сети растут, соединяя каждый новый узел с существующими. Мы нашли, что этих сетей (Рис.3) имеет разные формы для , и больших . Это происходит потому, что не все тетради могут быть созданы для или . Таким образом, данный подход может использоваться для изучения модельных сетей, и позволяет сравнивать их локальные структуры с системами реального мира.

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

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

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