Efficient algorithms for simulating sequences along a phylogenetic tree
Open Access
- 29 December 2025
- journal article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (1)
Abstract
Motivation: Sequence simulations along phylogenetic trees play an important role in numerous molecular evolution studies such as benchmarking algorithms for ancestral sequence reconstruction, multiple sequence alignment, and phylogeny inference. They are also used in phylogenetic model-selection tasks, including the inference of selective forces. Recently, Approximate Bayesian Computation (ABC)-based approaches have been developed for inferring parameters of complex evolutionary models, which rely on massive generation of simulated data. For all these applications, computationally efficient sequence simulators are essential. Results: In this study, we investigate fast algorithms for simulating sequences along a phylogenetic tree, focusing on accelerating the speed-limiting component of the simulation process: handling insertion and deletion (indel) events. We demonstrate that data structures which efficiently store indel events along a tree can substantially accelerate the simulation process compared to a naive approach. To illustrate the utility of this efficient simulator, we integrated it into an ABC-based algorithm for inferring indel model parameters and applied it to study indel dynamics within Chiroptera. Availability and implementation: The source code for the different simulation algorithms, alongside the data used, is available at: https://github.com/nimrodSerokTAU/evo-sim. The simulator has also been integrated into SpartaABC, a website for the inference of indel parameters, accessible at: https://spartaabc.tau.ac.il/.Keywords
Funding Information
- Israel Science Foundation (2818/21)
This publication has 63 references indexed in Scilit:
- MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transformNucleic Acids Research, 2002
- Separation of phylogenetic and functional associations in biological sequences by using the parametric bootstrapProceedings of the National Academy of Sciences, 2000
- Combining protein evolution and secondary structureMolecular Biology and Evolution, 1996
- Small genomes for better flyersNature, 1995
- A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates.Molecular Biology and Evolution, 1994
- Relative efficiencies of the maximum-likelihood, neighbor-joining, and maximum-parsimony methods when substitution rate varies with site.Molecular Biology and Evolution, 1994
- Simple diagnostic statistical tests of models for DNA substitutionJournal of Molecular Evolution, 1993
- Empirical and Structural Models for Insertions and Deletions in the Divergent Evolution of ProteinsJournal of Molecular Biology, 1993
- The rapid generation of mutation data matrices from protein sequencesBioinformatics, 1992
- Deletions in processed pseudogenes accumulate faster in rodents than in humansJournal of Molecular Evolution, 1989