A discrete perspective towards the construction of sparse probabilistic Boolean networks

Abstract

<p>The construction problem of sparse probabilistic Boolean networks (PBNs) has important applications in areas such as gene regulatory network inference and financial risk modeling. Many of the existing methods for solving this problem do not output sparse decompositions or are associated with high time complexity. We propose a new Entry-Removal-Type (ERT) algorithm called the Greedy Entry Removal algorithm (GER) for solving the construction problem. The key idea behind GER is to maximize the reduction in the number of positive entries in the residue matrix at each iteration, resulting in fewer iterations needed for the residue matrix to become the zero matrix and allowing GER to output sparse decompositions. We establish new upper bounds for two existing ERT algorithms and GER, providing theoretical guarantees for their performance. In numerical experiments based on both synthetic and real-world data, GER outperforms state-of-the-art sparse PBN construction algorithms by producing the sparsest decompositions for most of the tested transition probability matrices. Additionally, we are the first to study the lower bound problem related to sparse PBN construction and derive a series of theoretical results, which can inform future algorithm design and set realistic expectations for the sparsity achievable in practical scenarios.</p>