Limit cycles and update digraphs in Boolean networks

Boolean networks have been used as models of gene regulation and other biological networks, as well as for other kinds of distributed dynamical systems. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Salinas (2008) 22] and Aracena et al. (2009) 1], equivalence classes of deterministic update schedules according to the labeled digraph associated to a Boolean network (update digraph) were defined and it was proved that two schedules in the same class yield the same dynamical behavior. In this paper, we study the relations between the update digraphs and the preservation of limit cycles of Boolean networks iterated under non-equivalent update schedules. We show that the related problems lie in the class of NP-hard problems and we prove that the information provided by the update digraphs is not sufficient to determine whether two Boolean networks share limit cycles or not. Besides, we exhibit a polynomial algorithm that works as a necessary condition for two Boolean networks to share limit cycles. Finally, we construct some update schedule classes whose elements share a given limit cycle under certain conditions on the frozen nodes of it.