Finding the fixed points of a Boolean network from a positive feedback vertex set
Autor: | Luis Cabrera-Crot, Lilian Salinas, Julio Aracena |
---|---|
Rok vydání: | 2020 |
Předmět: |
Statistics and Probability
Vertex (graph theory) FOS: Computer and information sciences Discrete Mathematics (cs.DM) Computer science Gene regulatory network 0102 computer and information sciences Fixed point 01 natural sciences Biochemistry Feedback 03 medical and health sciences FOS: Mathematics Mathematics - Combinatorics Gene Regulatory Networks Molecular Biology 030304 developmental biology Positive feedback Discrete mathematics 0303 health sciences computer.file_format Graph Computer Science Applications Vertex (geometry) Computational Mathematics Boolean network Computational Theory and Mathematics 010201 computation theory & mathematics Feedback vertex set Executable Combinatorics (math.CO) computer Algorithms Computer Science - Discrete Mathematics |
Zdroj: | Bioinformatics (Oxford, England). 37(8) |
ISSN: | 1367-4811 |
Popis: | Motivation In the modeling of biological systems by Boolean networks, a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the regulatory graph like those proposed by Akutsu et al. and Zhang et al., which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation and inhibition) between its components. Results In this article, we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set P of its regulatory graph and which works, by applying a sequential update schedule, in time O(2|P|·n2+k), where n is the number of components and the regulatory functions of the network can be evaluated in time O(nk), k≥0. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point. Availability and implementation An executable file of FixedPoint algorithm made in Java and some examples of input files are available at: www.inf.udec.cl/˜lilian/FPCollector/. Supplementary information Supplementary material is available at Bioinformatics online. |
Databáze: | OpenAIRE |
Externí odkaz: |