UPGMA and the normalized equidistant minimum evolution problem

Moulton, Vincent, Spillner, Andreas and Wu, Taoyang (2018) UPGMA and the normalized equidistant minimum evolution problem. Theoretical Computer Science, 721. pp. 1-15. ISSN 0304-3975

[img] PDF (upgma_tcs_rev_R2) - Submitted Version
Restricted to Repository staff only until 31 December 2099.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (390kB) | Request a copy
    [img] PDF (Accepted manuscript) - Submitted Version
    Restricted to Repository staff only until 01 February 2020.
    Available under License Creative Commons Attribution Non-commercial No Derivatives.

    Download (433kB) | Request a copy

      Abstract

      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(log2n) of the optimum.

      Item Type: Article
      Uncontrolled Keywords: upgma,minimum evolution,balanced minimum evolution,hierarchical clustering
      Faculty \ School: Faculty of Science > School of Computing Sciences
      Depositing User: Pure Connector
      Date Deposited: 25 Jan 2018 15:30
      Last Modified: 09 Apr 2019 12:59
      URI: https://ueaeprints.uea.ac.uk/id/eprint/66076
      DOI: 10.1016/j.tcs.2018.01.022

      Actions (login required)

      View Item