Numerical taxonomy on data: Experimental results

Jaime Cohen, Martin Farach

    Research output: Contribution to journalArticlepeer-review


    We consider the problem of fitting an n x n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was presented (Agarwala et al., 1996) which achieves a factor of 3 approximation to the L∞ best fitting tree. We call this method the Single Pivot (SP) heuristic. Within the biology community, the so-called Neighbor-Joining (NJ) heuristic (Saitou and Nei, 1987) has wide acceptance. In this paper, we introduced a new Double Pivot (DP) heuristic, which is an extension of the SP heuristic, and show that DP outperforms NJ on biological and random data.

    Original languageEnglish (US)
    Pages (from-to)547-558
    Number of pages12
    JournalJournal of Computational Biology
    Issue number4
    StatePublished - 1997


    • Clustering analysis
    • Numerical taxonomy
    • Phylogenetic trees

    ASJC Scopus subject areas

    • Modeling and Simulation
    • Molecular Biology
    • Genetics
    • Computational Mathematics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Numerical taxonomy on data: Experimental results'. Together they form a unique fingerprint.

    Cite this