red booleana

Una red booleana consta de 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 de hecho 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 de tiempo 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 se puede hacer 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 cruda simplificación 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) no se entendió completamente hasta mediados de la década de 2000. ^[4]

modelo clasico

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 temporal tienen cada uno una biyección en una serie entera.

Una red booleana aleatoria (RBN) es aquella que se selecciona aleatoriamente del conjunto de todas las redes booleanas posibles de un tamaño particular , N. Entonces se puede estudiar estadísticamente cómo las propiedades esperadas de tales redes dependen de diversas 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 no comenzó hasta la década de 2000. ^[6]^[7]

Atractores

Dado que una red booleana tiene sólo 2 ^N estados posibles, una trayectoria tarde o temprano alcanzará un estado previamente visitado y, por lo tanto, dado que la dinámica es determinista, la trayectoria caerá en un estado estacionario o ciclo llamado atractor (aunque en el sentido más amplio). campo de los sistemas dinámicos un ciclo es un atractor sólo si las perturbaciones de él conducen de regreso a él). Si el atractor tiene un solo estado se llama atractor puntual , y si el atractor consta de más de un estado se llama atractor cíclico . El conjunto de estados que conducen a un atractor se llama cuenca del atractor. Los estados que ocurren sólo 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 tarda en llegar a un atractor se llama tiempo transitorio . ^[4]

Con una potencia informática cada vez mayor y una comprensión cada vez mayor del modelo aparentemente simple, diferentes autores dieron diferentes estimaciones para el número medio y la longitud de los atractores; aquí 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 se rige 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 con 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 determinado se actualiza según su tabla de verdad , cuyas salidas se completan aleatoriamente. denota la probabilidad de asignar una salida desactivada a una serie determinada 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 medio 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 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 sin escala donde la distribución de grados de entrada y salida es una distribución de ley de potencia: y , dado que cada enlace de salida desde 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 determinado cambie si cambia su entrada. Para redes booleanas aleatorias, . En el caso general, la estabilidad de la red se rige 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 simplemente se refiere a una grilla que no es más que la reducción al famoso modelo de Ising .
Se pueden elegir topologías sin escala para redes booleanas. ^[22] Se puede distinguir el caso en el que solo se distribuye la distribución dentro del grado en la ley de potencias, ^[23] o solo la distribución fuera del grado, o ambas.

Otros esquemas de actualización

Las redes booleanas clásicas (a veces denominadas CRBN , es decir, redes booleanas aleatorias clásicas) se actualizan sincrónicamente. Motivados 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 actualizadas asincrónicas deterministas ( DRBN ) no se actualizan sincrónicamente, 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 asincrónicas generales). Aquí, se seleccionan uno (o más) nodos en cada paso computacional para actualizar.
El modelo de señal del Sistema Dinámico Booleano Parcialmente Observado (POBDS) ^[27]^[28]^[29]^[30] difiere de todos los modelos de red booleanos deterministas y estocásticos anteriores al eliminar el supuesto de observabilidad directa del vector de estado booleano y permitir 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 número entero), lo que conduce a condiciones de carrera y 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 posible incertidumbre 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.

Ver también

modelo NK

Referencias

