Stochastic search strategy for estimation of maximum likelihood phylogenetic trees

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Maximum Likelihood (ML) is a powerful method for phylogenetic tree construction.
• Its application is limited by high computational cost, especially for large sequence datasets.
• Existing algorithms can be slow and prone to getting stuck in local optima.

Purpose of the Study:

• To develop a faster and more robust method for estimating Maximum Likelihood phylogenetic trees.
• To address the computational challenges associated with large-scale phylogenetic analyses.
• To improve the accuracy and efficiency of phylogenetic tree inference.

Main Methods:

• A novel stochastic search strategy based on a simulated annealing algorithm was developed.
• The algorithm utilizes a local rearrangement strategy to explore tree space.
• Acceptance of topological changes is based on likelihood improvement or a probability related to likelihood decrease.

Main Results:

• The proposed algorithm significantly reduces the time required for ML tree estimation.
• The stochastic search strategy is less likely to become trapped in local optima compared to existing methods.
• Successful demonstration on theoretical and real biological data examples, outperforming PAUP* and DNAMLK.

Conclusions:

• The simulated annealing-based stochastic search offers an efficient and reliable approach for Maximum Likelihood phylogenetic tree construction.
• This method effectively overcomes the computational bottlenecks of traditional ML approaches.
• It provides a valuable tool for large-scale phylogenetic studies in bioinformatics and computational biology.