LOCAL QUARTET SPLITS OF A BINARY-TREE INFER ALL QUARTET SPLITS VIA ONE DYADIC INFERENCE RULE

Citation
Pl. Erdos et al., LOCAL QUARTET SPLITS OF A BINARY-TREE INFER ALL QUARTET SPLITS VIA ONE DYADIC INFERENCE RULE, Computers and artificial intelligence, 16(2), 1997, pp. 217-227
Citations number
10
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
ISSN journal
02320274
Volume
16
Issue
2
Year of publication
1997
Pages
217 - 227
Database
ISI
SICI code
0232-0274(1997)16:2<217:LQSOAB>2.0.ZU;2-X
Abstract
A significant problem in phylogeny is to reconstruct a semilabelled bi nary tree from few valid quartet splits of it. It is well-known that e very semilabelled binary tree is determined by its set of all valid qu artet splits. Here Re strengthen this result by showing that its local (i.e. small diameter) quartet splits infer tv a dyadic inference rule all valid quartet splits. and hence determine the tree. The results o f the paper also present a polynomial time algorithm to recover the tr ee.