Julio Aracena, Luis Cabrera-Crot, Lilian Salinas:
Finding the fixed points of a Boolean network from a positive feedback vertex set
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 interaction graph like those proposed by Akutsu et al. which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation, inhibition) between its components. In this paper 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 interaction graph and which works, by applying a sequential update schedule, in time O(2^|P| n^2), where n is the number of components. The theoretical foundation of this algorithm is due to a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point. An executable file of FixedPoint algorithm made in Java and some examples of input files are available at: www.inf.udec.cl/~lilian/FPCollector
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Luis CABRERA-CROT, Lilian SALINAS: Finding the fixed points of a Boolean network from a positive feedback vertex set. Bioinformatics, vol. 37, 8, pp. 1148-1155, (2021).