Scalable Hypergraph Algorithms for Observability of Gene Regulation

A cornerstone of understanding complex systems is observability: the capacity of data to encode a system’s state. Hypergraphs are an effective way to represent higher-order data that captures group interactions within these systems. In this paper, we present hypergraph based algorithms that determine the observability properties of systems whose group interactions are governed by polynomial dynamics. Our proposed framework evaluates nonlinear observability criteria for polynomial dynamics using hypergraph walks, bypassing traditional matrix and tensor-based approaches. The improved efficiency of the proposed methods enables the analysis of hypergraph systems that are several orders of magnitude larger than previously possible. Finally, we use these methods to address the sensor and biomarker selection problem in a hypergraph model of the cell cycle, which contains hundreds of genes and thousands of group interactions.