Булева сеть

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

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

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

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

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

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

Аттракторы

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

С ростом вычислительной мощности и улучшением понимания, казалось бы, простой модели, разные авторы давали разные оценки среднего числа и длины аттракторов. Ниже приводится краткий обзор основных публикаций. ^[9]

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

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

Для NK-модели ^[15] сеть устойчива, если , критична, если , и неустойчива, если . $K<K_{c}$ $K=K_{c}$ $K>K_{c}$

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

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

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

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

Чувствительность показывает вероятность того, что выход булевой функции данного узла изменится, если изменится его вход. Для случайных булевых сетей . В общем случае устойчивость сети определяется наибольшим собственным значением матрицы , где , а — матрица смежности сети. ^[21] Сеть устойчива, если , критична, если , неустойчива, если . $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$

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

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

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

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

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

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

Детерминированные асинхронно обновляемые булевы сети ( DRBN s) не обновляются синхронно, но детерминированное решение все еще существует. Узел i будет обновлен, когда t ≡ Q _i ( mod P _i ), где t — временной шаг. ^[26]
Наиболее общим случаем является полное стохастическое обновление ( GARBN , общие асинхронные случайные булевы сети). Здесь на каждом вычислительном шаге выбирается один (или несколько) узлов для обновления.
Модель сигнала частично наблюдаемой булевой динамической системы (POBDS) ^[27]^[28]^[29]^[30] отличается от всех предыдущих детерминированных и стохастических моделей булевых сетей тем, что устраняет предположение о прямой наблюдаемости вектора булевого состояния и допускает неопределенность в процессе наблюдения, рассматривая сценарий, встречающийся на практике.
Автономные булевы сети ( ABN ) обновляются в непрерывном времени ( t — действительное число, а не целое), что приводит к условиям гонки и сложному динамическому поведению, такому как детерминированный хаос. ^[31]^[32]

Применение булевых сетей

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

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

Смотрите также

Модель НК

Ссылки

