Inference of evolutionary trees based on the maximum likelihood method is NP-hard. Thus, the introduction of heuristics to reduce the search space in terms of potential trees evaluated becomes inevitable. This paper represents a heuristic, called PSOML, for evolutionary tree reconstruction using particle swarm optimization (PSO). In particular, the state update of particles during iterations is accomplished by some topological rearrangement. The topological transformations currently include Nearest Neighbor Interchange (NNI), Subtree Prune and Regraft (SPR), Tree Bisection and Reconnection (TBR) and p-Edge Contraction and Refinement (p-ECR). Due to that the search space is wide and the size of the search space can be adaptively adjusted, p-ECR is adopted in PSOML. However, p-ECR is expensive in terms of computation. In order to make p-ECR efficient, this paper also proposes a new method by using the Neighbor Joining (NJ) method to refine the unresolved nodes produced in p-ECR. We conduct experiments with real datasets to compare PSOML with three recently developed maximum likelihood programs that have previously been shown to outperform others. Results show that PSOML clearly outperforms PHYML and RAxML in terms of solution optimality, although it cannot compete in terms of runtimes. Moreover, PSOML can find better trees than GARLI across a range of datasets in considerable time.
evolutionary tree, maximum likelihood, topological transformations, Particle Swarm optimization, p-Edge Contraction and Refinement (p-ECR)
