Local quartet splits of a binary tree inferall quartet splits via one dyadic inference rule
Péter L. Erdős, Mike Steel, Łászló A. Székely, Tandy J. Warnow · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 1996
A significant problem in phylogeny is to reconstruct a semilabelled binary tree from few valid quartet splits of it. It is well-known that every semilabelled binary tree is determined by its set of all valid quartet splits. Here we strengthen this result by showing that its local (i.e. small diameter) quartet splits infer by a dyadic inference rule all valid quartet splits, and hence determine the tree. The results of the paper also present a polynomial time algorithm to recover the tree. Keywords.semilabelled binary trees, subtrees, phylogeny, quartets. 1 Acknowledgment. This research started when the authors enjoyed the hospitality of DIMACS during the Special Year for Mathematical Support to Molecular Biology. The second author gratefully acknowledges the New Zealand Ministry of Research, Science and Technology (MORST) for support to visit Budapest under ISAC Programme grant 94/22. Research of the first and third authors was supported in part by the Hungarian National Science Fund...