Efficient inference of bacterial strain trees from genome-scale multilocus data.

Area of Science:

• Computational Biology
• Evolutionary Genetics
• Bioinformatics

Background:

• Inferring bacterial strain trees is crucial for understanding population evolution, divergence, and events like horizontal gene transfer and homologous recombination.
• High gene tree incongruence, caused by homologous recombination, presents a significant challenge in accurately reconstructing bacterial evolutionary histories from multilocus data.

Purpose of the Study:

• To develop a novel computational method for inferring bacterial strain trees that overcomes the challenge of massive gene tree incongruence.
• To accurately estimate divergence times and resolve the evolutionary history of bacterial strains, particularly in strongly isolated populations.

Main Methods:

• A three-phase computational approach was developed: candidate strain-tree topology generation using maximal cliques, divergence time estimation via mixed integer linear programming (MILP), and optimal tree selection based on an optimality criterion.
• The algorithms were implemented in the publicly available PhyloNet software package.

Main Results:

• The method successfully inferred a fully resolved (binary) strain tree with estimated divergence times for nine strains of Staphylococcus aureus.
• The analysis handled high degrees of sequence identity and significant gene tree incongruence, demonstrating the method's robustness.
• The computational efficiency makes the method suitable for large-scale genomic datasets, including challenging analyses of strongly isolated populations.

Conclusions:

• The novel method effectively reconstructs bacterial strain trees despite substantial gene tree incongruence.
• This approach enhances the analysis of bacterial evolution, especially in complex and isolated populations, by providing accurate evolutionary histories and divergence times.