UPGMA and the normalized equidistant minimum evolution problem

Preprint English OPEN
Moulton, Vincent ; Spillner, Andreas ; Wu, Taoyang (2017)
  • Subject: Quantitative Biology - Populations and Evolution | Computer Science - Discrete Mathematics | Computer Science - Computational Complexity

UPGMA (Unweighted Pair Group Method with Arithmetic Mean) is a widely used clustering method. Here we show that UPGMA is a greedy heuristic for the normalized equidistant minimum evolution (NEME) problem, that is, finding a rooted tree that minimizes the minimum evolution score relative to the dissimilarity matrix among all rooted trees with the same leaf-set in which all leaves have the same distance to the root. We prove that the NEME problem is NP-hard. In addition, we present some heuristic and approximation algorithms for solving the NEME problem, including a polynomial time algorithm that yields a binary, rooted tree whose NEME score is within O(log^2 n) of the optimum. We expect that these results to eventually provide further insights into the behavior of the UPGMA algorithm.
  • References (26)
    26 references, page 1 of 3

    [1] P. D'haeseleer, How does gene expression clustering work?, Nature biotechnology 23 (12) (2005) 1499-1501.

    [2] R. Sokal, C. Michener, A statistical method for evaluating systematic relationships, University of Kansas Science Bulletin 38 (1958) 1409-1438.

    [4] J. Felsenstein, Inferring phylogenies, Sinauer associates Sunderland, 2004.

    [5] P. Legendre, L. Legendre, Numerical ecology, Vol. 24, Elsevier, 2012.

    [6] W. Li, L. Fu, B. Niu, S. Wu, J. Wooley, Ultrafast clustering algorithms for metagenomic sequence analysis, Briefings in bioinformatics 13 (6) (2012) 656-668.

    [7] C. Romesburg, Cluster analysis for researchers, Lulu. com, 2004.

    [8] R. Davidson, S. Sullivant, Polyhedral combinatorics of UPGMA cones, Advances in Applied Mathematics 50 (2) (2013) 327-338.

    [9] O. Gascuel, M. Steel, Neighbor-Joining revealed, Molecular Biology and Evolution 23 (2006) 1997-2000.

    [10] N. Saitou, M. Nei, The Neighbor-Joining method: a new method for reconstructing phylogenetictrees, Molecular Biology and Evolution 4 (1987) 406-425.

    [11] A. Rzhetsky, M. Nei, Theoretical foundation of the minimum-evolution method of phylogenetic inference, Molecular Biology and Evolution 10 (1993) 1073-1095.

  • Metrics
    No metrics available
Share - Bookmark