Optimal algorithms for local vertex quartet cleaning.
BACKGROUND
Reconstructing evolutionary trees is an important problem in biology. A response to the computational intractability of most of the traditional criteria for inferring evolutionary trees has been a focus on new criteria, particularly quartet-based methods that seek to merge trees derived on subsets of four species from a given species-set into a tree for that entire set. Unfortunately, most of these methods are very sensitive to errors in the reconstruction of the trees for individual quartets of species. A recently developed technique called quartet cleaning can alleviate this difficulty in certain cases by using redundant information in the complete set of quartet topologies for a given species-set to correct such errors.


RESULTS
In this paper, we describe two new local vertex quartet cleaning algorithms which have optimal time complexity and error-correction bound, respectively. These are the first known local vertex quartet cleaning algorithms that are optimal with respect to either of these attributes.
Della Vedova
Gianluca
G
Dipartimento di Statistica, Universitá degli Studi di Milano-Bicocca, via Bicocca degli Arcimboldi 8, 20126 Milano, Italy. gianluca.dellavedova@unimib.it
Wareham
H Todd
HT
D000465:Algorithms; D019143:Evolution, Molecular; D014644:Genetic Variation; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny; D011786:Quality Control; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D013045:Species Specificity