KOMB

KOMB applies K-core graph decomposition to metagenome assembly graphs to identify repetitive and homologous regions and thereby characterize microbial community dynamics for longitudinal and functional analysis.

Key Features:

• K-core Graph Decomposition: Performs K-core decomposition on metagenome assembly graphs, partitioning the graph into hierarchical K-shells containing nodes of at least degree K to locate repetitive and homologous regions.
• Efficiency: Executes with computational complexity O(V + E) on the assembly graph (V vertices, E edges), improving on exact betweenness centrality approaches with O(VE) complexity.
• Resolution and Validation: Validated on simulated, synthetic, and real metagenomic datasets and shown to recover and profile repetitive and homologous genomic regions across organisms.
• Functional Insights: Identifies functionally rich regions in datasets such as the Human Microbiome Project (HMP).
• Longitudinal and Perturbation Analysis: Supports analysis of longitudinal data and perturbation studies, including identification of pivotal taxa in fecal microbiota transplantation (FMT) samples and changes associated with disease states.

Scientific Applications:

• Microbiome Dynamics Studies: Tracking homologous regions to characterize temporal changes and community evolution without relying on predefined taxonomic databases.
• Disease Research: Investigating microbiome changes associated with disease states and therapeutic interventions through longitudinal and perturbation analysis.
• Functional Genomics: Pinpointing functionally significant genomic regions within metagenomes to link sequence repeats and homology with potential community functions.

Methodology:

Apply K-core graph decomposition to metagenome assembly graphs, partition into K-shells of nodes with degree ≥ K to identify repetitive and homologous regions, with algorithmic complexity O(V + E), and validate results on simulated, synthetic, and real metagenomic datasets.