96-43: Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule

DIMACS TR: 96-43

Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule

Authors: Peter L. Erdos, Michael A. Steel, Laszlo A. Szekely, Tandy J. Warnow

ABSTRACT
A significant problem in phylogeny is to reconstruct a \slb\ tree from few valid quartet splits of it. It is well-known that every \slb\ 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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-43.ps.gz

DIMACS Home Page