Local Quartet Splits of a Binary Tree Infer All Quartet Splits Via One Dyadic Inference Rule
P. L. Erdös ; M. A. Steel ; L. A. Székely ; T. J. Warnow
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  
@article{cai669,
     author = {P. L. Erd\"os and M. A. Steel and L. A. Sz\'ekely and T. J. Warnow},
     title = {Local Quartet Splits of a Binary Tree Infer All Quartet Splits Via One Dyadic Inference Rule},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai669}
}

P. L. Erdös; M. A. Steel; L. A. Székely; T. J. Warnow. Local Quartet Splits of a Binary Tree Infer All Quartet Splits Via One Dyadic Inference Rule. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai669/