Efficient algorithms for simulating sequences along a phylogenetic tree

Area of Science:

• Computational Biology
• Molecular Evolution
• Bioinformatics

Background:

• Sequence simulations on phylogenetic trees are crucial for benchmarking algorithms and inferring evolutionary models.
• Approximate Bayesian Computation (ABC) methods require extensive simulated data for complex evolutionary models.
• Computationally efficient sequence simulators are essential for advancing molecular evolution research.

Purpose of the Study:

• To develop and investigate fast algorithms for simulating sequences along phylogenetic trees.
• To accelerate the simulation process by optimizing the handling of insertion and deletion (indel) events.
• To integrate an efficient simulator into an ABC-based algorithm for inferring indel model parameters.

Main Methods:

• Developed and evaluated data structures for efficient storage of indel events along phylogenetic trees.
• Compared the performance of novel simulation algorithms against a naive approach.
• Integrated the efficient simulator into an Approximate Bayesian Computation (ABC) framework.

Main Results:

• Efficient data structures for indel events significantly accelerate sequence simulation along phylogenetic trees.
• The developed simulator demonstrates substantial speed improvements over naive methods.
• The integrated simulator was successfully applied to study indel dynamics in Chiroptera using ABC.

Conclusions:

• Optimized handling of indel events is key to accelerating phylogenetic sequence simulations.
• The new efficient simulator enhances the feasibility of computationally intensive phylogenetic analyses.
• This work provides a valuable tool for inferring indel model parameters and studying evolutionary dynamics.