^ Naldi, A.; Monteiro, PT; Mejillón, C.; Kestler, HA; Ladrón, D.; Xenarios, I.; Sáez-Rodríguez, 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/bioinformática/btv013 . PMID 25619997.
^ Alberto, 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 del segmento en Drosophila melanogaster". Revista de Biología Teórica . 223 (1): 1–18. arXiv : q-bio/0311019 . Código Bib : 2003JThBi.223....1A. CiteSeerX 10.1.1.13.3370 . doi :10.1016/S0022-5193(03)00035-3. PMC 6388622 . PMID 12782112.
^ Li, J.; Banco, 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 malignas humanas". Procedimientos de la Academia Nacional de Ciencias . 101 (19): 7341–7346. Código bibliográfico : 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. S2CID 119300231.
^ ab Kauffman, Stuart (11 de octubre de 1969). "Homeostasis y diferenciación en redes de control genético aleatorio". Naturaleza . 224 (5215): 177–178. Código Bib :1969Natur.224..177K. doi :10.1038/224177a0. PMID 5343519. S2CID 4179318.
^ Aldana, Máximo; Calderero, Susan ; Kadanoff, Leo P. (2003). "Dinámica booleana con acoplamientos aleatorios". Perspectivas y problemas de 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.) Taller y actas tutoriales, Novena Conferencia Internacional sobre Simulación y Síntesis de Sistemas Vivos (ALife IX). págs . 2004 : 160-173. arXiv : nlin.AO/0408006 . Código Bib : 2004nlin......8006G.
^ Wuensche, Andrés (2011). Explorando la dinámica discreta: [el manual de DDLab: herramientas para investigar autómatas celulares, redes booleanas aleatorias y multivalor [sic] y más. Frome, Inglaterra: Luniver Press. pag. 16.ISBN 9781905986316. Archivado 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". Fronteras en la ciencia vegetal . 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 Kauffman". Physica D: Fenómenos no lineales . 115 (3–4): 219–233. arXiv : cond-mat/9708214 . Código Bib : 1998PhyD..115..219B. doi :10.1016/S0167-2789(97)00242-X. S2CID 1585753.
^ Bilke, Sven; Sjunnesson, Fredrik (diciembre de 2001). "Estabilidad del modelo Kauffman". Revisión física 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). "Escalado en redes booleanas aleatorias ordenadas y críticas". Cartas de revisión física . 90 (6): 068702. arXiv : cond-mat/0212306 . Código bibliográfico : 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 Kauffman". Cartas de revisión física . 90 (9): 098701. Código bibliográfico : 2003PhRvL..90i8701S. doi : 10.1103/PhysRevLett.90.098701. PMID 12689263.
^ Mihaljev, Tamara; Drossel, Barbara (octubre de 2006). "Escalado en una clase general de redes booleanas aleatorias críticas". Revisión física E. 74 (4): 046101. arXiv : cond-mat/0606612 . Código bibliográfico : 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 al azar". Revista de Biología Teórica . 22 (3): 437–467. Código Bib : 1969JThBi..22..437K. doi :10.1016/0022-5193(69)90015-0. PMID 5803332.
^ Derrida, B; Pomeau, Y (15 de enero de 1986). "Redes aleatorias de autómatas: una aproximación recocida simple". Cartas de Eurofísica (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 17 de mayo de 2020 . Consultado el 12 de enero de 2016 .
^ Solé, Ricard V.; Luque, Bartolo (2 de enero de 1995). "Transiciones de fase y anticaos en redes Kauffman generalizadas". Letras de Física A. 196 (5–6): 331–334. Código bibliográfico : 1995PhLA..196..331S. doi :10.1016/0375-9601(94)00876-Q.
^ Luque, Bartolo; Solé, Ricard V. (1 de enero de 1997). "Transiciones de fase en redes aleatorias: determinación analítica simple de puntos críticos". Revisión física E. 55 (1): 257–260. Código Bib : 1997PhRvE..55..257L. doi :10.1103/PhysRevE.55.257.
^ Zorro, Jeffrey J.; Colina, Colin C. (1 de diciembre de 2001). "De la topología a la dinámica en redes bioquímicas". Caos: una revista interdisciplinaria de ciencia no lineal . 11 (4): 809–815. Código Bib :2001Caos..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". Procedimientos de la Academia Nacional de Ciencias . 100 (15): 8710–8714. Código Bib : 2003PNAS..100.8710A. doi : 10.1073/pnas.1536783100 . ISSN 0027-8424. PMC 166377 . PMID 12853565.
^ Pomerancia, Andrew; Ott, Eduardo; Girvan, Michelle ; Losert, Wolfgang (19 de mayo de 2009). "El efecto de la topología de red sobre la estabilidad de modelos de control genético de estado discreto". Procedimientos de la Academia Nacional de Ciencias . 106 (20): 8209–8214. arXiv : 0901.4362 . Código Bib : 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: Fenómenos no lineales . 185 (1): 45–66. arXiv : cond-mat/0209571 . Código bibliográfico : 2003PhyD..185...45A. doi :10.1016/s0167-2789(03)00174-x.
^ Drossel, Bárbara; Greil, Florian (4 de agosto de 2009). "Redes booleanas críticas con distribución en grados sin escala". Revisión física E. 80 (2): 026102. arXiv : 0901.0387 . Código bibliográfico : 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 Maridos, Phil; Harvey, Imman (eds.). Actas de la Cuarta Conferencia Europea sobre Vida Artificial (ECAL97). Prensa del MIT. págs. 67–75. ISBN 9780262581578. Archivado 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, Estados Unidos. págs. 1–8. arXiv : cs/0208001 . Código Bib : 2002cs.......8001G. ISBN 9780262692816. Archivado 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, enero; Aerts, Diederik (14 de septiembre de 2003). "Redes booleanas aleatorias contextuales". Avances en vida artificial [ 7ª Conferencia Europea, ECAL 2003 ]. Apuntes de conferencias sobre 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. S2CID 4309400.{{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". Transacciones IEEE sobre procesamiento de señales . 65 (2): 359–371. arXiv : 1702.07269 . Código Bib : 2017ITSP...65..359I. doi :10.1109/TSP.2016.2614798. ISSN 1053-587X. S2CID 178376.
^ Imani, M.; Braga-Neto, UM (2015). "Estimación del estado óptimo para sistemas dinámicos booleanos utilizando un suavizador booleano de Kalman". Conferencia global IEEE 2015 sobre procesamiento de señales e información (GlobalSIP) . págs. 972–976. doi :10.1109/GlobalSIP.2015.7418342. ISBN 978-1-4799-7591-4. S2CID 8672734.
^ Imani, M.; Braga-Neto, UM (2016). Conferencia Americana de Control (ACC) 2016 . págs. 227-232. doi :10.1109/ACC.2016.7524920. ISBN 978-1-4673-8682-1. S2CID 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 55ª Conferencia del IEEE sobre Decisión y Control (CDC) . págs. 4208–4213. doi :10.1109/CDC.2016.7798908. ISBN 978-1-5090-1837-6. S2CID 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 unicelulares bajo la 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: Análisis y aplicaciones, 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)
DDLab
Simulador de redes booleanas NetBuilder
Simulador de red booleana de código abierto
Red Kauffman de JavaScript
Redes booleanas probabilísticas (PBN)
RBNLab
Una herramienta basada en SAT para calcular atractores en redes booleanas