logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-10212026-174620


Tipo di tesi
Tesi di dottorato di ricerca
Autore
PHAM, TRAN HUONG GIANG
URN
etd-10212026-174620
Titolo
Scalable Shapley Value Estimators for Node Importance in Boolean Models of Gene Regulatory Networks
Settore scientifico disciplinare
INF/01 - INFORMATICA
Corso di studi
INFORMATICA
Relatori
.
supervisore Prof. Milazzo, Paolo
co-supervisore Prof.ssa Da Pozzo, Eleonora
Parole chiave
  • Boolean Networks
  • Gene Regulatory Networks
  • Node importance
  • Shapley Value
Data inizio appello
25/10/2026
Consultabilità
Completa
Riassunto (Inglese)
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.
Riassunto (Italiano)
Questa tesi affronta il problema della valutazione dell'importanza dei nodi nelle reti biologiche, con particolare attenzione alle reti booleane come quadro di modellazione per i sistemi di regolazione genica. I processi biologici sono intrinsecamente complessi e sono spesso governati dalle interazioni tra più componenti. Comprendere quali componenti svolgano un ruolo critico nel determinare il comportamento del sistema è essenziale per applicazioni come l'analisi delle malattie e la scoperta di farmaci. In questo contesto, l'identificazione dei nodi importanti nelle reti biologiche è diventata un compito centrale della biologia computazionale.
Per valutare l'importanza dei nodi è stata proposta un'ampia gamma di metodi, tra cui misure basate sulla topologia, analisi della robustezza, tecniche di massimizzazione dell'influenza e analisi di sensibilità. Pur offrendo spunti preziosi, tali approcci si basano spesso su proprietà strutturali o metriche generiche che potrebbero non catturare pienamente la natura dinamica e dipendente dal contesto dei sistemi biologici. In particolare, molti dei metodi esistenti producono un'unica classifica generica dei nodi, il che ne limita la capacità di spiegare come specifiche componenti influenzino determinati fenotipi o output.
Per superare queste limitazioni, la tesi introduce un framework basato sul valore di Shapley, un concetto della teoria dei giochi cooperativi che quantifica il contributo dei singoli giocatori all'interno di un sistema. Partendo da questa idea, la tesi propone una formulazione del valore di Shapley adattata alle reti booleane. Tale formulazione si allinea naturalmente agli esperimenti di perturbazione biologica, come gli studi di knock-out e knock-in genico, e fornisce una misura quantitativa dell'importanza dei nodi con una chiara interpretazione biologica.
Una sfida importante nell'applicazione del valore di Shapley è la sua complessità computazionale, poiché il calcolo esatto richiede di valutare ripetutamente tutte le possibili condizioni ambientali per tutti i nodi interni della rete. Per superare questa limitazione, la tesi introduce un metodo basato sulla propagazione che calcola i valori di Shapley senza ricorrere a una simulazione esaustiva. Il metodo sfrutta la struttura logica delle reti booleane per propagare i contributi attraverso la rete, fornendo risultati esatti per le reti aciclici e approssimazioni accurate per quelle cicliche. Questo approccio riduce in modo significativo la complessità computazionale, rendendo l'analisi più scalabile e preservandone l'interpretabilità.
L'efficacia del metodo proposto è valutata attraverso una serie di esperimenti e analisi comparative. I risultati mostrano che il metodo fornisce indicazioni più informative e specifiche per il target rispetto agli approcci tradizionali, che spesso offrono un'unica classifica generica. Inoltre, l'approccio basato sulla propagazione offre vantaggi computazionali sostanziali rispetto ai metodi standard di perturbazione *in silico*, consentendo un'analisi efficiente di reti di dimensioni maggiori.
Infine, l'applicabilità pratica del framework è dimostrata attraverso un caso di studio su una rete biologica relativa alla polarizzazione dei macrofagi. Lo studio illustra come il metodo proposto possa essere utilizzato per identificare i nodi regolatori chiave associati a fenotipi specifici, evidenziandone il potenziale nel supportare l'identificazione di bersagli farmacologici e nell'orientare la ricerca sperimentale.
In conclusione, questa tesi presenta un approccio nuovo e scalabile per la valutazione dell'importanza dei nodi nelle reti booleane, che unisce rigore teorico e applicabilità pratica. Integrando concetti della teoria dei giochi e della dinamica delle reti, il framework proposto fornisce uno strumento potente per l'analisi dei sistemi biologici complessi e contribuisce al progresso dei metodi computazionali nella biologia dei sistemi e nella scoperta di farmaci.
Una piccola correzione: nel quarto paragrafo "per le reti aciclici" va corretto in "per le reti aciclìche" → **"per le reti aciclìche"** non è la forma standard; la forma corretta è **"per le reti aicliche"**... in realtà il termine giusto è **"per le reti acicliche"**. Ti consiglio di sostituire quella frase con: "fornendo risultati esatti per le reti acicliche e approssimazioni accurate per quelle cicliche."
File