Scalable Shapley Value Estimators for Node Importance in Boolean Models of Gene Regulatory Networks

This thesis addresses the problem of assessing node importance in biological networks, with a particular focus on Boolean networks as a modeling framework for gene regulatory systems. Biological processes are inherently complex and are often governed by interactions among multiple components. Understanding which components play a critical role in determining system behavior is essential for applications such as disease analysis and drug discovery. In this context, identifying important nodes in biological networks has become a central task in computational biology. A wide range of methods has been proposed to evaluate node importance, including topology-based measures, robustness analysis, influence maximization techniques, and sensitivity analysis. While these approaches provide valuable insights, they often rely on structural properties or generic metrics that may not fully capture the dynamic and context-dependent nature of biological systems. In particular, many existing methods produce a single generic ranking of nodes, which limits their ability to explain how specific components influence particular phenotypes or outputs. To address these limitations, this thesis introduces a framework based on the Shapley value, a concept from cooperative game theory that quantifies the contribution of individual players within a system. Building on this idea, the thesis proposes a formulation of Shapley value tailored to Boolean networks. This formulation aligns naturally with biological perturbation experiments, such as gene knock-out and knock-in studies, and provides a quantitative measure of node importance with a clear biological interpretation. A major challenge in applying the Shapley value is its computational complexity, as exact computation requires repeatedly evaluating all possible environmental conditions for all internal nodes of the network. To overcome this limitation, the thesis introduces a propagation-based method that computes Shapley values without exhaustive simulation. The method leverages the logical structure of Boolean networks to propagate contributions through the network, providing exact results for acyclic networks and accurate approximations for cyclic ones. This approach significantly reduces computational complexity, making the analysis more scalable while preserving interpretability. The effectiveness of the proposed method is evaluated through a series of experiments and comparative analyses. The results show that the method provides more informative and target-specific insights compared to traditional approaches, which often provide a single generic ranking. In addition, the propagation-based approach offers substantial computational advantages over standard \textit{in silico} perturbation methods, enabling efficient analysis of larger networks. Finally, the practical applicability of the framework is demonstrated through a case study on a biological network related to macrophage polarization. The study illustrates how the proposed method can be used to identify key regulatory nodes associated with specific phenotypes, highlighting its potential for supporting drug target identification and guiding experimental research. In conclusion, this thesis presents a novel and scalable approach for assessing node importance in Boolean networks, combining theoretical rigor with practical applicability. By integrating concepts from game theory and network dynamics, the proposed framework provides a powerful tool for analyzing complex biological systems and contributes to advancing computational methods in systems biology and drug discovery.