Graph-theoretic Approaches to Metagenomics Analysis: Entropy, Network Topology and Algorithm

Abstract

The human microbiome represents one of the most complex and dynamic ecosystems on Earth, harboring trillions of microorganisms that collectively influence human health through intricate networks of molecular interactions. Understanding the organizational principles and interaction dynamics governing these microbial communities is essential for developing effective strategies to address microbiome-related health issues. This dissertation presents novel computational frameworks for analyzing three critical aspects of microbiome organization and function: horizontal gene transfer networks, functional redundancy hierarchies, and metabolic cooperation networks.

First, We deduced the first comprehensive plasmid-mediated HGT network using 214,950 plasmid taxonomic units (PTUs) sourced from the IMG/PR database. In this network, taxa serve as vertices, with edges symbolizing potential gene exchanges facilitated by plasmids. This network demonstrates a hierarchical structure and high robustness. The network edges exhibit strong specificity to particular environments, while they exhibit similarity and generality across various categories of antibiotic-resistance genes (ARGs). Further, we observed a consistent preservation of plasmid-mediated communication ability in gut microbiome after antibiotic exposure in two independent experiments of antibiotic exposure.

Second, we represented functional redundancy as a network and developed a structural entropy (SE)-based approach to elucidate FR hierarchy, revealing functional redundancy clusters (FRCs) - groups of species capable of independently executing specific metabolic pathways. Through controlled simulations and cross-cohort analyses spanning 4,912 gut metagenomes across 28 disease cohorts, we established that our approach offers higher resolution, more comprehensive measurement, and greater robustness in detecting disease-associated functional patterns than traditional FR methods. This methodology establishes a novel perspective for understanding microbiome stability through personalized FR networks, positioning FRCs as promising diagnostic markers and therapeutic targets for microbiome-associated diseases.

Third, we developed an innovative algorithm for analyzing cooperation in metabolic networks of the microbiome, addressing the limitations of existing approaches by capturing both direct and indirect metabolic interactions. This comprehensive metabolic interaction network approach allows for the identification of complex cooperative relationships that would be overlooked by methods focusing solely on direct exchanges. Our work provides a more nuanced understanding of the metabolic interdependencies and impact of speceis in microbiome functional cooperation.

Together, these computational frameworks and biological insights advance our understanding of the complex organizational principles and interaction dynamics that govern microbial communities in the human microbiome. The approaches and findings presented in this dissertation offer tools for research in microbiome, with potential applications in personalized medicine and microbiome-based interventions.

Date of Award	21 Jan 2026
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Shuaicheng LI (Supervisor) & Jufang HE (Co-supervisor)