Red booleana

Una red booleana consiste en un conjunto discreto de variables booleanas, cada una de las cuales tiene asignada una función booleana (posiblemente diferente para cada variable) que toma entradas de un subconjunto de esas variables y una salida que determina el estado de la variable a la que está asignada. Este conjunto de funciones determina en efecto una topología (conectividad) en el conjunto de variables, que luego se convierten en nodos de una red . Por lo general, la dinámica del sistema se toma como una serie temporal discreta donde el estado de toda la red en el momento t +1 se determina evaluando la función de cada variable en el estado de la red en el momento t . Esto puede hacerse de forma sincrónica o asincrónica. ^[1]

Las redes booleanas se han utilizado en biología para modelar redes reguladoras. Aunque las redes booleanas son una simplificación burda de la realidad genética, donde los genes no son simples interruptores binarios, hay varios casos en los que transmiten correctamente el patrón correcto de genes expresados y suprimidos. ^[2]^[3] El modelo aparentemente matemático fácil (sincrónico) recién se entendió por completo a mediados de la década de 2000. ^[4]

Modelo clásico

Una red booleana es un tipo particular de sistema dinámico secuencial , donde el tiempo y los estados son discretos, es decir, tanto el conjunto de variables como el conjunto de estados en la serie de tiempo tienen cada uno una biyección sobre una serie de enteros.

Una red booleana aleatoria (RBN) es una que se selecciona aleatoriamente del conjunto de todas las redes booleanas posibles de un tamaño particular, N. Luego, se puede estudiar estadísticamente cómo las propiedades esperadas de dichas redes dependen de varias propiedades estadísticas del conjunto de todas las redes posibles. Por ejemplo, se puede estudiar cómo cambia el comportamiento de la RBN a medida que cambia la conectividad promedio.

Las primeras redes booleanas fueron propuestas por Stuart A. Kauffman en 1969, como modelos aleatorios de redes reguladoras genéticas ^[5] pero su comprensión matemática recién comenzó en la década de 2000. ^[6]^[7]

Atractores

Como una red booleana tiene solo 2 ^N estados posibles, una trayectoria alcanzará tarde o temprano un estado visitado previamente y, por lo tanto, como la dinámica es determinista, la trayectoria caerá en un estado estable o ciclo llamado atractor (aunque en el campo más amplio de los sistemas dinámicos, un ciclo solo es un atractor si las perturbaciones que lo originan conducen de regreso a él). Si el atractor tiene un solo estado, se denomina atractor puntual y si el atractor consta de más de un estado, se denomina atractor cíclico . El conjunto de estados que conducen a un atractor se denomina cuenca del atractor. Los estados que ocurren solo al comienzo de las trayectorias (ninguna trayectoria conduce a ellos) se denominan estados del jardín del Edén ^[8] y la dinámica de la red fluye desde estos estados hacia los atractores. El tiempo que lleva alcanzar un atractor se denomina tiempo transitorio ^[4] .

Con el aumento de la potencia informática y la creciente comprensión de un modelo aparentemente simple, distintos autores dieron distintas estimaciones del número medio y la longitud de los atractores; a continuación se presenta un breve resumen de las publicaciones clave. ^[9]

Estabilidad

En la teoría de sistemas dinámicos, la estructura y longitud de los atractores de una red corresponde a la fase dinámica de la red. La estabilidad de las redes booleanas depende de las conexiones de sus nodos . Una red booleana puede exhibir un comportamiento estable, crítico o caótico . Este fenómeno está regido por un valor crítico del número promedio de conexiones de nodos ( ), y puede caracterizarse por la distancia de Hamming como medida de distancia. En el régimen inestable, la distancia entre dos estados inicialmente cercanos en promedio crece exponencialmente en el tiempo, mientras que en el régimen estable disminuye exponencialmente. En esto, con "estados inicialmente cercanos" se quiere decir que la distancia de Hamming es pequeña en comparación con el número de nodos ( ) en la red. $K_{c}$ $N$

Para el modelo NK ^[15] la red es estable si , crítica si , e inestable si . $K<K_{c}$ $K=K_{c}$ $K>K_{c}$

