×

zbMATH — the first resource for mathematics

Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm. (English) Zbl 07304646
Summary: Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics.
MSC:
68 Computer science
Software:
SPRSupertrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, B. L.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5, 1-15 (2001) · Zbl 0978.05023
[2] Alon, N.; Chor, B.; Pardi, F.; Rapoport, A., Approximate maximum parsimony and ancestral maximum likelihood, IEEE/ACM Trans. Comput. Biol. Bioinform., 7, 1, 183-187 (January 2010)
[3] Anonymous, answer, How many vertices of degree 3 or more can a tree have at most?, (version: 2013-05-12)
[4] Atkins, R.; McDiarmid, C., Extremal distances for subtree transfer operations in binary trees, Ann. Comb., 23, 1, 1-26 (2019) · Zbl 1414.05074
[5] Baste, J.; Paul, C.; Sau, I.; Scornavacca, C., Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees, Bull. Math. Biol., 79, 4, 920-938 (2017) · Zbl 1372.92069
[6] Bodlaender, H. L., A tourist guide through treewidth, Acta Cybern., 11, 1-2, 1 (1994) · Zbl 0804.68101
[7] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[8] Boes, O.; Fischer, M.; Kelk, S., A linear bound on the number of states in optimal convex characters for maximum parsimony distance, IEEE/ACM Trans. Comput. Biol. Bioinform., 14, 2, 472-477 (2016)
[9] Bonet, M. L.; John, K. St, On the complexity of uSPR distance, IEEE/ACM Trans. Comput. Biol. Bioinform., 7, 3, 572-576 (2010)
[10] Bordewich, M.; Scornavacca, C.; Tokac, N.; Weller, M., On the fixed parameter tractability of agreement-based phylogenetic distances, J. Math. Biol., 74, 1-2, 239-257 (2017) · Zbl 1354.05129
[11] Bryant, D.; Lagergren, J., Compatibility of unrooted phylogenetic trees is FPT, Theor. Comput. Sci., 351, 3, 296-302 (2006) · Zbl 1086.68097
[12] Bulteau, L.; Weller, M., Parameterized algorithms in bioinformatics: an overview, Algorithms, 12, 12, 256 (2019)
[13] Chen, J.; Fan, J-H.; Sze, S-H., Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees, Theor. Comput. Sci., 562, 496-512 (2015) · Zbl 1303.68154
[14] Chen, J.; Shi, F.; Wang, J., Approximating maximum agreement forest on multiple binary trees, Algorithmica, 76, 4, 867-889 (2016) · Zbl 1352.68288
[15] Cygan, M.; Fomin, F.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer Publishing Company, Incorporated · Zbl 1334.90001
[16] Downey, R.; Fellows, M., Fundamentals of Parameterized Complexity, vol. 4 (2013), Springer · Zbl 1358.68006
[17] Felsenstein, J., Inferring Phylogenies (2004), Sinauer Associates, Incorporated
[18] Fischer, M.; Kelk, S., On the maximum parsimony distance between phylogenetic trees, Ann. Comb., 20, 1, 87-113 (2016) · Zbl 1332.05043
[19] Fitch, W., Toward defining the course of evolution: minimum change for a specific tree topology, Syst. Biol., 20, 4, 406-416 (1971)
[20] Huson, D.; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications (2011), Cambridge University Press
[21] Janssen, R.; Jones, M.; Kelk, S.; Stamoulis, G.; Wu, T., Treewidth of display graphs: bounds, brambles and applications, J. Graph Algorithms Appl., 23, 4 (2019) · Zbl 1419.05187
[22] Kelk, S.; Fischer, M., On the complexity of computing MP distance between binary phylogenetic trees, Ann. Comb., 21, 573-604 (2017) · Zbl 1380.05069
[23] Kelk, S.; Fischer, M.; Moulton, V.; Wu, T., Reduction rules for the maximum parsimony distance on phylogenetic trees, Theor. Comput. Sci., 646, 1-15 (2016) · Zbl 1348.68068
[24] Kelk, S.; Linz, S., A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees, SIAM J. Discrete Math., 33, 3, 1556-1574 (2019) · Zbl 1430.68130
[25] Kelk, S.; Linz, S., New reduction rules for the tree bisection and reconnection distance, Ann. Comb., 24, 475-502 (2020) · Zbl 1451.05042
[26] Kelk, S.; Stamoulis, G., A note on convex characters, Fibonacci numbers and exponential-time algorithms, Adv. Appl. Math., 84, 34-46 (2017) · Zbl 1431.05084
[27] Kelk, S.; Stamoulis, G.; Wu, T., Treewidth distance on phylogenetic trees, Theor. Comput. Sci., 731, 99-117 (2018) · Zbl 1395.05171
[28] Kelk, S.; van Iersel, L. J.J.; Scornavacca, C.; Weller, M., Phylogenetic incongruence through the lens of monadic second order logic, J. Graph Algorithms Appl., 20, 2, 189-215 (2016) · Zbl 1331.05210
[29] Liers, F.; Martin, A.; Pape, S., Binary Steiner trees: structural results and an exact solution approach, Discrete Optim., 21, 85-117 (2016) · Zbl 1387.90141
[30] Moran, S.; Snir, S., Convex recolorings of strings and trees: definitions, hardness results and algorithms, J. Comput. Syst. Sci., 74, 5, 850-869 (2008) · Zbl 1160.68025
[31] Moulton, V.; Wu, T., A parsimony-based metric for phylogenetic trees, Adv. Appl. Math., 66, 22-45 (2015) · Zbl 1315.05034
[32] Nakhleh, L., Computational approaches to species phylogeny inference and gene tree reconciliation, Trends Ecol. Evol., 28, 12, 719-728 (2013)
[33] Robinson, D.; Foulds, L., Comparison of phylogenetic trees, Math. Biosci., 53, 1-2, 131-147 (1981) · Zbl 0451.92006
[34] Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press · Zbl 1043.92026
[35] Shi, F.; Chen, J.; Feng, Q.; Wang, J., A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees, J. Comput. Syst. Sci., 97, 28-44 (2018) · Zbl 1400.92379
[36] John, K. St, The shape of phylogenetic treespace, Syst. Biol., 66, 1, e83-e94 (2017)
[37] Steel, M., Phylogeny: Discrete and Random Processes in Evolution (2016), SIAM · Zbl 1361.92001
[38] van Iersel, L.; Jones, M.; Kelk, S., A third strike against perfect phylogeny, Syst. Biol., 68, 5, 814-827 (2019)
[39] van Iersel, L.; Kelk, S.; Lekic, N.; Whidden, C.; Zeh, N., Hybridization number on three rooted binary trees is EPT, SIAM J. Discrete Math., 30, 3, 1607-1631 (2016) · Zbl 1345.92101
[40] Warnow, T., Computational Phylogenetics: An Introduction to Designing Methods for Phylogeny Estimation (2017), Cambridge University Press · Zbl 1377.92001
[41] Whidden, C.; Beiko, R. G.; Zeh, N., Fixed-parameter algorithms for maximum agreement forests, SIAM J. Comput., 42, 4, 1431-1466 (2013) · Zbl 1311.68079
[42] Whidden, C.; Zeh, N.; Beiko, R. G., Supertrees based on the subtree prune-and-regraft distance, Syst. Biol., 63, 4, 566-581 (2014)
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.