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) sobre el conjunto de variables, que luego se convierten en nodos en 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 tiempo t +1 se determina evaluando la función de cada variable sobre el estado de la red en el tiempo t . Esto se puede hacerde 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 burda simplificación de la realidad genética donde los genes no son simples interruptores binarios, hay varios casos en los que capturan correctamente el patrón correcto de genes expresados y suprimidos. [2] [3] El modelo aparentemente matemático fácil (sincrónico) solo se entendió completamente a 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 de la serie temporal tienen una biyección en una serie entera.
Una red Boolean aleatorio (RBN) es uno que se selecciona al azar a partir del conjunto de todas las posibles redes de operadores booleanos de un tamaño particular, N . Entonces se puede estudiar estadísticamente cómo las propiedades esperadas de tales 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 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 solo comenzó en la década de 2000. [6] [7]
Atractores
Dado que una red booleana tiene solo 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 estable o ciclo llamado atractor (aunque en el más amplio campo de los sistemas dinámicos, un ciclo es sólo un atractor si las perturbaciones de él conducen 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 se tarda en llegar a un atractor se denomina tiempo transitorio . [4]
Con el aumento de la potencia informática y la 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í un breve resumen de las publicaciones clave. [9]
Autor | Año | Longitud media del atractor | Número medio de atractores | comentario |
---|---|---|---|---|
Kauffmann [5] | 1969 | |||
Bastolla / Parisi [10] | 1998 | más rápido que una ley de potencia, | más rápido que una ley de potencia, | primeras evidencias numéricas |
Bilke / Sjunnesson [11] | 2002 | lineal con el tamaño del sistema, | ||
Socolar / Kauffman [12] | 2003 | más rápido que lineal, con | ||
Samuelsson / Troein [13] | 2003 | crecimiento superpolinomial, | prueba matemática | |
Mihaljev / Drossel [14] | 2005 | más rápido que una ley de potencia, | más rápido que una ley de potencia, |
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 medio de conexiones de nodos (), y se puede caracterizar 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 cerrados" uno significa que la distancia de Hamming es pequeña en comparación con el número de nodos () en la red.
Para el modelo NK [15], la red es estable si, crítico si , e inestable si .
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.
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.
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ítico si , e inestable si .
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 , ya que cada enlace de salida de un nodo es un enlace de entrada a otro. [20]
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 se rige por el valor propio más grande de matriz , dónde , y es la matriz de adyacencia de la red. [21] La red es estable si, crítico si , inestable si .
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 cuadrícula que es simplemente 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 de grados en la ley de potencias, [23] o solo la distribución de grados de salida o ambos.
Otros esquemas de actualización
Las redes booleanas clásicas (a veces llamadas CRBN , es decir, red booleana aleatoria clásica) se actualizan sincrónicamente. Motivados por el hecho de que los genes no suelen cambiar su estado de forma simultánea, [24] se han introducido diferentes alternativas. Una clasificación común [25] es la siguiente:
- Las redes booleanas actualizadas asíncronas deterministas ( DRBN ) no se actualizan sincrónicamente, pero todavía 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í, uno (o más) nodos se seleccionan en cada paso de cálculo para actualizarse.
- El modelo de señal del sistema dinámico booleano parcialmente observado (POBDS) [27] [28] [29] [30] difiere de todos los modelos de redes booleanos 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 conduce a 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 teniendo 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.
Ver también
- Modelo NK
Referencias
- ^ Naldi, A .; Monteiro, PT; Mejillón, C .; Kestler, HA; Thieffry, 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 / 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 del segmento en Drosophila melanogaster" . Revista de Biología Teórica . 223 (1): 1–18. 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 eliminado en neoplasias mieloides humanas" . Actas 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 .
- ^ a b Drossel, Barbara (diciembre de 2009). "Redes booleanas aleatorias". En Schuster, Heinz Georg (ed.). Capítulo 3. Redes booleanas aleatorias . Revisiones de complejidad y dinámica no lineal. Wiley. págs. 69-110. arXiv : 0706.3351 . doi : 10.1002 / 9783527626359.ch3 . ISBN 9783527626359. S2CID 119300231 .
- ^ a b 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 Bibliográfico : 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 las ciencias no lineales . 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.) Talleres y tutoriales, Novena Conferencia Internacional sobre 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 la dinámica discreta: [el manual de DDLab: herramientas para investigar autómatas celulares, neworks aleatorios booleanos y multivalor [sic] y más allá] . Frome, Inglaterra: Luniver Press. pag. 16. ISBN 9781905986316. Consultado el 12 de enero de 2016 .
- ^ Greil, Florian (2012). "Redes booleanas como marco de modelado" . Fronteras en la ciencia de las plantas . 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 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 Kauffman". Revisión E física . 65 (1): 016129. arXiv : cond-mat / 0107035 . Código Bibliográfico : 2002PhRvE..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 Kauffman Networks". 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 E física . 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 aleatoriamente". Revista de Biología Teórica . 22 (3): 437–467. 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 Europhysics (EPL) . 1 (2): 45–49. Código Bibliográfico : 1986EL ...... 1 ... 45D . doi : 10.1209 / 0295-5075 / 1/2/001 .
- ^ Solé, Ricard V .; Luque, Bartolo (2 de enero de 1995). "Transiciones de fase y antichaos en redes Kauffman generalizadas". Physics Letters 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 E física . 55 (1): 257–260. Código Bibliográfico : 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". Caos: una revista interdisciplinaria de ciencia no lineal . 11 (4): 809–815. Código bibliográfico : 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. Código Bib : 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 la red sobre 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 . Código Bibliográfico : 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, Barbara; Greil, Florian (4 de agosto de 2009). "Redes booleanas críticas con distribución en grados sin escala". Revisión E física . 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). Maridos, Phil; Harvey, Imman (eds.). Time out of joint: Atractores en redes booleanas aleatorias asincrónicas . Actas de la Cuarta Conferencia Europea sobre Vida Artificial (ECAL97) . Prensa del MIT. págs. 67–75. ISBN 9780262581578.
- ^ Gershenson, Carlos (2002). Standish, Russell K; Bedau, Mark A (eds.). Clasificación de redes booleanas aleatorias . Actas de la Octava Conferencia Internacional sobre Vida Artificial . Vida artificial. 8 . Cambridge, Massachusetts, Estados Unidos. págs. 1–8. arXiv : cs / 0208001 . Código Bibliográfico : 2002cs ........ 8001G . ISBN 9780262692816. Consultado el 12 de enero de 2016 .
- ^ Gershenson, Carlos; Broekaert, Jan; Aerts, Diederik (14 de septiembre de 2003). Redes booleanas aleatorias contextuales [ 7ª Conferencia Europea, ECAL 2003 ]. Avances en la vida artificial . Apuntes de conferencias en informática. 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 .
- ^ 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 de estado óptimo para sistemas dinámicos booleanos utilizando un suavizador de Kalman booleano". 2015 IEEE Global Conference on Signal and Information Processing (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 de Control Estadounidense de 2016 (ACC) . 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 valor basada 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. S2CID 11341805 .
- ^ Zhang, Rui; Cavalcante, Hugo LD de S .; Gao, Zheng; Gauthier, Daniel J .; Socolar, Joshua ES; Adams, Matthew M .; Lathrop, Daniel P. (2009). "Caos booleano". Revisión E física . 80 (4). arXiv : 0906.4124 . doi : 10.1103 / PhysRevE.80.045202 . ISSN 1539-3755 .
- ^ Cavalcante, Hugo LD de S .; Gauthier, Daniel J .; Socolar, Joshua ES; Zhang, Rui (2010). "Sobre el origen del caos en las redes autónomas booleanas". Transacciones filosóficas de la Royal Society A: Ciencias matemáticas, físicas y de la ingeniería . 368 (1911): 495–513. arXiv : 0909.2269 . doi : 10.1098 / rsta.2009.0235 . ISSN 1364-503X .
- ^ 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
- 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 la mayoría de las redes booleanas permisivas a partir de la arquitectura de red y las propiedades dinámicas
- CoLoMoTo (Consorcio de modelos lógicos y herramientas)
- DDLab
- Simulador de redes booleanas de NetBuilder
- Simulador de red booleana de código abierto
- JavaScript Kauffman Network
- Redes booleanas probabilísticas (PBN)
- RBNLab
- Una herramienta basada en SAT para computar atractores en redes booleanas