El estado de un nodo dado se actualiza de acuerdo con su tabla de verdad , cuyas salidas se completan aleatoriamente. denota la probabilidad de asignar una salida desactivada a una serie dada de señales de entrada. $n_{i}$ $p_{i}$

Si para cada nodo, la transición entre el rango estable y caótico depende de . Según Bernard Derrida e Yves Pomeau ^[16] , el valor crítico del número promedio de conexiones es . $p_{i}=p=const.$ $p$ $K_{c}=1/[2p(1-p)]$

Si no es constante y no hay correlación entre los grados de entrada y los grados de salida, las condiciones de estabilidad están determinadas por ^[17]^[18]^[19] La red es estable si , crítica si , e inestable si . $K$ $\langle K^{in}\rangle$ $\langle K^{in}\rangle <K_{c}$ $\langle K^{in}\rangle =K_{c}$ $\langle K^{in}\rangle >K_{c}$

Las condiciones de estabilidad son las mismas en el caso de redes con topología libre de escala donde la distribución de grados de entrada y salida es una distribución de ley de potencia: , y , ya que cada enlace de salida de un nodo es un enlace de entrada a otro. ^[20] $P(K)\propto K^{-\gamma }$ $\langle K^{in}\rangle =\langle K^{out}\rangle$

La sensibilidad muestra la probabilidad de que la salida de la función booleana de un nodo dado cambie si cambia su entrada. Para redes booleanas aleatorias, . En el caso general, la estabilidad de la red está gobernada por el valor propio más grande de la matriz , donde , y es la matriz de adyacencia de la red. ^[21] La red es estable si , crítica si , inestable si . $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$

Variaciones del modelo

Otras topologías

Un tema es estudiar diferentes topologías de gráficos subyacentes .

El caso homogéneo se refiere simplemente a una cuadrícula que es simplemente la reducción del famoso modelo de Ising .
Se pueden elegir topologías sin escala para redes booleanas. ^[22] Se puede distinguir el caso en el que solo la distribución de grado de entrada se distribuye según la ley de potencia, ^[23] o solo la distribución de grado de salida o ambas.

Otros esquemas de actualización

Las redes booleanas clásicas (a veces llamadas CRBN , es decir, Classic Random Boolean Network) se actualizan de forma sincrónica. Motivadas por el hecho de que los genes no suelen cambiar su estado simultáneamente, ^[24] se han introducido diferentes alternativas. Una clasificación común ^[25] es la siguiente:

Las redes booleanas asincrónicas deterministas actualizadas ( DRBN ) no se actualizan de forma sincrónica, pero aún existe una solución determinista. Un nodo i se actualizará cuando t ≡ Q _i ( mod P _i ), donde t es el paso de tiempo. ^[26]
El caso más general es la actualización estocástica completa ( GARBN , redes booleanas aleatorias asíncronas generales). Aquí, se seleccionan uno (o más) nodos en cada paso computacional para actualizarlos.
El modelo de señal del Sistema Dinámico Booleano Parcialmente Observado (POBDS) ^[27]^[28]^[29]^[30] se diferencia de todos los modelos de red booleana deterministas y estocásticos anteriores al eliminar el supuesto de observabilidad directa del vector de estado booleano y permitir la incertidumbre en el proceso de observación, abordando el escenario encontrado en la práctica.
Las redes booleanas autónomas ( ABN ) se actualizan en tiempo continuo ( t es un número real, no un entero), lo que genera condiciones de carrera y un comportamiento dinámico complejo como el caos determinista. ^[31]^[32]

Aplicación de redes booleanas

Clasificación

La clasificación bayesiana óptima escalable ^[33] desarrolló una clasificación óptima de trayectorias que tiene en cuenta la incertidumbre potencial del modelo y también propuso una clasificación de trayectoria basada en partículas que es altamente escalable para redes grandes con una complejidad mucho menor que la solución óptima.

Véase también

Modelo NK

Referencias

