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.

En esta tesis hemos estudiado dos problemas: el primero consiste en encontrar condiciones mínimas para obtener una cierta clase de recubrimientos del plano discreto mediante cuadrados y el segundo corresponde al estudio de redes Booleanas. El problema de recubrimiento por cuadrados nace como una variante del problema de embaldosado. El problema de embaldosado consiste en cubrir el plano discreto, o una parte de éste, sin dejar hoyos y sin superponer baldosas con un número finito de formas distintas. El caso estudiado consiste en cubrir completamente el plano discreto usando sólo cuadrados que pueden superponerse, pero no pueden compartir bordes ni vértices (recubrimiento fuerte). Además, se estudia el caso donde se permite dejar zonas de tamaño acotado sin cubrir y donde todos los cuadrados en el recubrimiento deben estar conectados (recubrimiento débil). Hemos probado que, en el caso donde todos los cuadrados tienen el mismo tamaño e intersectan el mismo número de cuadrados, los recubrimientos fuertes y débiles presentan cotas inferiores para el tamaño y número de cuadrados que los intersectan. Además, para un tamaño de cuadrado dado, mostramos una cota superior de orden lineal para el número de cuadrados que lo intersectan en un recubrimiento sea fuerte o débil, El segundo problema trata de redes Booleanas, las que fueron introducidas por S. Kauffman (1969) con el objeto de modelar las redes de regulación génica. El primer aspecto estudiado son las redes Booleanas cuyo grafo asociado es por capas. Probamos que el comportamiento límite de este tipo de redes queda completamente determinado por el estado inicial de los nodos en la primera capa, y que los atractores de estas redes son de largo potencia de dos. Más aún, en el caso que todas las bucles sean monótonas crecientes todos los atractores son puntos fijos. El segundo aspecto estudiado es la robustez de la dinámica y del comportamiento límite de una red Booleana frente a distintos esquemas de actualización (paralelo, secuencial por bloques o secuencial). Cada esquema de actualización permite definir un grafo con signo, los resultados obtenidos prueban que si dos esquemas de actualización generan el mismo grafo con signo, estas redes tienen exactamente el mismo comportamiento dinámico. Por otro lado, dado que los puntos fijos son invariantes frente a los distintos esquemas de actualización, nos concentramos en estudiar cómo pequeños cambios en el esquema de actualización producen diferencias en el conjunto de ciclos dinámicos asociados a una red Booleana. Uno de los principales resultados es el que muestra que, dado un esquema de actualización es posible encontrar otro con el cual no comparte ciclos dinámicos. Por último, presentamos un algoritmo que opera como un filtro de ciclos dinámicos para redes Booleanas donde todos los circuitos son positivos. Dada una red Booleana, que tiene sólo circuitos positivos, este filtro permite encontrar en tiempo polinomial una nueva red Booleana que tiene exactamente los mismos puntos fijos, pero no tiene ningún ciclo dinámico. Este algoritmo permite, además, encontrar un punto fijo de la red Booleana en tiempo polinomial.

Em sistemas biológicos, o estudo da estabilidade das redes de regulação gênica é visto como uma contribuição importante que a Matemática pode proporcionar a pesquisas sobre câncer e outras doenças genéticas. Neste trabalho, utilizamos o conceito de ``canalização\'\' como sinônimo de estabilidade em uma rede biológica. Como as características de uma rede de regulação canalizada ainda são superficialmente compreendidas, estudamos esse conceito sob o ponto de vista computacional: propomos um modelo matemático simplificado para descrever o fenômeno e realizamos algumas análises sobre o mesmo. Mais especificamente, a estabilidade da maior bacia de atração das redes Booleanas - um clássico paradigma para a modelagem de redes de regulação - é analisada. Os resultados indicam que a estabilidade da maior bacia de atração está relacionada com dados biológicos sobre o crescimento de colônias de leveduras e que considerações sobre a interação entre as funções Booleanas e a topologia da rede devem ser realizadas conjuntamente na análise de redes estáveis. / In biological systems, the study of gene regulatory networks stability is seen as an important contribution that Mathematics can make to cancer research and that of other genetic diseases. In this work, we consider the concept of ``canalization\'\' as a consequence of stability in gene regulatory networks. The characteristics of canalized regulatory networks are superficially understood. Hence, we study the canalization concept under a computational framework: a simplified model is proposed to describe the phenomenon using Boolean Networks - a classical paradigm to modeling regulatory networks. Specifically, the stability of the largest basin of attraction in gene regulatory networks is analyzed. Our results indicate that the stability of the largest basin of attraction is related to biological data on growth of yeast colonies, and that thoughts about the interaction between Boolean functions and network topologies must be given in the analysis of stable networks.

