Sparse unsupervised learning for metagenomic data
Institution:
université Paris-SaclayDisciplines:
Directors:
Abstract EN:
The development of massively parallel sequencing technologies enables to sequence DNA at high-throughput and low cost, fueling the rise of metagenomics which is the study of complex microbial communities sequenced in their natural environment.Metagenomic problems are usually computationally difficult and are further complicated by the massive amount of data involved.In this thesis we consider two different metagenomics problems: 1. raw reads binning and 2. microbial network inference from taxonomic abundance profiles. We address them using unsupervised machine learning methods leveraging the parsimony principle, typically involving l1 penalized log-likelihood maximization.The assembly of genomes from raw metagenomic datasets is a challenging task akin to assembling a mixture of large puzzles composed of billions or trillions of pieces (DNA sequences). In the first part of this thesis, we consider the related task of clustering sequences into biologically meaningful partitions (binning). Most of the existing computational tools perform binning after read assembly as a pre-processing, which is error-prone (yielding artifacts like chimeric contigs) and discards vast amounts of information in the form of unassembled reads (up to 50% for highly diverse metagenomes). This motivated us to try to address the raw read binning (without prior assembly) problem. We exploit the co-abundance of species across samples as discriminative signal. Abundance is usually measured via the number of occurrences of long k-mers (subsequences of size k). The use of Local Sensitive Hashing (LSH) allows us to contain, at the cost of some approximation, the combinatorial explosion of long k-mers indexing. The first contribution of this thesis is to propose a sparse Non-Negative Matrix factorization (NMF) of the samples x k-mers count matrix in order to extract abundance variation signals. We first show that using sparse NMF is well-grounded since data is a sparse linear mixture of non-negative components. Sparse NMF exploiting online dictionary learning algorithms retained our attention, including its decent behavior on largely asymmetric data matrices. The validation of metagenomic binning being difficult on real datasets, because of the absence of ground truth, we created and used several benchmarks for the different methods evaluated on. We illustrated that sparse NMF improves state of the art binning methods on those datasets. Experiments conducted on a real metagenomic cohort of 1135 human gut microbiota showed the relevance of the approach.In the second part of the thesis, we consider metagenomic data after taxonomic profiling: multivariate data representing abundances of taxa across samples. It is known that microbes live in communities structured by ecological interaction between the members of the community. We focus on the problem of the inference of microbial interaction networks from taxonomic profiles. This problem is frequently cast into the paradigm of Gaussian graphical models (GGMs) for which efficient structure inference algorithms are available, like the graphical lasso. Unfortunately, GGMs or variants thereof can not properly account for the extremely sparse patterns occurring in real-world metagenomic taxonomic profiles. In particular, structural zeros corresponding to true absences of biological signals fail to be properly handled by most statistical methods. We present in this part a zero-inflated log-normal graphical model specifically aimed at handling such "biological" zeros, and demonstrate significant performance gains over state-of-the-art statistical methods for the inference of microbial association networks, with most notable gains obtained when analyzing taxonomic profiles displaying sparsity levels on par with real-world metagenomic datasets.
Abstract FR:
Les avancées technologiques dans le séquençage ADN haut débit ont permis à la métagénomique de considérablement se développer lors de la dernière décennie. Le séquencage des espèces directement dans leur milieu naturel a ouvert de nouveaux horizons dans de nombreux domaines de recherche. La réduction des coûts associée à l'augmentation du débit fait que de plus en plus d'études sont lancées actuellement.Dans cette thèse nous considérons deux problèmes ardus en métagénomique, à savoir le clustering de lectures brutes et l'inférence de réseaux microbiens. Pour résoudre ces problèmes, nous proposons de mettre en oeuvre des méthodes d'apprentissage non supervisées utilisant le principe de parcimonie, ce qui prend la forme concrète de problèmes d'optimisation avec une pénalisation de norme l1.Dans la première partie de la thèse, on considère le problème intermédiaire du clustering des séquences ADN dans des partitions biologiquement pertinentes (binning). La plupart des méthodes computationelles n'effectuent le binning qu'après une étape d'assemblage qui est génératrice d'erreurs (avec la création de contigs chimériques) et de pertes d'information. C'est pourquoi nous nous penchons sur le problème du binning sans assemblage préalable. Nous exploitons le signal de co-abondance des espèces au travers des échantillons mesuré via le comptage des k-mers (sous-séquences de taille k) longs. L'utilisation du Local Sensitive Hashing (LSH) permet de contenir, au coût d'une approximation, l'explosion combinatoire des k-mers possibles dans un espace de cardinal fixé. La première contribution de la thèse est de proposer l'application d'une factorisation en matrices non-négatives creuses (sparse NMF) sur la matrice de comptage des k-mers afin de conjointement extraire une information de variation d'abondance et d'effectuer le clustering des k-mers. Nous montrons d'abord le bien fondé de l'approche au niveau théorique. Puis, nous explorons dans l'état de l'art les méthodes de sparse NMF les mieux adaptées à notre problème. Les méthodes d'apprentissage de dictionnaire en ligne ont particulièrement retenu notre attention de par leur capacité à passer à l'échelle pour des jeux de données comportant un très grand nombre de points. La validation des méthodes de binning en métagénomique sur des données réelles étant difficile à cause de l'absence de vérité terrain, nous avons créé et utilisé plusieurs jeux de données synthétiques pour l'évaluation des différentes méthodes. Nous montrons que l'application de la sparse NMF améliore les méthodes de l'état de l'art pour le binning sur ces jeux de données. Des expérience sur des données métagénomiques réelles issus de 1135 échantillons de microbiotes intestinaux d'individus sains ont également été menées afin de montrer la pertinence de l'approche.Dans la seconde partie de la thèse, on considère les données métagénomiques après le profilage taxonomique, c'est à dire des donnés multivariées représentant les niveaux d'abondance des taxons au sein des échantillons. Les microbes vivant en communautés structurées par des interactions écologiques, il est important de pouvoir identifier ces interactions. Nous nous penchons donc sur le problème de l'inférence de réseau d'interactions microbiennes à partir des profils taxonomiques. Ce problème est souvent abordé dans le cadre théorique des modèles graphiques gaussiens (GGM), pour lequel il existe des algorithmes d'inférence puissants tel que le graphical lasso. Mais les méthodes statistiques existantes sont très limitées par l'aspect extrêmement creux des profils taxonomiques que l'on rencontre en métagénomique, notamment par la grande proportion de zéros dits biologiques (i.e. liés à l'absence réelle de taxons). Nous proposons un model log normal avec inflation de zéro visant à traiter ces zéros biologiques et nous montrons un gain de performance par rapport aux méthodes de l'état de l'art pour l'inférence de réseau d'interactions microbiennes.