A New Quartet Tree Heuristic for Hierarchical Clustering
<|reference_start|>A New Quartet Tree Heuristic for Hierarchical Clustering: We consider the problem of constructing an an optimal-weight tree from the 3*(n choose 4) weighted quartet topologies on n objects, where optimality means that the summed weight of the embedded quartet topologiesis optimal (so it can be the case that the optimal tree embeds all quartets as non-optimal topologies). We present a heuristic for reconstructing the optimal-weight tree, and a canonical manner to derive the quartet-topology weights from a given distance matrix. The method repeatedly transforms a bifurcating tree, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. This contrasts to other heuristic search methods from biological phylogeny, like DNAML or quartet puzzling, which, repeatedly, incrementally construct a solution from a random order of objects, and subsequently add agreement values.<|reference_end|>
@article{cilibrasi2006a,
    title={A New Quartet Tree Heuristic for Hierarchical Clustering},
    author={Rudi Cilibrasi and Paul M.B. Vitanyi},
    journal={arXiv preprint arXiv:cs/0606048},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606048},
    primaryClass={cs.DS cs.CV cs.DM math.ST physics.data-an q-bio.QM stat.TH}
}