Em sistemas biológicos, o estudo da estabilidade das redes de regulação gênica é visto como uma contribuição importante que a Matemática pode proporcionar a pesquisas sobre câncer e outras doenças genéticas. Neste trabalho, utilizamos o conceito de ``canalização\'\' como sinônimo de estabilidade em uma rede biológica. Como as características de uma rede de regulação canalizada ainda são superficialmente compreendidas, estudamos esse conceito sob o ponto de vista computacional: propomos um modelo matemático simplificado para descrever o fenômeno e realizamos algumas análises sobre o mesmo. Mais especificamente, a estabilidade da maior bacia de atração das redes Booleanas - um clássico paradigma para a modelagem de redes de regulação - é analisada. Os resultados indicam que a estabilidade da maior bacia de atração está relacionada com dados biológicos sobre o crescimento de colônias de leveduras e que considerações sobre a interação entre as funções Booleanas e a topologia da rede devem ser realizadas conjuntamente na análise de redes estáveis. / In biological systems, the study of gene regulatory networks stability is seen as an important contribution that Mathematics can make to cancer research and that of other genetic diseases. In this work, we consider the concept of ``canalization\'\' as a consequence of stability in gene regulatory networks. The characteristics of canalized regulatory networks are superficially understood. Hence, we study the canalization concept under a computational framework: a simplified model is proposed to describe the phenomenon using Boolean Networks - a classical paradigm to modeling regulatory networks. Specifically, the stability of the largest basin of attraction in gene regulatory networks is analyzed. Our results indicate that the stability of the largest basin of attraction is related to biological data on growth of yeast colonies, and that thoughts about the interaction between Boolean functions and network topologies must be given in the analysis of stable networks.

Submitted by Marta Toyoda (1144061@mackenzie.br) on 2018-09-03T21:53:40Z No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2018-09-19T18:29:59Z (GMT) No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-09-19T18:29:59Z (GMT). No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the convergence to _xed points, a behavior found in the context of the density classi_cation problem, where the aim is the network's convergence to a fixed point of the prevailing node value in the initial global configuration of the network; in other words, a global decision is targeted, but according to a constrained, non-global action. In this work, we rely on evolutionary searches in order to _nd rules and network topologies with good performance in the task. All nodes' neighborhoods are assumed to be de_ned by non-regular and bidirectional links, and the Boolean function of the network initialized by the local majority rule. Firstly, is carried out a search in the space of network topologies, guided by the ω metric, related to the "small-worldness" of the networks, and then, in the space of Boolean functions, but constraining the network topologies to the best family identified in the previous experiment.. / Redes Booleanas são compostas por nós que representam variáveis binárias computadas em função dos valores representados por nós adjacentes. Esta computação local leva a comportamentos globais, como a convergência para um estado fixo da rede. Tal comportamento é utilizado na tarefa de classificação de densidade, onde procura-se a convergência dos valores de todos os nós para um ponto fixo que reflete o estado predominante presente na configuração inicial da rede, ou seja, um objetivo global restrito a ações de caráter local. Neste trabalho são efetuadas buscas evolutivas de modo a encontrar regras e topologias de redes Booleanas com boa performance na classificação de densidade. Consideram-se exclusivamente vizinhanças irregulares e bidirecionais para todos os nós, representando inicialmente a função Booleana da rede através da regra da maioria da vizinhança. Primeiramente, efetuam-se buscas evolutivas por topologias de redes guiadas pela métrica ω, esta referente à classificação de redes de mundo pequeno, e em seguida, efetuam-se buscas evolutivas no espaço de possíveis funções Booleanas utilizando as topologias de redes encontradas anteriormente.

