International Workshop on Boolean Networks (IWBN 2020) January 07‑10, 2020 07‑10 de enero 2020 Universidad de Concepción |
Universidad de Concepción Depto. de Ing. Inf. y Cs. de la Computación Depto. de Ingeniería Matemática Contact information: Contacto: iwbn2020 at udec.cl |
Boolean networks are a particular type of finite dynamic system that has been widely used in modeling complex systems such as: social networks, communication networks and, especially, biological systems such as gene regulation networks and neural networks. Las redes Booleanas son un tipo particular de sistema dinámicos finito que ha sido ampliamente usado en el modelamiento de sistemas complejos como: redes sociales, redes de comunicación y especialmente sistemas biológicos como redes de regulación génica y redes neuronales. This workshop aims at the scientific exchange on problems of Boolean networks and related combinatorial objects, from the point of view of discrete mathematics and computer science. Este workshop apunta al intercambio científico sobre problemas de las redes booleanas y objetos combinatorios relacionados, desde el punto de vista de la matemática discreta y ciencias de la computación. Participation in the workshop is free of charge but requires prior registration to the email: iwbn2020 at udec.cl. La participación en el workshop no tiene costo, pero requiere de una inscripción previa al correo: iwbn2020 at udec.cl.
Plenary Speakers Charlas Plenarias
Many structural and algorithmic results in graph theory concern special classes of graphs (e.g. bipartite, chordal, cographs, etc.). In this talk, we shall investigate how we could define different classes of Boolean networks and review some old and some recent results about their dynamics. We could define Boolean network classes e.g. recursively, or based on their interaction graph, or based on their local functions. “Automata Networks: 40 years of problems and applications” [+]
I will present a kind of survey on different problems related to automata networks that I have developed and shared with several colleagues in the last 40 years. Some of them are now closed, other semi‑closed and several ones remain open. “An introduction to algebraic biology: theory and applications” [+] Since Boolean functions can be expressed as polynomials, computational algebraic tools can be useful in the analysis of Boolean networks. I will use two examples from biology: analyzing a model of the tryptophanase (tna) operon in E. coli, and reverse engineering a mammalian signaling network, to illustrate how computational algebra arises. Relevant tools will include Gröbner bases, primary decomposition of ideals, and Alexander duality. Even better: biological applications like these have inspired completely new areas of classical mathematics. I will give a few examples of these, from the theory of pseudomonomial ideals, to a signed version of Stanley-Reisner theory. I will assume no prior knowledge of algebra in this talk. “Boolean networks and their dynamics” [+]
While Boolean networks have found a wide range of applications in the life sciences and elsewhere, their utility as models of dynamic processes has been limited by a relative lack of mathematical tools for their analysis, in comparison to continuous models. The size and complexity of published models is growing to the point where simulation and sampling methods for the determination of model dynamics are increasingly unsatisfactory. Also, much remains to be learned about the structural characteristics of Boolean network models in different application domains. Since the class of Boolean networks on n nodes is equivalent to the class of all set functions on binary strings of length n, such characteristics are needed in order to identify suitable structural restrictions on models that are sufficiently broad to cover applications, but sufficiently narrow to allow in depth mathematical analysis. This talk will outline approaches to a mathematical research program that can help address these issues and provide a foundation for the study of Boolean networks and their dynamics. “Algorithms for analyzing and controlling Boolean networks as biological networks” [+]
Boolean networks (BNs) can be considered as gene regulatory networks, where 1 (resp. 0) means that the gene is active (resp. inactive). Each singleton attractor (fixed point) corresponds to a cell type. We developed several rigorous exponential time algorithms that find singleton attractors for AND/OR BNs and nested canalyzing BNs. Furthermore, we developed integer linear programming (ILP)‑based methods for controlling BNs and singleton attractors. Invited Speakers Oradores Invitados
“ Complexity of limit cycle problems in conjunctive networks with different schedules” [+]
In this presentation, we will talk about conjunctive Boolean networks, namely, Boolean networks with conjunctive local functions. More precisely, we will show the complexity of the problem of determining if a conjunctive Boolean network has a limit cycle of a given length with different block sequential update schedules. We will first show this problem assuming a parallel (i.e. synchronous) update schedule. “Inverse problems on the block‑sequential operator in Boolean networks” [+] Motivated by the problem of the possible dynamics of a Boolean network with different update schedules, we study the block‑sequential operator that associates each Boolean network with block‑sequential schedule an equivalent Boolean network with a parallel scheme. In this presentation we focus on solving some inverse problems of this operator. In particular, on the complexity of finding the pre‑images of a given Boolean network. “A hard problem in a Boolean asynchronous freezing cellular automata” [+] In this talk we will study a particularly complex boolean asynchronous freezing cellular automaton (BAFCA). A cellular automaton is called freezing if cells in state 1 remain always in that state. A cellular automaton is asynchronous if at each time‑step only one cell is updated following a fixed permutation, called updating scheme. Given configuration, we say that a cell in state 0 is unstable if there exists an updating scheme that changes the state of the cell. In this context, we define the problem AsyncUnstability, which consists in deciding if a cell is unstable or not. In general, AsyncUnstability is NP. In this talk, we show that there exists an BAFCA with only 2 states and von Neumann neighborhood where AsyncUnstability is NP‑complete. In other words, under the assumption that P ≠ NP, there is no polynomial‑time algorithm capable to decide if a cell is unstable for this rule. “Combinatorics and dynamical classification of an Ising cellular automaton: the Q2R model” [+]
(joint work with Sergio Rica and Felipe Urbina) “The impact of topology in the prediction of freezing automata networks” [+]
An Automata Network is a map F : Qn → Qn where Q is a finite alphabet. It can be viewed as a graph with n vertices, called interaction graph, where each vertex has a state in Q. The state of each vertex v evolves following a synchronous update rule fv, which only depends on the neighbors in the interaction graph. An automata network is called freezing if a partial order can be defined on Q, in such a way that the state of a vertex is only allowed to evolve to a bigger state according to this order. “Multivariate information in random Boolean networks” [+] We numerically apply the framework of O‑information, as recently developed by Rosas et al, to study the dynamics that govern Random Boolean Networks (RBNs). O‑information is a multivariate extension of mutual information, and is therefore expected to illuminate the high‑order interdependencies that underlie distributed information processing. The results recover the familiar picture of order, chaos and complex behaviours of RBNs, which O‑information reveals, respectively, as redundancy‑dominated, synergistical and as a balance thereof. This suggests a novel way to study the dynamics between and within the different phases, as well as its relation with topology, restrictions on local functions or other variants. “Structure‑to‑Function theory for Boolean networks” [+] A central goal in research on Boolean Networks is to relate properties of their constituents (graphs, functions, and update mechanism) to properties of their phase spaces. In the first part of the presentation I will give examples of such results for threshold Boolean Networks. In the second and main part of the talk I will present a new Lipschitz continuity result showing the close relationship between phase spaces of asynchronous Boolean networks (ABNs) under toric equivalence of update sequences. I will close by remarking on how the diversity of dynamics for permutation ABNs is closely governed by the cycle structure of the underlying graph. “Composing behaviours in the semiring of dynamical systems” [+] By considering the operations of product and sum (co‑product) in the category of finite dynamical systems, we obtain a semiring structure, which allows us to analyse the composition of dynamics from an algebraic point of view. This semiring R appears to have a relatively complex structure, including multiple distinct decompositions into irreducible elements. We investigate the algorithmic solvability of equations in the associated semiring of polynomials R[X], which ranges from undecidable to tractable, as well as the related question of (in)decomposability of finite dynamical systems. “Synchronizing Boolean networks asynchronously” [+] The asynchronous automaton associated with a Boolean network f : {0,1}n → {0,1}n is the finite deterministic automaton with set of states {0,1}n, alphabet {1,…, n}, and where the action of letter i on a state x consists in either switching the i‑th component if fi (x) ≠ xi or doing nothing otherwise. This action is extended to words in the natural way. We then say that the Boolean network is synchronizing if there is a word w whose action is constant, that is, for some state x, the result of action of w on any state is x. In this talk, we present some works in progress concerning synchronizing Boolean networks. Our main result is that a Boolean network is synchronizing if its signed interaction graph is strong, has no positive cycle, and maximum in‑degree two (and the result is false if one the three hypotheses is dropped). “On the use of computational intelligence for threshold Boolean network inference with applications” [+]
In this talk we will present several applications of computational intelligence (genetic algorithms, differential evolution, swarm intelligence, neural networks, etc.) to the problem of inferring threshold Boolean networks that contain a desired Boolean trajectory or specific attractors. Applications to several biological models will be analyzed. “Enumerating the fixed points of a Boolean network from a positive feedback vertex set” [+]
Abstract Lilian Salinas Otros Participantes Other Participants
Program ProgramaSatellite School on Boolean Networks Escuela Satélite en Redes BooleanasThis school will be held on January 6 and 7, it is aimed at graduate and advanced undergraduate students as well as researchers looking for a quick introduction to the main theoretical results about Boolean networks. Esta escuela se desarrollará los días 6 y 7 de enero de 2020, está dirigida a estudiantes de pre y postgrado e investigadores que desean una rápida introducción a los principales resultados teóricos en redes Booleanas. The aim of this school is to introduce the Boolean network and the state of the art of the subject, so that undergraduate and graduate students can participate in the workshop that will take place between January 7 and 10. El objetivo de la escuela es presentar las redes Booleanas y el estado del arte en el tema, de modo que los estudiantes puedan participar en el Workshop que tomará lugar inmediatamente después.
The number of participants is limited, so those interested should apply before There are a limited number of accommodation and food scholarships for students outside of Concepción. For those who require it, they must include the request in their motivation email. Hay un número limitado de becas de alojamiento y alimentación para estudiantes fuera de Concepción. Para quienes lo requieran deben incluir la solicitud en su correo de motivación. Tutorials Tutoriales
Introducción a las redes Booleanas: motivación y conceptos básicos. Influence of the interaction graph on the dynamics of Boolean networks. Fixed points and feedback cycles in Boolean networks. Dinámica de redes Booleanas con diferentes esquemas de actualización. Programa ProgramLas clases se realizarán en la Sala IS 3-1 de la Facultad de Ingeniería, Universidad de Concepción. Classes are held in classroom IS 3-1 of the Faculty of Engineering, Universidad de Concepción.
Facultad de Ciencias Físicas y Matemáticas Universidad de Concepción, Auditorio Alamiro Robledo.
Pictures Fotos
|