Булева мережа складається з дискретного набору булевих змінних, кожній з яких призначено булеву функцію (можливо, різну для кожної змінної), яка приймає вхідні дані від підмножини цих змінних та вихідні дані, що визначають стан змінної, якій вона призначена. Цей набір функцій фактично визначає топологію (зв'язність) на наборі змінних, які потім стають вузлами в мережі. Зазвичай динаміка системи розглядається як дискретний часовий ряд, де стан усієї мережі в момент часу t +1 визначається шляхом оцінки функції кожної змінної щодо стану мережі в момент часу t. Це може бути зроблено синхронно або асинхронно.

Булеві мережі використовуються в біології для моделювання регуляторних мереж. Хоча вони є суттєвим спрощенням генетичної реальності, оскільки гени не функціонують як прості бінарні перемикачі, існує низка випадків, у яких такі моделі коректно відтворюють характер експресії та пригнічення генів. Попри математичну простоту синхронної моделі, її властивості були повною мірою зрозумілі лише в середині 2000-х років.

Класична модель Булева мережа — це особливий вид послідовної динамічної системи, де час і стани є дискретними, тобто як набір змінних, так і набір станів у часовому ряді мають бієкцію на цілочисельний ряд.

Випадкова булева мережа (, RBN) — це мережа, випадковим чином вибрана з множини всіх можливих булевих мереж заданого розміру N. Це дає змогу статистично досліджувати, як очікувані властивості таких мереж залежать від різних статистичних характеристик ансамблю всіх можливих мереж. Наприклад, можна аналізувати, як змінюється поведінка випадкової булевої мережі зі зміною її середньої зв’язності.

Перші булеві мережі були запропоновані Стюартом Кауфманом у 1969 році як випадкові моделі генетичних регуляторних мереж.

Атрактори Оскільки булева мережа має лише 2N можливих станів, її траєкторія рано чи пізно досягне одного з уже відвіданих станів. Внаслідок детермінованого характеру динаміки після цього траєкторія переходить у стаціонарний стан або цикл, який називається атрактором (хоча в загальній теорії динамічних систем цикл вважається атрактором лише тоді, коли збурення від нього приводять систему назад до нього).

Якщо атрактор складається лише з одного стану, його називають точковим атрактором, а якщо він містить більше ніж однин стан — циклічним атрактором. Сукупність станів, що приводять до певного атрактора, називається його басейном притягання. Стани, які можуть виникати лише на початку траєкторій (тобто до яких не веде жодна траєкторія), називаються станами райського саду. Динаміка мережі переходить від цих станів до відповідних атракторів. Час, необхідний для досягнення атрактора, називається перехідним часом.

Зі зростанням потужності комп'ютерів та поглибленим розумінням, здавалося б, простої моделі, різні автори давали різні оцінки середньої кількості та довжини атракторів. Ось короткий огляд ключових публікацій. АвторРікСередня довжина атрактораСереднє число атракторівКоментарКауфман1969Бастола/Парісі1998швидше, ніж за степеневим законом, швидше, ніж за степеневим законом, перші чисельні доказиБілке/ С'юннесон2002лінійно залежить від розміру системи, Соколар/Кауфман2003швидше, ніж за степеневим законом, with Семюелсон/Троеін2003суперполіноміальне зростання, математичне доведенняМіхальєв/Дроссель2005швидше, ніж за степеневим законом, швидше, ніж за степеневим законом, Фінк/Шелдон2023експоненційне зростання, математичне доведення

Стабільність У теорії динамічних систем структура та довжина атракторів мережі відповідають динамічній фазі мережі. Стабільність булевих мереж залежить від зв'язків їхніх вузлів. Булева мережа може демонструвати стабільну, критичну або хаотичну поведінку.

Це явище визначається критичним значенням середньої кількості зв'язків вузлів (), і може бути охарактеризована відстанню Хеммінга як мірою відстані. У нестабільному режимі відстань між двома спочатку близькими станами в середньому зростає експоненціально з часом, тоді як у стабільному режимі вона експоненціально зменшується. У цьому випадку під "спочатку близькими станами" мається на увазі, що відстань Хеммінга мала порівняно з кількістю вузлів () у мережі.

Для N-K-моделі мережа є стабільною, якщо , критично, якщо , і нестабільний, якщо .

Стан заданого вузла оновлюється відповідно до своєї таблиці істинності, виходи якої заповнюються випадковим чином.

позначає ймовірність призначення вимкненого виходу заданій послідовності вхідних сигналів.

Якщо для кожного вузла перехід між стабільним та хаотичним діапазоном залежить від Згідно з Бернаром Дерріда та Івом Помо, критичне значення середньої кількості з'єднань становить .

Якщо не є постійною величиною, і немає кореляції між вхідними та вихідними ступенями, умови стійкості визначаються як Мережа є стабільною, якщо , критично, якщо , і нестабільний, якщо .

Умови стійкості однакові у випадку мереж з безмасштабною топологією, де розподіл вхідних та вихідних ступенів є степеневим розподілом: , та , оскільки кожне вихідне посилання з одного вузла є внутрішнім посиланням на інший.

Чутливість показує ймовірність того, що вихід булевої функції заданого вузла зміниться, якщо зміниться його вхід. Для випадкових булевих мереж, .

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

Варіації моделі

Інші топології Одна з тем полягає у вивченні різних базових топологій графів.

Однорідний випадок просто стосується сітки, яка є просто редукцією до відомої моделі Ізінга; Для булевих мереж можна обрати безмасштабні топології. Можна розрізнити випадок, коли розподілений лише розподіл в межах степеня, або лише розподіл поза степенем, або обидва.

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

Детерміновані асинхронно оновлювані булеві мережі (DRBN) не оновлюються синхронно, але детермінований розв'язок все ще існує. Вузол i буде оновлено, коли t ≡ Qi (mod Pi), де t – крок за часом/ Найзагальнішим випадком є повне стохастичне оновлення (GARBN, загальні асинхронні випадкові булеві мережі). Тут на кожному обчислювальному кроці вибирається один (або декілька) вузлів для оновлення. Модель сигналу частково спостережуваної булевої динамічної системи (POBDS) відрізняється від усіх попередніх детермінованих та стохастичних моделей булевих мереж тим, що виключає припущення про пряму спостережуваність булевого вектора стану та допускає невизначеність у процесі спостереження, що враховує сценарій, що зустрічається на практиці. Автономні булеві мережі (ABN) оновлюються в безперервному часі (t – дійсне число, а не ціле), що призводить до умов гонки та складної динамічної поведінки, такої як детермінований хаос.

Застосування булевих мереж

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

Масштабована оптимальна баєсівська класифікаціяHajiramezanali, E. & Imani, M. & Braga-Neto, U. & Qian, X. & Dougherty, E.. Scalable Optimal Bayesian Classification of Single-Cell Trajectories under Regulatory Model Uncertainty. ACMBCB'18. https://dl.acm.org/citation.cfm?id=3233689 розробила оптимальний метод класифікації траєкторій із урахуванням потенційної невизначеності моделі, а також запропонувала класифікацію траєкторій на основі частинок, яка має високу масштабованість для великих мереж і значно меншу обчислювальну складність порівняно з оптимальним рішенням.

Посилання

Дуброва, Е., Тесленко, М., Мартінеллі, А., (2005). *Мережі Кауфмана: аналіз та застосування, у «Матеріалах Міжнародної конференції з автоматизованого проектування», с. 479—484.

Зовнішні посилання

Аналіз динамічних алгебраїчних моделей (ADAM) версії 1.1 bioasp/bonesis: Синтез найбільш пермісивних булевих мереж з архітектури мережі та динамічних властивостей CoLoMoTo (Консорціум логічних моделей та інструментів) DDLab Симулятор булевих мереж NetBuilder Симулятор булевої мережі з відкритим кодом Мережа Кауфмана на JavaScript Ймовірнісні булеві мережі (PBN) RBNLab Інструмент на основі SAT для обчислення атракторів у булевих мережах