LAUSR

We derive a new graph-theoretic sufficient condition for observability of a Boolean control network (BCN). We describe two algorithms that are based on this condition. The first selects a set of nodes so that observing this set makes the BCN observable. The second algorithm builds an observer for the observable BCN. Both algorithms are sub-optimal, as they are based on a sufficient but not necessary condition for observability. Yet their time-complexity is linear in the length of the description of the BCN, rendering them feasible for large-scale BCNs. We discuss how these results can be used to provide a sub-optimal yet polynomial-complexity algorithm for the minimal observability problem in BCNs. Some of the theoretical results are demonstrated using BCN models of mammalian cell cycle control, and T-cell receptor kinetics.