^ Naldi, A.; Monteiro, PT; Mussel, C.; Kestler, HA; Thieffry, D.; Xenarios, I.; Saez-Rodriguez, J.; Helikar, T.; Chaouiya, C. (25 de enero de 2015). "Desarrollo cooperativo de estándares y herramientas de modelado lógico con CoLoMoTo". Bioinformática . 31 (7): 1154–1159. doi : 10.1093/bioinformatics/btv013 . PMID 25619997.
^ Albert, Réka; Othmer, Hans G (julio de 2003). "La topología de las interacciones reguladoras predice el patrón de expresión de los genes de polaridad de segmentos en Drosophila melanogaster". Journal of Theoretical Biology . 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 de abril de 2004). "Impresión del gen L3MBTL humano, un miembro de la familia polycomb ubicado en una región del cromosoma 20 eliminada en neoplasias mieloides humanas". Actas de la Academia Nacional de Ciencias . 101 (19): 7341–7346. Bibcode :2004PNAS..101.7341L. doi : 10.1073/pnas.0308195101 . PMC 409920 . PMID 15123827.
^ ab Drossel, Barbara (diciembre de 2009). "Redes booleanas aleatorias". En Schuster, Heinz Georg (ed.). Capítulo 3. Redes booleanas aleatorias . Reseñas de dinámica no lineal y complejidad. Wiley. págs. 69-110. arXiv : 0706.3351 . doi :10.1002/9783527626359.ch3. ISBN . 9783527626359.S2CID119300231 .
^ ab Kauffman, Stuart (11 de octubre de 1969). "Homeostasis y diferenciación en redes de control genético aleatorio". 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). "Dinámica booleana con acoplamientos aleatorios". Perspectivas y problemas en la ciencia no lineal: un volumen de celebración en honor a Lawrence Sirovich . págs. 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). "Introducción a las redes booleanas aleatorias". En Bedau, M., P. Husbands, T. Hutton, S. Kumar y H. Suzuki (Eds.) Actas del taller y tutorial, Novena conferencia internacional sobre la simulación y síntesis de sistemas vivos (ALife IX). Pp . 2004 : 160–173. arXiv : nlin.AO/0408006 . Código Bibliográfico :2004nlin......8006G.
^ Wuensche, Andrew (2011). Explorando dinámica discreta: [el manual de DDLab: herramientas para investigar autómatas celulares, redes aleatorias booleanas y multivalor y más allá]. Frome, Inglaterra: Luniver Press. p. 16. ISBN 9781905986316Archivado desde el original el 4 de febrero de 2023 . Consultado el 12 de enero de 2016 .
^ Greil, Florian (2012). "Redes booleanas como marco de modelado". Frontiers in Plant Science . 3 : 178. doi : 10.3389/fpls.2012.00178 . PMC 3419389 . PMID 22912642.
^ Bastolla, U.; Parisi, G. (mayo de 1998). "La estructura modular de las redes de Kauffman". Physica D: Nonlinear Phenomena . 115 (3–4): 219–233. arXiv : cond-mat/9708214 . Código Bibliográfico :1998PhyD..115..219B. doi :10.1016/S0167-2789(97)00242-X. S2CID 1585753.
^ Bilke, Sven; Sjunnesson, Fredrik (diciembre de 2001). "Estabilidad del modelo de Kauffman". Physical Review E . 65 (1): 016129. arXiv : cond-mat/0107035 . Código Bibliográfico :2001PhRvE..65a6129B. doi :10.1103/PhysRevE.65.016129. PMID 11800758. S2CID 2470586.
^ Socolar, J.; Kauffman, S. (febrero de 2003). "Escalamiento en redes booleanas aleatorias críticas y ordenadas". Physical Review Letters . 90 (6): 068702. arXiv : cond-mat/0212306 . Bibcode :2003PhRvL..90f8702S. doi :10.1103/PhysRevLett.90.068702. PMID 12633339. S2CID 14392074.
^ Samuelsson, Björn; Troein, Carl (marzo de 2003). "Crecimiento superpolinomial en el número de atractores en redes de Kauffman". Physical Review Letters . 90 (9): 098701. Bibcode :2003PhRvL..90i8701S. doi :10.1103/PhysRevLett.90.098701. PMID 12689263.
^ Mihaljev, Tamara; Drossel, Barbara (octubre de 2006). "Escalamiento en una clase general de redes booleanas aleatorias críticas". Physical Review E . 74 (4): 046101. arXiv : cond-mat/0606612 . Bibcode :2006PhRvE..74d6101M. doi :10.1103/PhysRevE.74.046101. PMID 17155127. S2CID 17739744.
^ Kauffman, SA (1969). "Estabilidad metabólica y epigénesis en redes genéticas construidas aleatoriamente". Journal of Theoretical Biology . 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). "Redes aleatorias de autómatas: una aproximación recocida simple". Europhysics Letters (EPL) . 1 (2): 45–49. Código Bibliográfico :1986EL......1...45D. doi :10.1209/0295-5075/1/2/001. S2CID 160018158. Archivado desde el original el 2020-05-17 . Consultado el 2016-01-12 .
^ Solé, Ricard V.; Luque, Bartolo (2 de enero de 1995). "Transiciones de fase y anticaos en redes generalizadas de Kauffman". 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). "Transiciones de fase en redes aleatorias: determinación analítica simple de puntos críticos". Physical Review E . 55 (1): 257–260. Bibcode :1997PhRvE..55..257L. doi :10.1103/PhysRevE.55.257.
^ Fox, Jeffrey J.; Hill, Colin C. (1 de diciembre de 2001). "De la topología a la dinámica en redes bioquímicas". Chaos: An Interdisciplinary Journal of Nonlinear Science . 11 (4): 809–815. Bibcode :2001Chaos..11..809F. doi : 10.1063/1.1414882 . ISSN 1054-1500. PMID 12779520.
^ Aldana, Maximino; Cluzel, Philippe (22 de julio de 2003). "Una clase natural de redes robustas". Actas de la Academia Nacional de Ciencias . 100 (15): 8710–8714. Bibcode :2003PNAS..100.8710A. doi : 10.1073/pnas.1536783100 . ISSN 0027-8424. PMC 166377 . PMID 12853565.
^ Pomerance, Andrew; Ott, Edward; Girvan, Michelle ; Losert, Wolfgang (19 de mayo de 2009). "El efecto de la topología de red en la estabilidad de los modelos de estado discreto de control genético". Actas de la Academia Nacional de Ciencias . 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 (octubre de 2003). "Dinámica booleana de redes con topología libre de escala". Physica D: Nonlinear Phenomena . 185 (1): 45–66. arXiv : cond-mat/0209571 . Bibcode :2003PhyD..185...45A. doi :10.1016/s0167-2789(03)00174-x.
^ Drossel, Barbara; Greil, Florian (4 de agosto de 2009). "Redes booleanas críticas con distribución de grado de entrada libre de escala". Physical Review E . 80 (2): 026102. arXiv : 0901.0387 . Bibcode :2009PhRvE..80b6102D. doi :10.1103/PhysRevE.80.026102. PMID 19792195. S2CID 2487442.
^ Harvey, Imman; Bossomaier, Terry (1997). "Tiempo fuera de articulación: Atractores en redes booleanas aleatorias asincrónicas". En Husbands, Phil; Harvey, Imman (eds.). Actas de la Cuarta Conferencia Europea sobre Vida Artificial (ECAL97). MIT Press. págs. 67–75. ISBN 9780262581578Archivado desde el original el 4 de febrero de 2023. Consultado el 16 de septiembre de 2020 .
^ Gershenson, Carlos (2002). "Clasificación de redes booleanas aleatorias". En Standish, Russell K; Bedau, Mark A (eds.). Actas de la Octava Conferencia Internacional sobre Vida Artificial. Vida artificial. Vol. 8. Cambridge, Massachusetts, EE. UU., págs. 1–8. arXiv : cs/0208001 . Código Bibliográfico :2002cs........8001G. ISBN. 9780262692816Archivado desde el original el 4 de febrero de 2023 . Consultado el 12 de enero de 2016 .{{cite book}}: CS1 maint: location missing publisher (link)
^ Gershenson, Carlos; Broekaert, Jan; Aerts, Diederik (14 de septiembre de 2003). "Redes booleanas aleatorias contextuales". Avances en vida artificial [ 7.ª Conferencia Europea, ECAL 2003 ]. Apuntes de clase en informática. Vol. 2801. Dortmund, Alemania. págs. 615–624. arXiv : nlin/0303021 . doi :10.1007/978-3-540-39432-7_66. ISBN . 978-3-540-39432-7.S2CID4309400 .{{cite book}}: CS1 maint: location missing publisher (link)
^ Imani, M.; Braga-Neto, UM (1 de enero de 2017). "Filtro adaptativo de máxima verosimilitud para sistemas dinámicos booleanos parcialmente observados". IEEE Transactions on Signal Processing . 65 (2): 359–371. arXiv : 1702.07269 . Bibcode :2017ITSP...65..359I. doi :10.1109/TSP.2016.2614798. ISSN 1053-587X. S2CID 178376.
^ Imani, M.; Braga-Neto, UM (2015). "Estimación de estado óptimo para sistemas dinámicos booleanos utilizando un suavizador de Kalman booleano". Conferencia global IEEE de 2015 sobre procesamiento de señales e información (GlobalSIP) . pp. 972–976. doi :10.1109/GlobalSIP.2015.7418342. ISBN . 978-1-4799-7591-4.S2CID8672734 .
^ Imani, M.; Braga-Neto, UM (2016). Conferencia Americana de Control de 2016 (ACC) . págs. 227–232. doi :10.1109/ACC.2016.7524920. ISBN . 978-1-4673-8682-1. Número de identificación del sujeto 7210088.
^ Imani, M.; Braga-Neto, U. (1 de diciembre de 2016). "Iteración de valores basados en puntos para sistemas dinámicos booleanos parcialmente observados con espacio de observación finito". 2016 IEEE 55th Conference on Decision and Control (CDC) . págs. 4208–4213. doi :10.1109/CDC.2016.7798908. ISBN 978-1-5090-1837-6. Número de identificación del sujeto 11341805.
^ Zhang, Rui; Cavalcante, Hugo LD de S.; Gao, Zheng; Gauthier, Daniel J.; Socolar, Josué ES; Adams, Mateo M.; Lathrop, Daniel P. (2009). "Caos booleano". Revisión física E. 80 (4): 045202. arXiv : 0906.4124 . Código Bib : 2009PhRvE..80d5202Z. doi : 10.1103/PhysRevE.80.045202. ISSN 1539-3755. PMID 19905381. S2CID 43022955.
^ Cavalcante, Hugo LD de S.; Gauthier, Daniel J.; Socolar, Josué ES; Zhang, Rui (2010). "Sobre el origen del caos en las redes booleanas autónomas". Transacciones filosóficas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería . 368 (1911): 495–513. arXiv : 0909.2269 . Código Bib : 2010RSPTA.368..495C. doi :10.1098/rsta.2009.0235. ISSN 1364-503X. PMID 20008414. S2CID 426841.
^ Hajiramezanali, E. & Imani, M. & Braga-Neto, U. & Qian, X. & Dougherty, E.. Clasificación bayesiana óptima escalable de trayectorias de células individuales bajo incertidumbre del modelo regulatorio. ACMBCB'18. https://dl.acm.org/citation.cfm?id=3233689 Archivado el 22 de marzo de 2021 en Wayback Machine.

Dubrova, E., Teslenko, M., Martinelli, A., (2005). *Kauffman Networks: Analysis and Applications, en "Actas de la Conferencia Internacional sobre Diseño Asistido por Computadora", páginas 479-484.

Enlaces externos

Análisis de modelos algebraicos dinámicos (ADAM) v1.1
bioasp/bonesis: Síntesis de las redes booleanas más permisivas a partir de la arquitectura de red y las propiedades dinámicas
CoLoMoTo (Consorcio de modelos y herramientas lógicos)
Laboratorio DDL
Simulador de redes booleanas NetBuilder
Simulador de red booleana de código abierto
Red Kauffman de JavaScript
Redes Booleanas Probabilísticas (PBN)
Laboratorio RBNL
Una herramienta basada en SAT para calcular atractores en redes booleanas