KOMB: Graph-Based Characterization of Genome Dynamics in Microbial Communities

Abstract

Characterizing metagenomic samples via kmer-based, database-dependent taxonomic classification methods has provided crucial insight into underlying host-associated microbiome dynamics. However, novel approaches are needed that are able to track microbial community dynamics within metagenomes to elucidate genome flux in response to perturbations and disease states. Here we describe KOMB, a novel approach for tracking homologous regions within microbiomes. KOMB utilizes K-core graph decomposition on metagenome assembly graphs to identify repetitive and homologous regions to varying degrees of resolution. K-core performs a hierarchical decomposition which partitions the graph into shells containing nodes having degree at least K, called K-shells, yielding O(V + E) complexity compared to exact betweenness centrality complexity of O(V E) found in prior related approaches. We show through rigorous validation on simulated, synthetic, and real metagenomic datasets that KOMB accurately recovers and profiles repetitive and homologous genomic regions across organisms in the sample. KOMB can also identify functionally-rich regions in Human Microbiome Project (HMP) datasets, and can be used to analyze longitudinal data and identify pivotal taxa in fecal microbiota transplantation (FMT) samples. In summary, KOMB represents a novel approach to microbiome characterization that can efficiently identify sequences of interest in metagenomes.

Publication
Advait Balaji
Advait Balaji
PhD student

Advait (4th year PhD student) obtained a dual degree, B.E Computer Science and MS Biological Sciences from BITS, Pilani in India. During his undergraduate degree, he received the Khorana Scholarship (2016) from the Indo-US Science and Technology Forum and also a thesis fellowship (2017-18) to work at Icahn School of Medicine, Mount Sinai, NY. At Mount Sinai, he worked on creating a Sub-cellular process-based ontology that predicts whole cell function using Natural Language Processing. His research interests are at the intersection of genomic data science and designing efficient algorithms to analyze genomic data.

Nicolae Sapoval
Nicolae Sapoval
PhD student

Nick (3rd year PhD student) obtained a B.S. degree in Computer Science and a B.S. with Honors in Mathematics from the University of Chicago. At the University of Chicago Nick worked in wireless networks research and later in computational biophysics focusing on conformational transition modeling for insulin degrading enzyme. His current interests are in the areas of computational biology with a focus on genomic data.

R.A. Leo Elworth
R.A. Leo Elworth
NLM Postdoctoral Fellow

Leo (NLM Postdoctoral Fellow, primary mentor Prof. Lauren Stadler, secondary mentor Prof. Todd Treangen) received his PhD in Computer Science at Rice University in 2019 working on statistical modeling of DNA sequence evolution. He was advised by Dr. Luay Nakhleh, the J.S. Abercrombie Professor and Chair of the Department of Computer Science at Rice. Since joining at Rice, Leo was awarded a graduate research fellowship from the National Library of Medicine, has published work in computational biology in journals such as Bioinformatics, presented research at scientific conferences like RECOMB-CG in Barcelona and WABI in Helsinki, and contributed to a soon to be released book on computational modeling of evolutionary histories of genomes.

Next
Previous

Related