Bacteria are everywhere and play essential roles in Earth's diverse ecosystems and human health. For example, humans harbor a complex and essential gut microbial community comprising thousands of bacterial species (in addition to numerous viruses, fungi, and microbial eukaryotes). This community helps break down and synthesize nutrients, trains the immune system, and keeps pathogens at bay. However, imbalances in this community are associated with several diseases, including obesity, inflammatory bowel syndrome, and recurrent urinary tract infections. Moreover, bacteria can cause deadly infections, and many are developing resistance to our most potent antibiotics. Studying bacteria is thus essential for identifying differences between pathogens and harmless commensals, countering antimicrobial resistance, and understanding their impacts on human health.

To study bacteria, we typically characterize and compare their genomes. The genome comprises all of an organism's hereditary information, and its genes encode the molecular machines necessary for cell function, providing an overview of an organism's capabilities. The hereditary information in genomes additionally enables inferring the organism's evolutionary history, which helps in understanding why specific traits evolved or aid in inferring transmission links in case of an outbreak.

A challenge with comparing large sets of bacterial genomes is the extensive variation in genome content among many species. For example, two Escherichia coli strains can share as little as 50% of their genes. Current computational tools offer biased or incomplete views of genetic variation among strains. This hinders the identification of genotype-phenotype associations, prevents tracking mobile genetic elements, and limits our understanding of the microbial communities they are part of.

The central question of this thesis is how to design computational tools that enable accurate characterization of genetic variation among diverse bacterial genomes. This thesis introduces new algorithms to identify and represent genetic variation using graph data structures. It additionally presents a tool that characterizes strain-specific genetic variation in microbial communities, even in the presence of same-species strain mixtures. Finally, this thesis uses the previously mentioned tools to investigate the role of the gut microbiome in women with recurrent urinary tract infections, offering novel insights into the gut and bladder dynamics of  E. coli.

Collectively, we expect this work to contribute to an improved mechanistic understanding of bacteria's role in human health, help track and counter the spread of antimicrobial resistance, and inform on the development of microbiome-mediated therapeutics.@en

Motivation
Partial order alignment is a widely used method for computing multiple sequence alignments, with applications in genome assembly and pangenomics, among many others. Current algorithms to compute the optimal, gap-affine partial order alignment do not scale well to larger graphs and sequences. While heuristic approaches exist, they do not guarantee optimal alignment and sacrifice alignment accuracy.

Results
We present POASTA, a new optimal algorithm for partial order alignment that exploits long stretches of matching sequence between the graph and a query. We benchmarked POASTA against the state-of-the-art on several diverse bacterial gene datasets and demonstrated an average speed-up of 4.1x and up to 9.8x, using less memory. POASTA’s memory scaling characteristics enabled the construction of much larger POA graphs than previously possible, as demonstrated by megabase-length alignments of 342 Mycobacterium tuberculosis sequences.@en

Low-abundance members of microbial communities are difficult to study in their native habitats, including Escherichia coli, a minor but common inhabitant of the gastrointestinal tract, and key opportunistic pathogen of the urinary tract. While multi-omic analyses have detailed interactions between uropathogenic Escherichia coli (UPEC) and the bladder mediating urinary tract infection (UTI), little is known about UPEC in its pre-infection reservoir, the gastrointestinal tract, partly due to its low relative abundance (<1%). To sensitively explore the genomes and transcriptomes of diverse gut E. coli, we develop E. coli PanSelect, which uses probes designed to specifically capture E. coli’s broad pangenome. We demonstrate its ability to enrich diverse E. coli by orders of magnitude, in a mock community and in human stool from a study investigating recurrent UTI (rUTI). Comparisons of transcriptomes between gut E. coli of women with and without history of rUTI suggest rUTI gut E. coli are responding to increased oxygen and nitrate, suggestive of mucosal inflammation, which may have implications for recurrent disease. E. coli PanSelect is well suited for investigations of in vivo E. coli biology in other low-abundance environments, and the framework described here has broad applicability to other diverse, low-abundance organisms.@en

Recurrent urinary tract infections (rUTIs) are a major health burden worldwide, with history of infection being a significant risk factor. While the gut is a known reservoir for uropathogenic bacteria, the role of the microbiota in rUTI remains unclear. We conducted a year-long study of women with (n = 15) and without (n = 16) history of rUTI, from whom we collected urine, blood and monthly faecal samples for metagenomic and transcriptomic interrogation. During the study 24 UTIs were reported, with additional samples collected during and after infection. The gut microbiome of individuals with a history of rUTI was significantly depleted in microbial richness and butyrate-producing bacteria compared with controls, reminiscent of other inflammatory conditions. However, Escherichia coli gut and bladder populations were comparable between cohorts in both relative abundance and phylogroup. Transcriptional analysis of peripheral blood mononuclear cells revealed expression profiles indicative of differential systemic immunity between cohorts. Altogether, these results suggest that rUTI susceptibility is in part mediated through the gut–bladder axis, comprising gut dysbiosis and differential immune response to bacterial bladder colonization, manifesting in symptoms.

@en

Human-associated microbial communities comprise not only complex mixtures of bacterial species, but also mixtures of conspecific strains, the implications of which are mostly unknown since strain level dynamics are underexplored due to the difficulties of studying them. We introduce the Strain Genome Explorer (StrainGE) toolkit, which deconvolves strain mixtures and characterizes component strains at the nucleotide level from short-read metagenomic sequencing with higher sensitivity and resolution than other tools. StrainGE is able to identify strains at 0.1x coverage and detect variants for multiple conspecific strains within a sample from coverages as low as 0.5x.

@en