Adaptive memory programming: local search parallel algorithms for phylogenetic tree construction

One of the most important aspect of molecular and computational biology is the reconstruction of evolutionary relationships. The area is well explored after decades of intensive research. Despite this fact there remains a need for good and efficient algorithms that are capable of reconstructing the evolutionary relationship in reasonable time. Since the problem is computationally intractable, exact algorithms are used only for small groups of species. In the Maximum Parsimony approach the time of computation grows so fast when number of sequences increases, that in practice it is possible to find the optimal solution for instances containing about 20 sequences only. It is this reason that in practical applications, heuristic methods are used. In this paper, parallel adaptive memory programming algorithms based on Maximum Parsimony and some known neighborhood search methods for phylogenetic tree construction are proposed, and the results of computational experiments are presented. The proposed algorithms achieve a superlinear speedup and find solutions of good quality.