^ Naldi, A.; Monteiro, PT; Mussel, C.; Kestler, HA; Thieffry, D.; Xenarios, I.; Saez-Rodriguez, J.; Helikar, T.; Chaouiya, C. (25 января 2015 г.). «Совместная разработка стандартов и инструментов логического моделирования с CoLoMoTo». Биоинформатика . 31 (7): 1154–1159. doi : 10.1093/bioinformatics/btv013 . PMID 25619997.
^ Альберт, Река; Отмер, Ханс Г (июль 2003 г.). «Топология регуляторных взаимодействий предсказывает паттерн экспрессии генов сегментной полярности у Drosophila melanogaster». Журнал теоретической биологии . 223 (1): 1–18. arXiv : q-bio/0311019 . Bibcode : 2003JThBi.223....1A. CiteSeerX 10.1.1.13.3370 . doi : 10.1016/S0022-5193(03)00035-3. PMC 6388622. PMID 12782112 .
^ Li, J.; Bench, AJ; Vassiliou, GS; Fourouclas, N.; Ferguson-Smith, AC; Green, AR (30 апреля 2004 г.). «Импринтинг гена L3MBTL человека, члена семейства поликомб, расположенного в области хромосомы 20, удаленной при миелоидных злокачественных новообразованиях человека». Труды Национальной академии наук . 101 (19): 7341–7346. Bibcode : 2004PNAS..101.7341L. doi : 10.1073 /pnas.0308195101 . PMC 409920. PMID 15123827.
^ ab Drossel, Barbara (декабрь 2009 г.). "Случайные булевы сети". В Schuster, Heinz Georg (ред.). Глава 3. Случайные булевы сети . Обзоры нелинейной динамики и сложности. Wiley. стр. 69–110. arXiv : 0706.3351 . doi :10.1002/9783527626359.ch3. ISBN 9783527626359. S2CID 119300231.
^ ab Кауфман, Стюарт (11 октября 1969 г.). «Гомеостаз и дифференциация в случайных генетических сетях управления». Nature . 224 (5215): 177–178. Bibcode :1969Natur.224..177K. doi :10.1038/224177a0. PMID 5343519. S2CID 4179318.
^ Aldana, Maximo; Coppersmith, Susan ; Kadanoff, Leo P. (2003). "Булевская динамика со случайными связями". Перспективы и проблемы в нелинейной науке: праздничный том в честь Лоуренса Сировича . стр. 23–89. arXiv : nlin/0204062 . doi :10.1007/978-0-387-21789-5_2. ISBN 978-1-4684-9566-9. S2CID 15024306.
^ Gershenson, Carlos (2004). «Введение в случайные булевы сети». В Bedau, M., P. Husbands, T. Hutton, S. Kumar и H. Suzuki (ред.) Workshop and Tutorial Proceedings, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALife IX). С. 2004 : 160–173. arXiv : nlin.AO/0408006 . Bibcode :2004nlin......8006G.
^ Wuensche, Andrew (2011). Исследование дискретной динамики: [руководство DDLab: инструменты для исследования клеточных автоматов, случайных булевых и многозначных сетей [sic] и не только]. Фром, Англия: Luniver Press. стр. 16. ISBN 9781905986316. Архивировано из оригинала 4 февраля 2023 . Получено 12 января 2016 .
^ Грейл, Флориан (2012). «Булевы сети как модельная структура». Frontiers in Plant Science . 3 : 178. doi : 10.3389 /fpls.2012.00178 . PMC 3419389. PMID 22912642.
^ Bastolla, U.; Parisi, G. (май 1998). "Модульная структура сетей Кауфмана". Physica D: Nonlinear Phenomena . 115 (3–4): 219–233. arXiv : cond-mat/9708214 . Bibcode : 1998PhyD..115..219B. doi : 10.1016/S0167-2789(97)00242-X. S2CID 1585753.
^ Бильке, Свен; Сьюннессон, Фредрик (декабрь 2001 г.). "Устойчивость модели Кауфмана". Physical Review E. 65 ( 1): 016129. arXiv : cond-mat/0107035 . Bibcode : 2001PhRvE..65a6129B. doi : 10.1103/PhysRevE.65.016129. PMID 11800758. S2CID 2470586.
^ Socolar, J.; Kauffman, S. (февраль 2003 г.). "Масштабирование в упорядоченных и критических случайных булевых сетях". Physical Review Letters . 90 (6): 068702. arXiv : cond-mat/0212306 . Bibcode : 2003PhRvL..90f8702S. doi : 10.1103/PhysRevLett.90.068702. PMID 12633339. S2CID 14392074.
^ Самуэльссон, Бьёрн; Тройн, Карл (март 2003 г.). «Суперполиномиальный рост числа аттракторов в сетях Кауфмана». Physical Review Letters . 90 (9): 098701. Bibcode : 2003PhRvL..90i8701S. doi : 10.1103/PhysRevLett.90.098701. PMID 12689263.
^ Михальев, Тамара; Дроссель, Барбара (октябрь 2006 г.). «Масштабирование в общем классе критических случайных булевых сетей». Physical Review E. 74 ( 4): 046101. arXiv : cond-mat/0606612 . Bibcode : 2006PhRvE..74d6101M. doi : 10.1103/PhysRevE.74.046101. PMID 17155127. S2CID 17739744.
^ Кауфман, С.А. (1969). «Метаболическая стабильность и эпигенез в случайно сконструированных генетических сетях». Журнал теоретической биологии . 22 (3): 437–467. Bibcode : 1969JThBi..22..437K. doi : 10.1016/0022-5193(69)90015-0. PMID 5803332.
^ Derrida, B; Pomeau, Y (1986-01-15). "Случайные сети автоматов: простое отожженное приближение". Europhysics Letters (EPL) . 1 (2): 45–49. Bibcode : 1986EL......1...45D. doi : 10.1209/0295-5075/1/2/001. S2CID 160018158. Архивировано из оригинала 2020-05-17 . Получено 2016-01-12 .
^ Solé, Ricard V.; Luque, Bartolo (1995-01-02). «Фазовые переходы и антихаос в обобщенных сетях Кауфмана». Physics Letters A. 196 ( 5–6): 331–334. Bibcode :1995PhLA..196..331S. doi :10.1016/0375-9601(94)00876-Q.
^ Luque, Bartolo; Solé, Ricard V. (1997-01-01). «Фазовые переходы в случайных сетях: простое аналитическое определение критических точек». Physical Review E. 55 ( 1): 257–260. Bibcode : 1997PhRvE..55..257L. doi : 10.1103/PhysRevE.55.257.
^ Фокс, Джеффри Дж.; Хилл, Колин К. (2001-12-01). «От топологии к динамике в биохимических сетях». Хаос: междисциплинарный журнал нелинейной науки . 11 (4): 809–815. Bibcode :2001Chaos..11..809F. doi : 10.1063/1.1414882 . ISSN 1054-1500. PMID 12779520.
^ Aldana, Maximino; Cluzel, Philippe (2003-07-22). "Естественный класс надежных сетей". Труды Национальной академии наук . 100 (15): 8710–8714. Bibcode : 2003PNAS..100.8710A. doi : 10.1073 /pnas.1536783100 . ISSN 0027-8424. PMC 166377. PMID 12853565.
^ Померанс, Эндрю; Отт, Эдвард; Гирван, Мишель ; Лосерт, Вольфганг (2009-05-19). «Влияние топологии сети на устойчивость дискретных моделей состояний генетического контроля». Труды Национальной академии наук . 106 (20): 8209–8214. arXiv : 0901.4362 . Bibcode : 2009PNAS..106.8209P. doi : 10.1073/pnas.0900142106 . ISSN 0027-8424. PMC 2688895. PMID 19416903 .
^ Aldana, Maximino (октябрь 2003 г.). «Булевская динамика сетей с топологией без масштаба». Physica D: Nonlinear Phenomena . 185 (1): 45–66. arXiv : cond-mat/0209571 . Bibcode : 2003PhyD..185...45A. doi : 10.1016/s0167-2789(03)00174-x.
^ Дроссель, Барбара; Грейл, Флориан (4 августа 2009 г.). «Критические булевы сети с безмасштабным распределением входящих степеней». Physical Review E. 80 ( 2): 026102. arXiv : 0901.0387 . Bibcode : 2009PhRvE..80b6102D. doi : 10.1103/PhysRevE.80.026102. PMID 19792195. S2CID 2487442.
^ Харви, Имман; Боссомайер, Терри (1997). «Время вышло из строя: аттракторы в асинхронных случайных булевых сетях». В Husbands, Фил; Харви, Имман (ред.). Труды Четвертой Европейской конференции по искусственной жизни (ECAL97). MIT Press. стр. 67–75. ISBN 9780262581578. Архивировано из оригинала 2023-02-04 . Получено 2020-09-16 .
^ Гершенсон, Карлос (2002). «Классификация случайных булевых сетей». В Standish, Russell K; Bedau, Mark A (ред.). Труды Восьмой международной конференции по искусственной жизни. Искусственная жизнь. Том 8. Кембридж, Массачусетс, США. стр. 1–8. arXiv : cs/0208001 . Bibcode :2002cs........8001G. ISBN 9780262692816. Архивировано из оригинала 4 февраля 2023 . Получено 12 января 2016 .{{cite book}}: CS1 maint: location missing publisher (link)
^ Гершенсон, Карлос; Брокарт, Ян; Аэртс, Дидерик (14 сентября 2003 г.). «Контекстные случайные булевы сети». Достижения в области искусственной жизни [ 7-я Европейская конференция, ECAL 2003 г. ]. Конспект лекций по информатике. Том 2801. Дортмунд, Германия. С. 615–624. arXiv : nlin/0303021 . doi :10.1007/978-3-540-39432-7_66. ISBN 978-3-540-39432-7. S2CID 4309400.{{cite book}}: CS1 maint: location missing publisher (link)
^ Имани, М.; Брага-Нето, УМ (01.01.2017). «Адаптивный фильтр максимального правдоподобия для частично наблюдаемых булевых динамических систем». Труды IEEE по обработке сигналов . 65 (2): 359–371. arXiv : 1702.07269 . Bibcode : 2017ITSP...65..359I. doi : 10.1109/TSP.2016.2614798. ISSN 1053-587X. S2CID 178376.
^ Имани, М.; Брага-Нето, УМ (2015). «Оптимальная оценка состояния для булевых динамических систем с использованием булева сглаживателя Калмана». Глобальная конференция IEEE по обработке сигналов и информации (GlobalSIP) 2015 г. стр. 972–976. doi :10.1109/GlobalSIP.2015.7418342. ISBN 978-1-4799-7591-4. S2CID 8672734.
^ Имани, М.; Брага-Нето, UM (2016). Американская конференция по контролю (ACC) 2016 г. С. 227–232. doi :10.1109/ACC.2016.7524920. ISBN 978-1-4673-8682-1. S2CID 7210088.
^ Имани, М.; Брага-Нето, У. (2016-12-01). "Итерация значений на основе точек для частично наблюдаемых булевых динамических систем с конечным пространством наблюдения". 55-я конференция IEEE по принятию решений и управлению (CDC) 2016 г. стр. 4208–4213. doi :10.1109/CDC.2016.7798908. ISBN 978-1-5090-1837-6. S2CID 11341805.
^ Чжан, Руи; Кавальканте, Хьюго LD de S.; Гао, Чжэн; Готье, Дэниел Дж.; Соколар, Джошуа ES; Адамс, Мэтью М.; Латроп, Дэниел П. (2009). "Булев хаос". Physical Review E. 80 ( 4): 045202. arXiv : 0906.4124 . Bibcode : 2009PhRvE..80d5202Z. doi : 10.1103/PhysRevE.80.045202. ISSN 1539-3755. PMID 19905381. S2CID 43022955.
^ Кавальканте, Хьюго LD de S.; Готье, Даниэль Дж.; Соколар, Джошуа ES; Чжан, Руи (2010). «О происхождении хаоса в автономных булевых сетях». Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences . 368 (1911): 495–513. arXiv : 0909.2269 . Bibcode : 2010RSPTA.368..495C. doi : 10.1098/rsta.2009.0235. ISSN 1364-503X. PMID 20008414. S2CID 426841.
^ Хаджирамезанали, Э. и Имани, М. и Брага-Нето, У. и Цянь, Х. и Догерти, Э.. Масштабируемая оптимальная байесовская классификация траекторий отдельных клеток в условиях неопределенности регуляторной модели. ACMBCB'18. https://dl.acm.org/citation.cfm?id=3233689 Архивировано 22.03.2021 на Wayback Machine

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

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

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