SAWSA-LPR: Astochastic search strategy for estimation of maximum likelihood DNA phylogenetic trees

In the spirit of the “grand challenge”, this paper covers the development of novel concepts for inference of large phylogenies based on the maximum likelihood method, which has proved to be the most accurate model for inference of huge and complex phylogenetic trees. Here, a novel method called Leaf Pruning and Re-grafting (LPR) has being presented, which is a variant of standard Sub-tree Pruning and Re-grafting (SPR) technique. LPR is a systematic approach where only unique topologies are generated at each step. Various stochastic search strategies for estimation of the maximum likelihood (ML) tree have also being proposed. Here, simulated annealing has been combined with steepest accent method to improve the quality of the final tree obtained. All the current simulated annealing approaches are used with simple hill climbing method to avoid the large number of repeated topologies that are normally generated by SPR. This easily leads to local maxima. However in the present study steepest accent with simulated annealing by way of LPR (SAWSA-LPR) has being used; the chances of returning local maxima has being significantly reduced. A straightforward and efficient parallel version of simulated annealing with steepest accent to accelerate the process of DNA phylogenetic tree inference has also being presented. It was observed that the implementation of the algorithm based on random DNA sequences gave better results as compared to other tree construction methods.