Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments

Authors: 

Chris Whidden
Robert G. Beiko
Norbert Zeh

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2

Abstract: 

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(3^k n) and O(3^k nlogn) to O(2.42^k n) and O(2.42^k nlogn), respectively. In practice, the speed up of the algorithms 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 MAF algorithm is orders of magnitude faster than the best previous methods and can handle much larger trees and SPR distances.

Tech Report Number: 
CS-2010-03
Report Date: 
March 12, 2010
AttachmentSize
PDF icon CS-2010-03.pdf246.25 KB