Lower bounds for maximum parsimony with gene order data

In this paper, we study lower bound techniques for branch-and-bound algorithms for maximum parsimony, with a focus on gene order data. We give a simple O(n ³) time dynamic programming algorithm for computing the maximum circular ordering lower bound, where n is the number of leaves. The well-known gene order phylogeny program, GRAPPA, currently implements two heuristic approximations to this lower bounds. Our experiments show a significant improvement over both these methods in practice. Next, we show that the linear programming-based lower bound of Tang and Moret (Tang and Moret, 2005) can be greatly simplified, allowing us to solve the LP in O*n ³) time in the worst case, and in O*(n ^2.5) time amortized over all binary trees. Finally, we formalize the problem of computing the circular ordering lower bound, when the tree topologies are generated bottom-up, as a Path-Constrained Traveling Salesman Problem, and give a polynomial-time 3-approximation algorithm for it. This is a special case of the more general Precedence-Constrained Travelling Salesman Problem and has not previously been studied, to the best of our knowledge.