New reduction rules for the tree bisection and reconnection distance.

*(English)*Zbl 1451.05042Summary: Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most \(15k-9\) taxa where \(k\) is the TBR (tree bisection and reconnection) distance between the two trees, and that this bound is tight. Here, we propose five new reduction rules and show that these further reduce the bound to \(11k-9\). The new rules combine the “unrooted generator” approach introduced in S. Kelk and S. Linz [SIAM J. Discrete Math. 33, No. 3, 1556–1574 (2019; Zbl 1430.68130)] with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules.

##### MSC:

05C05 | Trees |

##### Keywords:

fixed-parameter tractability; tree bisection; tree reconnection; generator; kernelization; agreement forest; phylogenetic network; phylogenetic tree; hybridization number
PDF
BibTeX
XML
Cite

\textit{S. Kelk} and \textit{S. Linz}, Ann. Comb. 24, No. 3, 475--502 (2020; Zbl 1451.05042)

Full Text:
DOI

##### References:

[1] | B. Allen and M. Steel. Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics, 5:1-15, 2001. · Zbl 0978.05023 |

[2] | R. Atkins and C. McDiarmid. Extremal distances for subtree transfer operations in binary trees. Annals of Combinatorics, 23(1):1-26, 2019. · Zbl 1414.05074 |

[3] | M. Baroni, C. Semple, and M. Steel. Hybrids in real time. Systematic Biology, 55(1):46-56, 2006. |

[4] | M. Bordewich, C. Scornavacca, N. Tokac, and M. Weller. On the fixed parameter tractability of agreement-based phylogenetic distances. Journal of Mathematical Biology, 74(1-2):239-257, 2017. · Zbl 1354.05129 |

[5] | J. Chen, J-H. Fan, and S-H. Sze. Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. Theoretical Computer Science, 562:496-512, 2015. · Zbl 1303.68154 |

[6] | M. Cygan, F. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms, volume 3. Springer, 2015. |

[7] | J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Incorporated, 2004. |

[8] | M. Fischer and S. Kelk. On the Maximum Parsimony distance between phylogenetic trees. Annals of Combinatorics, 20(1):87-113, 2016. · Zbl 1332.05043 |

[9] | F. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. · Zbl 1426.68003 |

[10] | J. Hein, T. Jiang, L. Wang, and K. Zhang. On the complexity of comparing evolutionary trees. Discrete Applied Mathematics, 71(1-3):153-169, 1996. · Zbl 0876.92020 |

[11] | D. Huson, R. Rupp, and C. Scornavacca. Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, 2011. |

[12] | Steven Kelk and Simone Linz. A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees. SIAM Journal on Discrete Mathematics, 33(3):1556-1574, 2019. · Zbl 1430.68130 |

[13] | C. Semple and M. Steel. Phylogenetics. Oxford University Press, 2003. |

[14] | F. Shi, J. Chen, Q. Feng, and J. Wang. A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees. Journal of Computer and System Sciences, 97:28-44, 2018. · Zbl 1400.92379 |

[15] | 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(11):2993-3022, 2018. · Zbl 1410.68178 |

[16] | C. Whidden, R. G. Beiko, and N. Zeh. Fixed-parameter algorithms for maximum agreement forests. SIAM Journal on Computing, 42(4):1431-1466, 2013. · Zbl 1311.68079 |

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.