×

zbMATH — the first resource for mathematics

A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees. (English) Zbl 1430.68130

MSC:
68Q27 Parameterized complexity, tractability and kernelization
05C05 Trees
68W40 Analysis of algorithms
92D15 Problems related to evolution
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] B. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5 (2001), pp. 1–15. · Zbl 0978.05023
[2] M. Baroni, C. Semple, and M. Steel, Hybrids in real time, Syst. Biol., 55 (2006), pp. 46–56.
[3] H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Kernelization lower bounds by cross-composition, SIAM J. Discrete Math., 28 (2014), pp. 277–305.
[4] M. Bonet and K. S. John, On the complexity of uSPR distance, IEEE/ACM Trans. Comput. Biol. Bioinform., 7 (2010), pp. 572–576.
[5] M. Bordewich, C. Scornavacca, N. Tokac, and M. Weller, On the fixed parameter tractability of agreement-based phylogenetic distances, J. Math. Biol., 74 (2017), pp. 239–257. · Zbl 1354.05129
[6] M. Bordewich and C. Semple, On the computational complexity of the rooted subtree prune and regraft distance, Ann. Comb., 8 (2005), pp. 409–423. · Zbl 1059.05035
[7] M. Bordewich and C. Semple, Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable, IEEE/ACM Trans. Comput. Biol. Bioinform., 4 (2007), pp. 458–466.
[8] M. Bordewich and C. Semple, Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Appl. Math., 155 (2007), pp. 914–928. · Zbl 1111.92041
[9] J. Chen, J.-H. Fan, and S.-H. Sze, Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees, Theoret. Comput. Sci., 562 (2015), pp. 496–512. · Zbl 1303.68154
[10] M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, 1st ed., Springer, Cham, Switzerland, 2015.
[11] J. Felsenstein, Inferring Phylogenies, Sinauer Associates, Sunderland, MA, 2004.
[12] M. Fischer and S. Kelk, On the maximum parsimony distance between phylogenetic trees, Ann. Comb., 20 (2016), pp. 87–113. · Zbl 1332.05043
[13] W. M. Fitch, Toward defining the course of evolution: Minimum change for a specific tree topology, Syst. Biol., 20 (1971), pp. 406–416.
[14] P. Gambette, V. Berry, and C. Paul, Quartets and unrooted phylogenetic networks, J. Bioinf. Comput. Biol., 10 (2012), 1250004.
[15] J. Hein, T. Jiang, L. Wang, and K. Zhang, On the complexity of comparing evolutionary trees, Discrete Appl. Math., 71 (1996), pp. 153–169. · Zbl 0876.92020
[16] D. Huson, R. Rupp, and C. Scornavacca, Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, Cambridge, 2011.
[17] K. S. John, The shape of phylogenetic treespace, Syst. Biol., 66 (2017), e83–e94.
[18] S. Kelk, M. Fischer, V. Moulton, and T. Wu, Reduction rules for the maximum parsimony distance on phylogenetic trees, Theoret. Comput. Sci., 646 (2016), pp. 1–15. · Zbl 1348.68068
[19] S. Kelk and C. Scornavacca, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Algorithmica, 68 (2014), pp. 886–915. · Zbl 1350.92036
[20] S. Kelk and G. Stamoulis, A note on convex characters, Fibonacci numbers and exponential-time algorithms, Adv. Appl. Math., 84 (2017), pp. 34–46. · Zbl 1431.05084
[21] S. Kelk, L. van Iersel, N. Lekić, S. Linz, C. Scornavacca, and L. Stougie, Cycle killer... Qu’est-ce que c’est? On the comparative approximability of hybridization number and directed feedback vertex set, SIAM J. Discrete Math., 26 (2012), pp. 1635–1656. · Zbl 1263.68174
[22] D. Money and S. Whelan, Characterizing the phylogenetic tree-search problem, Syst. Biol., 61 (2012), pp. 228–239.
[23] V. Moulton and T. Wu, A parsimony-based metric for phylogenetic trees, Adv. Appl. Math., 66 (2015), pp. 22–45. · Zbl 1315.05034
[24] F. Shi, J. Chen, Q. Feng, and J. Wang, A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees, J. Comput. System Sci., 97 (2018), pp. 28–44. · Zbl 1400.92379
[25] M. Steel, Phylogeny: Discrete and Random Processes in Evolution, CBMS-NSF Regional Conf. Ser. in Appl. Math. 89, SIAM, Philadelphia, 2016.
[26] L. van Iersel, J. Keijsper, S. Kelk, L. Stougie, F. Hagen, and T. Boekhout, Constructing level-2 phylogenetic networks from triplets, IEEE/ACM Trans. Comput. Biol. Bioinform., 6 (2009), pp. 667–681.
[27] L. van Iersel, S. Kelk, N. Lekić, C. Whidden, and N. Zeh, Hybridization number on three rooted binary trees is EPT, SIAM J. Discrete Math., 30 (2016), pp. 1607–1631. · Zbl 1345.92101
[28] L. van Iersel, S. Kelk, and C. Scornavacca, Kernelizations for the hybridization number problem on multiple nonbinary trees, J. Comput. System Sci., 82 (2016), pp. 1075–1089. · Zbl 1342.68170
[29] L. van Iersel, S. Kelk, G. Stamoulis, L. Stougie, and O. Boes, On unrooted and root-uncertain variants of several well-known phylogenetic network problems, Algorithmica, 80 (2018), pp. 2993–3022. · Zbl 1410.68178
[30] L. van Iersel and S. Linz, A quadratic kernel for computing the hybridization number of multiple trees, Inform. Process. Lett., 113 (2013), pp. 318–323. · Zbl 1287.68060
[31] C. Whidden, R. G. Beiko, and N. Zeh, Fixed-parameter algorithms for maximum agreement forests, SIAM J. Comput., 42 (2013), pp. 1431–1466. · Zbl 1311.68079
[32] C. Whidden and F. Matsen, Calculating the unrooted subtree prune-and-regraft distance, IEEE/ACM Trans. Comput. Biol. Bioinform., 16 (2019), pp. 898–911.
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.