Magíster en Ciencias, Mención Computación / Ingeniero Civil Matemático / Una red Booleana es un modelo de redes en el cual, cada nodo o elemento de la red tiene asociado una función Booleana que determina el estado del nodo respectivo, y de esta forma la evolución de la red en el tiempo. Los puntos fijos de una red Booleana, esto es, estados particulares de la red que permanecen constantes en el tiempo, han ganado importancia, por ejemplo, en el contexto de redes de regulación génica, donde los puntos fijos tienen un correlato biológico. Para cada red finita y estado inicial posible, dentro de una cantidad finita de actualizaciones de la red, los estados de la red alcanzarán un punto fijo o un ciclo límite, la cual es una secuencia de estados de la red que se repiten a lo largo del tiempo. Puntos fijos y ciclos límites son denominados atractores de la red.
En este trabajo nos concentramos en estudiar ciertos aspectos de los atractores de redes Booleanas, incluyendo aspectos computacionales, caracterizaciones, entre otros, utilizando la noción de "filtro'' de una red. Un filtro es un procedimiento consistente en aplicar de forma iterativa transformaciones a una red, cada una de las cuales simula con dinámica paralela cierto modo de actualización, produciendo una nueva red cuyas propiedades y dinámica pueden ser relacionadas con la red inicial. Se ha mostrado que estos filtros pueden ser muy útiles, dado que filtros asociados a actualizaciones secuenciales pueden entregar información eficientemente sobre los puntos fijos de una red (Goles y Salinas 2010).
Nuestro análisis se restringe a redes Booleanas disyuntivas, lo cual permite concentrarse solo en la topología de la red. Nos concentramos además en esquemas de actualización bloque-secuencial, los cuales son una generalización de los esquemas paralelo y secuencial. Los principales resultados de este trabajo establecen cotas polinomiales para la complejidad de tiempo de un filtro, así como condiciones sobre la red y esquema de entrada que aseguran ciertas propiedades en la red de salida, incluyendo la remoción de ciclos límites. Los resultados obtenidos hacen uso de teoría de matrices positivas, y fueron formulados con la ayuda de simulaciones computacionales ejecutadas con una aplicación desarrollada para este fin.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/131562 |
| Date | January 2014 |
| Creators | Plana Perillán, Francisco Antonio |
| Contributors | Pérez Rojas, Jorge, Goles Chacc, Eric, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ciencias de la Computación, Departamento de Ingeniería Matemática, Barceló Baeza, Pablo, Rapaport Zimermann, Iván, Ruz Heredia, Gonzalo |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds