Theoretical Models and Computational Techniques for the Analysis of Microbial Communities

Abstract

[eng] Microbial communities are complex ecosystems comprising diverse microorganisms that interact within a shared living space. Understanding their diversity and the relationships between population compositions is crucial for comprehending their dynamics and ecological significance. In this thesis, we focus on two key aspects: (1) biodiversity assessment in microbial communities and (2) analyzing virus-host relations in metagenomic and metaviromic samples using computational techniques. To assess microbial biodiversity, measures based on phylogenetic information have been proposed. The most popular such measure is Faith’s phylogenetic diversity (PD), which quantifies the diversity of phenotypic characters in a set of species using a phylogenetic tree. However, in microbial evolution, reticulate events such as genetic recombinations and lateral gene transfers play significant roles, making it necessary the use of phylogenetic networks. We develop an exchange property for the extension of PD to phylogenetic networks, allowing the characterization of subsets of species with maximal rPSD scores on up to semi-binary level-2 networks or semi-ternary level-1 networks via a polynomial time greedy algorithm. Furthermore, in the same context, we investigate the application of interaction indices from game theory to phylogenetic networks. These indices evaluate the contributions of coalitions of species to the overall phylogenetic diversity. We derive simplified expressions for the Shapley interaction index and the Banzhaf interaction index for various cooperative games with phylogenetic meaning defined on phylogenetic networks, including rooted and unrooted phylogenetic subnet diversity on rooted phylogenetic networks and phylogenetic subnet diversity on a very popular type of non rooted phylogenetic networks, the split networks. These expressions deepen our understanding of value and power distribution among species and groups of species. In the second part, we delve into the analysis of virus-host relations within microbial communities. The study of virus-host relationships in metagenomic samples is crucial for understanding the dynamics and impact of viruses in microbial communities. We begin by addressing the challenge of classification of viruses in metaviromic samples. Despite viruses being the most abundant life forms on Earth, there has been a lack of software for the taxonomic classification of metaviromic data. We propose a new tool, VPF-Class, based on Viral Protein Families (VPFs) that provides both a taxonomic classification and a host prediction. Then we introduce METEOR, a tool that integrates VPF-Class and metagenomic assignment tools like MegaBLAST and TANGO. The host predictions of viral sequences generated by VPF-Class are cross-validated and enriched with evidence about putative hosts present in a metagenomic sample obtained from the same microbial community, resulting in more accurate host predictions restricted to hosts present in the metagenomic sample. Finally, we address the challenge of aligning virus-host protein-protein interaction networks (PPIN). We present a compact integer linear programming formulation of the PPIN alignment problem, which can be solved using state-of-the-art mathematical modeling and integer linear programming software tools. We also provide empirical results demonstrating that small biological networks, such as virus-host PPIN in the STRING Viruses database, can be aligned in a reasonable amount of time on a personal computer, yielding structurally coherent and biologically meaningful alignments.

[spa] Las comunidades microbianas son ecosistemas complejos formados por diversos microorganismos que interactúan en un espacio vital compartido. Entender su diversidad y las relaciones entre las composiciones de las poblaciones es crucial para comprender su dinámica y su importancia ecológica. En esta tesis, nos centramos en dos aspectos clave: (1) la evaluación de la biodiversidad en comunidades microbianas y (2) el análisis de las relaciones virus-hospedador en muestras metagenómicas y metavirómicas mediante técnicas computacionales. Para evaluar la biodiversidad microbiana se han propuesto diversas medidas basadas en información filogenética. La más popular es la diversidad filogenética (PD) de Faith, que cuantifica la diversidad de caracteres fenotípicos en un conjunto de especies utilizando un árbol filogenético. Sin embargo, en la evolución microbiana, acontecimientos reticulares como las recombinaciones genéticas y las transferencias laterales de genes desempeñan papeles significativos, lo que hace necesario el uso de redes filogenéticas. En esta tesis desarrollamos una propiedad de intercambio para la extensión de la PD de Faith de árboles a redes filogenéticas (rPSD). Esto permite la caracterización, en tiempo polinómico, de subconjuntos de especies con puntuaciones rPSD máximas en redes filogenéticas del tipo semi-binarias nivel-2 o semi-ternarias nivel-1 mediante un algoritmo greedy. Además, en el mismo contexto, investigamos la aplicación de los índices de interacción de la teoría de juegos a las redes filogenéticas. Estos índices evalúan las contribuciones de las coaliciones de especies a la diversidad filogenética global. Así pues, derivamos expresiones simplificadas del índice de interacción de Shapley y el índice de interacción de Banzhaf, introducidos para varios juegos cooperativos, a índices con significado filogenético definidos sobre redes filogenéticas, incluyendo la diversidad de subredes filogenéticas enraizadas y no enraizadas en redes filogenéticas enraizadas, y también la diversidad de subredes filogenéticas en las redes split, una clase muy popular de redes filogenéticas no enraizadas. Estas expresiones profundizan nuestra comprensión del valor y la distribución de poder entre especies y grupos de especies. En la segunda parte de esta tesis, nos adentramos en el análisis de las relaciones virushospedador en el marco de las comunidades microbianas. El estudio de las relaciones virus-hospedador en muestras metagenómicas es crucial para comprender la dinámica y el impacto de los virus en las comunidades microbianas. Comenzamos abordando el reto de la clasificación de los virus en muestras metagenómicas. A pesar de que los virus son las formas de vida más abundantes en la Tierra, hay pocas herramientas informáticas para la clasificación taxonómica de los datos metavirómicos. En este trabajo proponemos una nueva herramienta, VPF-Class, basada en familias de proteínas virales (VPF), que proporciona tanto una clasificación taxonómica como una predicción del hospedador de una muestra metavirómica. A continuación presentamos METEOR, una herramienta que integra VPF-Class y herramientas de asignación metagenómica como MegaBLAST y TANGO. Las predicciones de hospedadores de secuencias virales generadas por VPF-Class se validan de forma cruzada y se enriquecen con evidencias sobre hospedadores putativos presentes en una muestra metagenómica obtenida de la misma comunidad microbiana, lo que da lugar a predicciones de hospedadores más precisas y restringidas a los hospedadores presentes en la muestra metagenómica. Por último, abordamos el reto de alinear las redes de interacciones proteína-proteína (PPIN) virus-huésped. Presentamos una formulación compacta mediante programación lineal entera del problema de alineación de PPIN, que puede resolverse utilizando programas estándar de modelización matemática y programación lineal entera. También mostramos resultados empíricos que prueban que las redes biológicas pequeñas, como las PPIN virushuésped de la base de datos STRING Viruses, pueden alinearse en un tiempo razonable en un ordenador personal, produciendo alineaciones estructuralmente coherentes y biológicamente significativas.

[cat] Les comunitats microbianes són ecosistemes complexos formats per diversos microorganismes que interactuen en un espai vital compartit. Entendre la seva diversitat i les relacions entre les composicions de les poblacions és crucial per a comprendre la seva dinàmica i la seva importància ecològica. En aquesta tesi, ens centrem en dos aspectes clau: (1) l’avaluació de la biodiversitat en comunitats microbianes i (2) l’anàlisi de les relacions virus-hoste en mostres metagenòmiques i metaviròmiques mitjançant tècniques computacionals. Per a avaluar la biodiversitat microbiana s’han proposat diverses mesures basades en informació filogenètica. La més popular és la diversitat filogenètica (PD) de Faith, que quantifica la diversitat de caràcters fenotípics en un conjunt d’espècies utilitzant un arbre filogenètic. No obstant això, en l’evolució microbiana, esdeveniments reticulars com les recombinacions genètiques i les transferències laterals de gens exerceixen papers significatius, la qual cosa fa necessari l’ús de xarxes filogenètiques. En aquesta tesi, introduïm una propietat d’intercanvi per a l’extensió de la PD de Faith d’arbres a xarxes filogenètiques (rPSD). Això ens permet caracteritzar, en temps polinòmic, subconjunts d’espècies amb puntuacions rPSD màximes a xarxes filogenètiques semi-binàries de nivell 2 o semiternàries de nivell 1, mitjançant un algorisme greedy. A més, en el mateix context, investiguem l’aplicació dels índexs d’interacció de la teoria de jocs a les xarxes filogenètiques. Aquests índexs avaluen les contribucions de les coalicions d’espècies a la diversitat filogenètica global. Així doncs, derivem expressions simplificades de l’índex d’interacció de Shapley i l’índex d’interacció de Banzhaf, introduïts per a diversos jocs cooperatius, a índexs amb significat filogenètic definits en xarxes filogenètiques, incloent-hi la diversitat de subxarxes filogenètiques arrelades i no arrelades en xarxes filogenètiques arrelades i també la diversitat de subxarxes filogenètiques a les xarxes split, una classe molt popular de xarxes filogenètiques no arrelades. Aquestes expressions aprofundeixen la nostra comprensió del valor i la distribució de poder entre espècies i grups d’espècies. En la segona part d’aquesta tesi, ens endinsem en l’anàlisi de les relacions virus-hoste en el marc de les comunitats microbianes. L’estudi de les relacions virus-hoste en mostres metagenòmiques és crucial per a comprendre la dinàmica i l’impacte dels virus en les comunitats microbianes. Comencem abordant el repte de la classificació dels virus en mostres metagenòmiques. Malgrat que els virus són les formes de vida més abundants en la Terra, hi ha poques eines informàtiques per a la classificació taxonòmica de les dades metaviròmiques. Proposem doncs una nova eina, VPF-Class, basada en famílies de proteïnes virals (VPF), que proporciona tant una classificació taxonòmica com una predicció de l’hoste. A continuació presentem METEOR, una eina que integra VPF-Class i eines d’assignació metagenòmica com MegaBLAST i TANGO. Les prediccions d’hostes de seqüències virals generades per VPF-Class es validen de forma creuada i s’enriqueixen amb evidències sobre hostes putatius presents en una mostra metagenòmica obtinguda de la mateixa comunitat microbiana, la qual cosa resulta en prediccions d’hostes més precises i restringides als hostes presents en la mostra metagenòmica. Finalment, abordem el repte d’alinear les xarxes d’interaccions proteïna-proteïna (PPIN) virus-hoste. Presentem una formulació compacta mitjançant programació lineal entera del problema d’alineació de PPIN, que pot resoldre’s utilitzant programes estàndard de modelització matemàtica i programació lineal entera. També proporcionem resultats emiv pírics que demostren que les xarxes petites, com les PPIN virus-hoste de la base de dades STRING Viruses, poden alinear-se en un temps raonable en un ordinador personal, produint alineacions estructuralment coherents i biològicament significatives.