Loïc Paulevé

Maximilien Gadouleau, Loïc Paulevé, Sara Riva

Boolean networks are extensively applied as models of complex dynamical systems, aiming at capturing essential features related to causality and synchronicity of the state changes of components along time. Dynamics of Boolean networks result from the application of their Boolean map according to a so-called update mode, specifying the possible transitions between network configurations. In this paper, we explore update modes that possess a memory on past configurations, and provide a generic framework to define them. We show that recently introduced modes such as the most permissive and interval modes can be naturally expressed in this framework, and we propose novel update modes, the history-based, trapping, and subcube-based modes. Building on the unified definitions, we provide a comprehensive comparison of memory-based update modes, resulting in their hierarchy by simulation and weak simulation. Finally, we highlight consequences of introducing memory on the notions of trajectory and attractors.

Kyungduk Moon, Kangbok Lee, Loïc Paulevé

Boolean networks are dynamical models of disease development in which the activation levels of genes are represented by binary variables. Given a Boolean network, controls represent mutations or medical treatments that fix the activation levels of selected genes so that all states in every attractor (i.e., long-term recurrent states) satisfy a desired phenotype. Our goal is to enumerate all minimal controls, identifying critical gene subsets in disease development and therapy. This problem has an inherent bilevel integer programming structure and is computationally challenging. We propose an infeasibility-based Benders decomposition, a logic-based Benders framework for bilevel integer programs with multiple subproblems. In our application, each subproblem finds a forbidden attractor of a given length and yields a problem-specific feasibility cut. We also propose an auxiliary IP called subspace separation that finds a Boolean subspace that includes multiple forbidden attractors and thereby strengthens the cut. Numerical experiments show that the resulting algorithms are much more scalable than state-of-the-art methods and that subspace separation substantially improves performance.