Discrimination of singleton and periodic attractors in Boolean networks

Determining the minimum number of sensor nodes to observe the internal state of the whole system is important in analysis of complex networks. However, existing studies suggest that a large number of sensor nodes are needed to know the whole internal state. In this paper, we focus on identification of a small set of sensor nodes to discriminate statically and periodically steady states using the Boolean network model where steady states are often considered to correspond to cell types. In other words, we seek a minimum set of nodes to discriminate singleton and periodic attractors. We prove that one node is not necessarily enough but two nodes are always enough to discriminate two periodic attractors by using the Chinese remainder theorem. Based on this, we present an algorithm to determine the minimum number of nodes to discriminate all given attractors. We also present a much more efficient algorithm to discriminate singleton attractors. The results of computational experiments suggest that attractors in realistic Boolean networks can be discriminated by observing the states of only a small number of nodes.