We present a new quartet tree heuristic for hierarchical clustering from weighted quartet topologies, and a standard manner to derive those from a given distance matrix. We do not assume that there is a true ternary tree that generated the quartet topologies or distances which we wish to recover as closely as possible. Our aim is to just model the input data as faithfully as possible by the quartet tree. Our method is capable of handling up to 60–80 objects in a matter of hours, while no existing quartet heuristic can directly compute a quartet tree of more than about 20–30 objects without running for years. The method is implemented and available as public software.

, ,
Dagstuhl Seminar Proceedings
Theory of Evolutionary Algorithms
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Cilibrasi, R.L, & Vitányi, P.M.B. (2006). A new quartet tree heuristic for hierarchical clustering. In Dagstuhl Seminar Proceedings. doi:10.4230/DagSemProc.06061.4