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

редактировать

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

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

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

Содержание

1 Классическая модель
- 1.1 Аттракторы
2 Стабильность
3 Варианты модели
- 3.1 Другое топологии
- 3.2 Другие схемы обновления
4 Применение логических сетей
- 4.1 Классификация
5 См. также
6 Ссылки
7 Внешние ссылки

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

A Логическая сеть - это особый вид последовательной динамической системы, в которой время и состояния дискретны, т.е. как набор переменных, так и набор состояний во временном ряду имеют биекцию на целочисленный ряд. Такие системы похожи на клеточные автоматы в сетях, за исключением того факта, что при их настройке каждый узел имеет правило, которое случайным образом выбирается из всех 2 возможных с K входами. При K = 2 поведение класса 2 имеет тенденцию преобладать. Но для K>2 наблюдаемое поведение быстро приближается к типичному для случайного отображения, в котором сеть, представляющая эволюцию двух состояний N нижележащих узлов, сама соединена по существу случайным образом.

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

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

Аттракторы

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

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

Автор	Год	Средняя длина аттрактора	Среднее число аттрактора	комментарий
Кауфманн	1969	$⟨A⟩ ∼ N {\ displaystyle \ langle A \ rangle \ sim {\ sqrt {N}}}$ $\ langle A \ rangle \ sim {\ sqrt {N}}$	$⟨ν⟩ ∼ N {\ displaystyle \ langle \ nu \ rangle \ sim {\ sqrt {N}}}$ $\ langle \ nu \ rangle \ sim {\ sqrt {N}}$
Бастолла / Паризи	1998	быстрее, чем степенной закон, $⟨A⟩>N x ∀ x {\ displaystyle \ langle A \ rangle>N ^ {x} \ forall x}$ $\langle A\rangle>N ^ {x} \ forall x$	быстрее, чем степенной закон, $⟨ν⟩>N x ∀ x {\ displaystyle \ langle \ nu \ rangle>N ^ { x} \ forall x}$ $\langle \nu \rangle>N ^ {x} \ forall x$	первые числовые свидетельства
Bilke / Sjunnesson	2002		линейный с размером системы, $⟨ν⟩ ∼ N {\ displaystyle \ langle \ nu \ rangle \ sim N}$ $\ langle \ ню \ rangle \ sim N$
Socolar / Kauffman	2003		быстрее линейного, $⟨ν⟩>N x {\ displaystyle \ langle \ nu \ rangle>N ^ {x}}$ $\langle \nu \rangle>N ^ {x}$ с $x>1 {\ displaystyle x>1}$ $x>1$
Самуэльссон / Тройн	2003		суперполиномиальный рост, $⟨ν⟩>N x ∀ x {\ displaystyle \ langle \ nu \ rangle>N ^ {x} \ forall x}$ $\langle \nu \rangle>N ^ {x} \ forall x$	математическое доказательство
Mihaljev/Drossel	2005	быстрее, чем закон мощности, $⟨A⟩>N x ∀ x {\ displaystyle \ langle A \ rangle>N ^ {x} \ forall x}$ $\langle A\rangle>N ^ {x} \ forall x$	быстрее, чем закон мощности, $⟨ν ⟩>N x ∀ x {\ displaystyle \ langle \ nu \ rangle>N ^ {x} \ forall x}$ $\langle \nu \rangle>N ^ {x} \ forall x$

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

В теории динамических систем структура и длина Аттракторы сети соответствуют динамической фазе сети. Стабильность булевых сетей зависит от соединений их узлов. Логическая сеть может демонстрировать стабильное, критическое или хаотическое поведение. Это явление определяется критическим значением среднего числа соединений узлов ( $K c {\ displaystyle K_ {c}}$ ${\ displaystyle K_ {c}}$ ) и может быть охарактеризовано расстоянием Хэмминга как мера расстояния. В нестабильном режиме расстояние между двумя изначально близкими состояниями в среднем растет во времени по экспоненте, а в устойчивом - по экспоненте. В этом случае термин «изначально близкие состояния» означает, что расстояние Хэмминга мало по сравнению с количеством узлов ( $N {\ displaystyle N}$ $N$ ) в сети.

Для NK-модели сеть стабильна, если $K < K c {\displaystyle K$ ${\ displaystyle K <K_ {c}}$ , критична, если $K = K c {\ displaystyle K = K_ {c}}$ ${\ displaystyle K = K_ {c}}$ , и нестабильный, если $K>K c {\ displaystyle K>K_ {c}}$ $K>K_ {c}$ .

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

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

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

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

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

Варианты модели

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

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

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

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

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

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

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

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

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

См. также

модель NK

Литература

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

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