Efficient inference of recent and ancestral recombination within bacterial populations

Rafal Mostowy, Nicholas J. Croucher, Cheryl P. Andam, Jukka Corander, William P. Hanage, Pekka Marttinen

Abstract

Prokaryotic evolution is affected by horizontal transfer of genetic material through recombination. Inference of an evolutionary tree of bacteria thus relies on accurate identification of the population genetic structure and recombination-derived mosaicism. Rapidly growing databases represent a challenge for computational methods to detect recombinations in bacterial genomes. We introduce a novel algorithm called fastGEAR which identifies lineages in diverse microbial alignments, and recombinations between them and from external origins. The algorithm detects both recent recombinations (affecting a few isolates) and ancestral recombinations between detected lineages (affecting entire lineages), thus providing insight into recombinations affecting deep branches of the phylogenetic tree. In simulations, fastGEAR had comparable power to detect recent recombinations and outstanding power to detect the ancestral ones, compared to state-of-the-art methods, often with a fraction of computational cost. We demonstrate the utility of the method by analysing a collection of 616 whole-genomes of a recombinogenic pathogen Streptococcus pneumoniae, for which the method provided a high-resolution view of recombination across the genome. We examined in detail the penicillin-binding genes across the Streptococcus genus, demonstrating previously undetected genetic exchanges between different species at these three loci. Hence, fastGEAR can be readily applied to investigate mosaicism in bacterial genes across multiple species. Finally, fastGEAR correctly identified many known recombination hotspots and pointed to potential new ones.

Introduction

Bacteria do not evolve solely through simple vertical descent. Instead, their evolutionary history is frequently punctuated by horizontal gene transfer, or recombination, where genetic material is swapped between individuals. This process creates "mosaic" genomes that defy traditional phylogenetic tree models. As genomic databases expand to include thousands of isolates, existing computational tools face significant hurdles. Most current methods struggle with scalability and often focus exclusively on "recent" recombination events—those affecting only a few individuals at the tips of the tree. Consequently, they miss "ancestral" recombinations that occurred long ago and are now fixed within entire lineages. Identifying these deep-branch events is essential for a complete understanding of bacterial evolution.

The fastGEAR Algorithm

To address these challenges, we developed fastGEAR, a scalable algorithm designed to identify lineages and detect both recent and ancestral recombinations. The framework distinguishes between three temporal classes of recombination events based on their position in the phylogeny.

The diagram illustrates the three types of recombination: ancestral (1), intermediate (2), and recent (3).

The algorithm employs a multi-step approach centered on Hidden Markov Models (HMMs) to analyze polymorphic sites in DNA alignments:

  1. Lineage Identification: Sequences are clustered into lineages using a combination of the BAPS algorithm and HMM-based refinement.
  2. Recent Recombination Detection: For each strain, an HMM identifies segments likely originating from a different lineage or an unknown external source.
  3. Ancestral Recombination Detection: The tool compares pairs of lineages to find segments where they are unexpectedly similar, indicating a recombination event that occurred before the lineages diversified.
  4. Significance Testing: To minimize false positives, a post-processing step uses Bayes Factors based on SNP density to ensure "recombinant" segments are statistically distinct from the background.
HMM logic for identifying lineages (A) and recent recombinations (B).

By modeling allele frequencies with HMMs rather than full Markov Chain Monte Carlo (MCMC) simulations, fastGEAR achieves a massive speedup—operating roughly 1.5 to 2 orders of magnitude faster than traditional tools like STRUCTURE.

Results and Biological Insights

We validated fastGEAR using both coalescent simulations and real-world datasets. In simulations, the tool demonstrated "outstanding power" to detect ancestral recombinations where other state-of-the-art methods often failed.

Streptococcus pneumoniae and Inter-species Exchange

Analysis of 616 S. pneumoniae whole-genomes revealed a high-resolution map of recombination across the species. The tool successfully identified known recombination hotspots, such as the pspC gene, and suggested new ones, including the chromosome partitioning protein SMC.

Crucially, fastGEAR provided new insights into the spread of antibiotic resistance. By examining penicillin-binding protein (PBP) genes across the Streptococcus genus, we found clear evidence of genetic "shuffling" between different species (e.g., S. mitis and S. oralis). This suggests that inter-species recombination is a primary driver for the dissemination of resistance genes.

Discussion and Limitations

While fastGEAR offers significant advancements, some limitations remain. Determining the exact directionality of ancestral events (donor vs. recipient) remains difficult and currently relies on parsimony-based assumptions. Additionally, the tool does not detect intra-lineage recombination, as these events often lack sufficient diversity to be statistically detectable. Future work may involve integrating fastGEAR into pan-genome assembly pipelines to further enhance its utility in large-scale genomic studies.

Summary updated

Abstract

Abstract Prokaryotic evolution is affected by horizontal transfer of genetic material through recombination. Inference of an evolutionary tree of bacteria thus relies on accurate identification of the population genetic structure and recombination-derived mosaicism. Rapidly growing databases represent a challenge for computational methods to detect recombinations in bacterial genomes. We introduce a novel algorithm called fastGEAR which identifies lineages in diverse microbial alignments, and recombinations between them and from external origins. The algorithm detects both recent recombinations (affecting a few isolates) and ancestral recombinations between detected lineages (affecting entire lineages), thus providing insight into recombinations affecting deep branches of the phylogenetic tree. In sim-ulations, fastGEAR had comparable power to detect recent recombinations and outstanding power to detect the ancestral ones, compared to state-of-the-art methods, often with a fraction of computational cost. We demonstrate the utility of the method by analysing a collection of 616 whole-genomes of a recombinogenic pathogen Streptococcus pneumoniae , for which the method provided a high-resolution view of recombination across the genome. We examined in detail the penicillin-binding genes across the Streptococcus genus, demonstrating previously undetected genetic exchanges between different species at these three loci. Hence, fastGEAR can be readily applied to investigate mosaicism in bacterial genes across multiple species. Finally, fastGEAR correctly identified many known recombination hotspots and pointed to potential new ones. Matlab code and Linux/Windows executables are available at https://users.ics.aalto.fi/~pemartti/fastGEAR/
BibTeX
@inproceedings{mostowy2017efficient,
  author = {Rafal Mostowy and Nicholas J. Croucher and Cheryl P. Andam and Jukka Corander and William P. Hanage and Pekka Marttinen},
  title = {{Efficient inference of recent and ancestral recombination within bacterial populations}},
  booktitle = {Molecular},
  year = {2017},
  doi = {10.1093/molbev/msx066},
}
Figure