Логическая сеть

Пространство состояний булевой сети с N=4 узлами и K=1 ссылками на узел. Узлы могут быть включены (красный) или выключены (синий). Тонкие (черные) стрелки символизируют входные данные булевой функции , которая представляет собой простую функцию копирования для каждого узла. Толстые (серые) стрелки показывают, что делает синхронное обновление. Всего имеется 6 (оранжевых) аттракторов , 4 из них — неподвижные точки .

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

Булевы сети использовались в биологии для моделирования регуляторных сетей. Хотя логические сети представляют собой грубое упрощение генетической реальности, где гены не являются простыми двоичными переключателями, в нескольких случаях они правильно передают правильную структуру экспрессируемых и подавляемых генов. Казалось бы, математическая простая (синхронная) модель была полностью понята только в середине 2000-х годов.

Классическая модель

Булева сеть — это особый вид последовательной динамической системы , в которой время и состояния дискретны, т. е. и набор переменных, и набор состояний во временных рядах имеют биекцию в целочисленный ряд.

Случайная булева сеть (RBN) — это сеть, которая случайным образом выбирается из набора всех возможных логических сетей определенного размера N . Тогда можно статистически изучить, как ожидаемые свойства таких сетей зависят от различных статистических свойств ансамбля всех возможных сетей. Например, можно изучить, как меняется поведение RBN при изменении среднего уровня связности.

Первые логические сети были предложены Стюартом А. Кауфманом в 1969 году как случайные модели генетических регуляторных сетей . но их математическое понимание началось только в 2000-х годах.

Аттракторы

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

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

Автор	Год	Средняя длина аттрактора	Среднее число аттрактора	комментарий
Кауфман	1969	$\langle A\rangle \sim {\sqrt {N}}$	$\langle \nu \rangle \sim {\sqrt {N}}$
Бастолла/ Париж	1998	быстрее, чем степенной закон, $\langle A\rangle >N^{x}\forall x$	быстрее, чем степенной закон, $\langle \nu \rangle >N^{x}\forall x$	первые числовые доказательства
Билке/ Сюннессон	2002		линейная в зависимости от размера системы, $\langle \nu \rangle \sim N$
Соколар/Кауфман	2003		быстрее линейного, $\langle \nu \rangle >N^{x}$ с $x>1$
Самуэльссон/Тройн	2003		суперполиномиальный рост, $\langle \nu \rangle >N^{x}\forall x$	математическое доказательство
Михальев/Дроссель	2005	быстрее, чем степенной закон, $\langle A\rangle >N^{x}\forall x$	быстрее, чем степенной закон, $\langle \nu \rangle >N^{x}\forall x$

Стабильность

В теории динамических систем структура и длина аттракторов сети соответствуют динамической фазе сети. Устойчивость булевых сетей зависит от связей их узлов . Булева сеть может демонстрировать стабильное, критическое или хаотическое поведение . Это явление определяется критическим значением среднего числа связей узлов ( $K_{c}$), и может быть охарактеризовано расстоянием Хэмминга как мерой расстояния. В неустойчивом режиме расстояние между двумя изначально близкими состояниями в среднем растет экспоненциально во времени, а в устойчивом режиме экспоненциально уменьшается. При этом под «изначально близкими состояниями» подразумевается, что расстояние Хэмминга мало по сравнению с числом узлов ( $N$) в сети.

Для модели НК сеть стабильна, если $K<K_{c}$, критично, если $K=K_{c}$и неустойчив, если $K>K_{c}$.

Состояние данного узла $n_{i}$ обновляется в соответствии со своей таблицей истинности , выходные данные которой заполняются случайным образом. $p_{i}$ обозначает вероятность назначения выключенного выхода данной серии входных сигналов.

Если $p_{i}=p=const.$ для каждого узла переход между стабильным и хаотичным диапазоном зависит от $p$. По мнению Бернара Деррида и Ива Помо. , критическое значение среднего числа связей равно $K_{c}=1/[2p(1-p)]$.

Если $K$ не является постоянной, и нет никакой корреляции между входящими и выходными степенями, условия устойчивости определяются $\langle K^{in}\rangle$ Сеть стабильна, если $\langle K^{in}\rangle <K_{c}$, критично, если $\langle K^{in}\rangle =K_{c}$и неустойчив, если $\langle K^{in}\rangle >K_{c}$.

Условия устойчивости одинаковы в случае сетей с безмасштабной топологией , где распределение по степени входа и выхода является степенным: $P(K)\propto K^{-\gamma }$, и $\langle K^{in}\rangle =\langle K^{out}\rangle$, поскольку каждая исходящая ссылка от узла является внутренней ссылкой на другой.

Чувствительность показывает вероятность того, что выходные данные булевой функции данного узла изменятся, если изменяются ее входные данные. Для случайных логических сетей $q_{i}=2p_{i}(1-p_{i})$. В общем случае устойчивость сети определяется наибольшим собственным значением $\lambda _{Q}$ матрицы $Q$, где $Q_{ij}=q_{i}A_{ij}$, и $A$ – матрица смежности сети. Сеть стабильна, если $\lambda _{Q}<1$, критично, если $\lambda _{Q}=1$, неустойчив, если $\lambda _{Q}>1$.

Вариации модели

Другие топологии

Одной из тем является изучение различных базовых топологий графов .

• Однородный случай просто относится к сетке, которая является просто сокращением знаменитой модели Изинга .
• Для логических сетей могут быть выбраны безмасштабные топологии. Можно выделить случай, когда распределение по степеням распределяется только по степеням, или только распределение по исходящей степени, или и то, и другое.

Другие схемы обновления

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

• Детерминированные асинхронно обновляемые логические сети ( DRBN ) не обновляются синхронно, но детерминированное решение все еще существует. Узел i будет обновлен, когда t ≡ Q _i ( mod P _i ), где t — временной шаг.
• Самый общий случай — полное стохастическое обновление ( GARBN , общие асинхронные случайные логические сети). Здесь один (или несколько) узлов выбираются на каждом вычислительном этапе для обновления.
• Частично наблюдаемая булева динамическая система (POBDS) Модель сигнала отличается от всех предыдущих детерминистических и стохастических моделей булевых сетей тем, что устраняет предположение о прямой наблюдаемости булевого вектора состояния и допускает неопределенность в процессе наблюдения, рассматривая сценарий, встречающийся на практике.
• Автономные логические сети ( ABN ) обновляются непрерывно ( t — действительное, а не целое число), что приводит к состояниям гонки и сложному динамическому поведению, такому как детерминированный хаос.

Применение логических сетей

Классификация

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

См. также

• Модель НК

Ссылки

• Дуброва Е., Тесленко М., Мартинелли А. (2005). * Сети Кауфмана: анализ и приложения , в «Материалах международной конференции по автоматизированному проектированию», страницы 479-484.

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

• Анализ динамических алгебраических моделей (ADAM) v1.1
• bioasp/bonesis : синтез наиболее разрешительных логических сетей на основе сетевой архитектуры и динамических свойств.
• CoLoMoTo (Консорциум логических моделей и инструментов)
• ДДЛаб
• Симулятор логических сетей NetBuilder
• Симулятор логической сети с открытым исходным кодом
• JavaScript Сеть Кауфмана
• Вероятностные логические сети (PBN)
• РБНЛаб
• Инструмент на основе SAT для вычисления аттракторов в логических сетях.