| Lower Bounds for Maximum Parsimony with Gene Order Data (2005) | |||||||||||||||||
Abstract | |||||||||||||||||
| Abstract. In this paper, we study lower bound techniques for branchand-bound algorithms for maximum parsimony, with a focus on gene order data. We give a simple O(n 3) 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 programmingbased lower bound of Tang and Moret (Tang and Moret, 2005) can be greatly simplified, allowing us to solve the LP in O ∗ n 3) 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. 1 | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||