We present new and improved approximation and FPT algorithms for computing rooted and unrooted maximum agreement forests (MAFs) of pairs of phylogenetic trees. Their sizes correspond to the subtree-prune-and-regraft distances and the tree-bisection-and-reconnection distances of the trees, respectively. We also provide the first bounded search tree FPT algorithm for computing rooted maximum acyclic agreement forests (MAAFs) of pairs of phylogenetic trees, whose sizes are the hybridization numbers of these pairs of trees. These distance metrics are essential tools for understanding reticulate evolution.
Two algorithms for computing rooted SPR distances, SPRdist @cite_30 and TreeSAT @cite_28 , express the problem of computing maximum agreement forests as an integer linear program (ILP) and a satisfiability problem (SAT), respectively, and employ efficient ILP and SAT solvers to obtain a solution. SPRdist has been shown to outperform EEEP and Lattrans @cite_30 . Although such algorithms draw on the close scrutiny that has been applied to these problems, experiments show that these algorithms cannot compete with the rooted SPR algorithm presented in this paper @cite_4 .
@cite_30 @cite_28 @cite_4
2145171033 1558959051 1582613544
Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance. Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance. Availability: A software tool, SPRDist, is available for download from the web page: http: www.engr.uconn.edu ywu. Contact: ywu@engr.uconn.edu We develop techniques to calculate important measures in evolutionary biology by encoding to CNF formulas and using powerful SAT solvers. Comparing evolutionary trees is a necessary step in tree reconstruction algorithms, locating recombination and lateral gene transfer, and in analyzing and visualizing sets of trees. We focus on two popular comparison measures for trees: the hybridization number and the rooted subtree-prune-and-regraft (rSPR) distance. Both have recently been shown to be NP-hard, and effcient algorithms are needed to compute and approximate these measures. We encode these as a Boolean formula such that two trees have hybridization number k (or rSPR distance k) if and only if the corresponding formula is satisfiable. We use state-of-the-art SAT solvers to determine if the formula encoding the measure has a satisfying assignment. Our encoding also provides a rich source of real-world SAT instances, and we include a comparison of several recent solvers (minisat, adaptg2wsat, novelty+p, Walksat, March KS and SATzilla). We improve on earlier FPT algorithms for computing a rooted maximum agreement forest (MAF) or a maximum acyclic agreement forest (MAAF) of a pair of phylogenetic trees. Their sizes give the subtree-prune-and-regraft (SPR) distance and the hybridization number of the trees, respectively. We introduce new branching rules that reduce the running time of the algorithms from O(3kn) and O(3kn logn) to O(2.42kn) and O(2.42kn logn), respectively. In practice, the speed up may be much more than predicted by the worst-case analysis. We confirm this intuition experimentally by computing MAFs for simulated trees and trees inferred from protein sequence data. We show that our algorithm is orders of magnitude faster and can handle much larger trees and SPR distances than the best previous methods, treeSAT and sprdist.