×

zbMATH — the first resource for mathematics

On the fixed parameter tractability of agreement-based phylogenetic distances. (English) Zbl 1354.05129
Summary: Three important and related measures for summarizing the dissimilarity in phylogenetic trees are the minimum number of hybridization events required to fit two phylogenetic trees onto a single phylogenetic network (the hybridization number), the (rooted) subtree prune and regraft distance (the rSPR distance) and the tree bisection and reconnection distance (the TBR distance) between two phylogenetic trees. The respective problems of computing these measures are known to be NP-hard, but also fixed-parameter tractable in their respective natural parameters. This means that, while they are hard to compute in general, for cases in which a parameter (here the hybridization number and rSPR/TBR distance, respectively) is small, the problem can be solved efficiently even for large input trees. Here, we present new analyses showing that the use of the “cluster reduction” rule – already defined for the hybridization number and the rSPR distance and introduced here for the TBR distance – can transform any \(O(f(p) \cdot n)\)-time algorithm for any of these problems into an \(O(f(k) \cdot n)\)-time one, where \(n\) is the number of leaves of the phylogenetic trees, \(p\) is the natural parameter and \(k\) is a much stronger (that is, smaller) parameter: the minimum level of a phylogenetic network displaying both trees.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92-08 Computational methods for problems pertaining to biology
05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, BL; Steel, M, Subtree transfer operations and their induced metrics on evolutionary trees, Ann Combinat, 5, 1-15, (2001) · Zbl 0978.05023
[2] Baroni, M; Grünewald, S; Moulton, V; Semple, C, Bounding the number of hybridisation events for a consistent evolutionary history, J Math Biol, 51, 171-182, (2005) · Zbl 1068.92034
[3] Baroni, M; Semple, C; Steel, M, Hybrids in real time, Syst Biol, 55, 46-56, (2006)
[4] Bordewich, M; Semple, C, On the computational complexity of the rooted subtree prune and regraft distance, Ann Combinat, 8, 409-423, (2005) · Zbl 1059.05035
[5] Bordewich, M; Semple, C, Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable, IEEE/ACM Trans Comput Biol Bioinf (TCBB), 4, 458-466, (2007)
[6] Bordewich M, Semple C (2007b) Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl Math 155(8):914-928 · Zbl 1111.92041
[7] Bordewich, M; Linz, S; John, KS; Semple, C, A reduction algorithm for computing the hybridization number of two trees, Evol Bioinf Online, 3, 86, (2007)
[8] Chen J, Fan JH, Sze SH (2013) Parameterized and approximation algorithms for the MAF problem in multifurcating trees. In: Graph-theoretic concepts in computer science. Springer, Berlin, pp 152-164 · Zbl 1400.05236
[9] Chen, ZZ; Fan, Y; Wang, L, Faster exact computation of rspr distance, J Combin Optim, 29, 605-635, (2013) · Zbl 1322.90103
[10] Hallett MT, Lagergren J (2001) Efficient algorithms for lateral gene transfer problems. In: Proceedings of the fifth annual international conference on computational biology. ACM, New York, pp 149-156 · Zbl 1322.90103
[11] Harel, D; Tarjan, RE, Fast algorithms for finding nearest common ancestors, Siam J Comput, 13, 338-355, (1984) · Zbl 0535.68022
[12] Hein, J; Jiang, T; Wang, L; Zhang, K, On the complexity of comparing evolutionary trees, Discrete Appl Math, 71, 153-169, (1996) · Zbl 0876.92020
[13] van Iersel L, Kelk S, Stougie L, Boes O (2016) On unrooted and root-uncertain variants of several well-known phylogenetic network problems (In preparation) · Zbl 1410.68178
[14] Jansson, J; Sung, WK, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Theoret Comput Sci, 363, 60-68, (2006) · Zbl 1110.68032
[15] Kelk, S; Scornavacca, C; Iersel, L, On the elusiveness of clusters, IEEE/ACM Trans Comput Biol Bioinf (TCBB), 9, 517-534, (2012)
[16] Linz, S; Semple, C, A cluster reduction for computing the subtree distance between phylogenies, Ann Combinat, 15, 465-484, (2011) · Zbl 1234.05057
[17] Maddison, WP, Gene trees in species trees, Syst Biol, 46, 523-536, (1997)
[18] Nakhleh L, Warnow T, Linder CR (2004) Reconstructing reticulate evolution in species: theory and practice. In: Proceedings of the eighth annual international conference on research in computational molecular biology. ACM, New York, pp 337-346 · Zbl 1068.92034
[19] Semple C, Steel MA (2003) Phylogenetics, vol 24. Oxford University Press, Oxford · Zbl 1043.92026
[20] Iersel, L; Kelk, S, When two trees go to war, J Theoret Biol, 269, 245-255, (2011) · Zbl 1307.92304
[21] Iersel, L; Kelk, S; Mnich, M, Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks, J Bioinf Comput Biol, 7, 597-623, (2009)
[22] Whidden, C; Beiko, RG; Zeh, N, Fixed-parameter algorithms for maximum agreement forests, SIAM J Comput, 42, 1431-1466, (2013) · Zbl 1311.68079
[23] Whidden C, Beiko R, Zeh N (2016) Computing the SPR distance of binary rooted trees in \(O(2^k n)\) time (In preparation) · Zbl 1333.68297
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.