Tools
Tools
Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435, Spillner, Andreas and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001
(2018)
UPGMA and the normalized equidistant minimum evolution problem.
Theoretical Computer Science, 721.
pp. 1-15.
ISSN 0304-3975
Preview |
PDF (Accepted manuscript)
- Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (443kB) | Preview |
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 |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Depositing User: | Pure Connector |
| Date Deposited: | 25 Jan 2018 15:30 |
| Last Modified: | 14 Jun 2023 13:15 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/66076 |
| DOI: | 10.1016/j.tcs.2018.01.022 |
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |