Influence maximization in Boolean networks

The optimization problem aiming at the identification of minimal sets of nodes able to drive the dynamics of Boolean networks toward desired long-term behaviors is central for some applications, as for example the detection of key therapeutic targets to control pathways in models of biological signaling and regulatory networks. Unfortunately, the complexity of the optimization problem is exponential, making it exactly solvable on very small systems only. Some scalable approaches exist, but they rely on linear approximations; other approaches estimate nonlinear effects, but they are generally not scalable. In this talk, I will introduce an alternative method inspired by those used in the solution of the well-studied problem of influence maximization for spreading processes in social networks. The computational time of the proposed method scales cubically with the network size. This is achieved thanks to some strong approximations, as for example neglecting dynamical correlations among Boolean variables. However, the method has the desirable feature of fully accounting for the nonlinear nature of Boolean dynamics. I will validate the method on small gene regulatory networks whose dynamical landscapes are known by means of brute-force analysis. I will then systematically apply it to a large collection of gene regulatory networks revealing that for about 65% of the analyzed networks, the minimal driver sets contain less than 20% of their nodes.