Name
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(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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13193-6_13 | SEA |
Keywords | Field | DocType |
fast fpt algorithm,larger tree,maximum acyclic agreement forest,fpt algorithm,rooted maximum agreement forest,protein sequence data,rooted agreement forest,previous method,hybridization number,spr distance,simulated tree,phylogenetic tree,protein sequence | Combinatorics,Phylogenetic tree,Algorithm,Intuition,Mathematics,Speedup,Branching (version control),Search tree | Conference |
ISBN | Citations | PageRank |
3-642-13192-1 | 20 | 1.20 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Whidden | 1 | 89 | 7.99 |
| Robert G. Beiko | 2 | 134 | 10.89 |
| Norbert Zeh | 3 | 55 | 6.97 |