2006/06/11 by Rudi Cilibrasi, Cilibrasi, Rudi, Paul Vitányi +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Computer Vision and Pattern Recognition (cs.CV) #Data Analysis #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #G.1.6 #Quantitative Methods (q-bio.QM) #Statistics Theory (math.ST) #Statistics and Probability (physics.data-an) #cs.CV #cs.DM #cs.DS #math.ST #physics.data-an #q-bio.QM #stat.TH
paper · pdf · doi:10.48550/arxiv.cs/0606048
22 pages, 14 figures
arxiv created 2006/06/11 · openalex publication_date 2006/06/11 · arxiv updated 2011/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.