Um problema importante na área de Biologia Sistêmica é o de inferência de redes de regulação gênica. Os avanços científicos e tecnológicos nos permitem analisar a expressão gênica de milhares de genes simultaneamente. Por \"expressão gênica\'\', estamos nos referindo ao nível de mRNA dentro de uma célula. Devido a esta grande quantidade de dados, métodos matemáticos, estatísticos e computacionais têm sido desenvolvidos com o objetivo de elucidar os mecanismos de regulação gênica presentes nos organismos vivos. Para isso, modelos matemáticos de redes de regulação gênica têm sido propostos, assim como algoritmos para inferir estas redes. Neste trabalho, focamos nestes dois aspectos: modelagem e inferência. Com relação à modelagem, estudamos modelos existentes para o ciclo celular da levedura (Saccharomyces cerevisiae). Após este estudo, propomos um modelo baseado em redes Booleanas probabilísticas sensíveis ao contexto, e em seguida, um aprimoramento deste modelo, utilizando cadeias de Markov não homogêneas. Mostramos os resultados, comparando os nossos modelos com os modelos estudados. Com relação à inferência, propomos um novo algoritmo utilizando o paradigma de crescimento de semente de genes. Neste contexto, uma semente é um pequeno subconjunto de genes de interesse. Nosso algoritmo é baseado em dois passos: passo de crescimento de semente e passo de amostragem. No primeiro passo, o algoritmo adiciona outros genes à esta semente, seguindo algum critério. No segundo, o algoritmo realiza uma amostragem de redes, definindo como saída um conjunto de redes potencialmente interessantes. Aplicamos o algoritmo em dados artificiais e dados biológicos de células HeLa, mostrando resultados satisfatórios. / A key problem in Systems Biology is the inference of gene regulatory networks. The scientific and technological advancement allow us to analyze the gene expression of thousands of genes, simultaneously. By \"gene expression\'\' we refer to the mRNA concentration level inside a cell. Due to this large amount of data, mathematical, statistical and computational methods have been developed in order to elucidate the gene regulatory mechanisms that take part of every living organism. To this end, mathematical models of gene regulatory networks have been proposed, along with algorithms to infer these networks. In this work, we focus in two aspects: modeling and inference. Regarding the modeling, we studied existing models for the yeast (Saccharomyces cerevisiae) cell cycle. After that, we proposed a model based on context sensitive probabilistic Boolean networks, and then, an improvement of this model, using nonhomogeneous Markov chain. We show the results, comparing our models against the studied models. Regarding the inference, we proposed a new algorithm using the seed growing paradigm. In this context, a seed is a small subset of genes. Our algorithm is based in two main steps: seed growing step and sampling step. In the first step, the algorithm adds genes into the seed, according to some criterion. In the second step, the algorithm performs a sampling process on the space of networks, defining as its output a set of potentially interesting networks. We applied the algorithm on artificial and biological HeLa cells data, showing satisfactory results.

Um problema importante na área de Biologia Sistêmica é o de inferência de redes de regulação gênica. Os avanços científicos e tecnológicos nos permitem analisar a expressão gênica de milhares de genes simultaneamente. Por \"expressão gênica\'\', estamos nos referindo ao nível de mRNA dentro de uma célula. Devido a esta grande quantidade de dados, métodos matemáticos, estatísticos e computacionais têm sido desenvolvidos com o objetivo de elucidar os mecanismos de regulação gênica presentes nos organismos vivos. Para isso, modelos matemáticos de redes de regulação gênica têm sido propostos, assim como algoritmos para inferir estas redes. Neste trabalho, focamos nestes dois aspectos: modelagem e inferência. Com relação à modelagem, estudamos modelos existentes para o ciclo celular da levedura (Saccharomyces cerevisiae). Após este estudo, propomos um modelo baseado em redes Booleanas probabilísticas sensíveis ao contexto, e em seguida, um aprimoramento deste modelo, utilizando cadeias de Markov não homogêneas. Mostramos os resultados, comparando os nossos modelos com os modelos estudados. Com relação à inferência, propomos um novo algoritmo utilizando o paradigma de crescimento de semente de genes. Neste contexto, uma semente é um pequeno subconjunto de genes de interesse. Nosso algoritmo é baseado em dois passos: passo de crescimento de semente e passo de amostragem. No primeiro passo, o algoritmo adiciona outros genes à esta semente, seguindo algum critério. No segundo, o algoritmo realiza uma amostragem de redes, definindo como saída um conjunto de redes potencialmente interessantes. Aplicamos o algoritmo em dados artificiais e dados biológicos de células HeLa, mostrando resultados satisfatórios. / A key problem in Systems Biology is the inference of gene regulatory networks. The scientific and technological advancement allow us to analyze the gene expression of thousands of genes, simultaneously. By \"gene expression\'\' we refer to the mRNA concentration level inside a cell. Due to this large amount of data, mathematical, statistical and computational methods have been developed in order to elucidate the gene regulatory mechanisms that take part of every living organism. To this end, mathematical models of gene regulatory networks have been proposed, along with algorithms to infer these networks. In this work, we focus in two aspects: modeling and inference. Regarding the modeling, we studied existing models for the yeast (Saccharomyces cerevisiae) cell cycle. After that, we proposed a model based on context sensitive probabilistic Boolean networks, and then, an improvement of this model, using nonhomogeneous Markov chain. We show the results, comparing our models against the studied models. Regarding the inference, we proposed a new algorithm using the seed growing paradigm. In this context, a seed is a small subset of genes. Our algorithm is based in two main steps: seed growing step and sampling step. In the first step, the algorithm adds genes into the seed, according to some criterion. In the second step, the algorithm performs a sampling process on the space of networks, defining as its output a set of potentially interesting networks. We applied the algorithm on artificial and biological HeLa cells data, showing satisfactory results.