Optimal implementations of UPGMA and other common clustering algorithms
Information Processing LettersPublished 5 July 2007
Ilan Gronau, Shlomo Moran
Citations185
SJR quartileQ3
SJR score0.41
SNIP0.73
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work surveys optimal O(n2)-time implementations of such algorithms which use a 'locally closest' joining scheme, and specifies conditions under which this relaxed joining scheme is equivalent to the original one (i.e. 'globally closest').
Abstract
In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n2)-time implementations of such algorithms which use a 'locally closest' joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. 'globally closest').
Keywords
Computer Science
Molecular Biology and EvolutionThe neighbor-joining method: a new method for reconstructing phylogenetic trees.
60,481 Citations1987Naruya Saitou, M Nei
The neighbor-joining method and Sattath and Tversky's method are shown to be generally better than the other methods for reconstructing phylogenetic trees from evolutionary distance data.
Nucleic Acids ResearchMUSCLE: multiple sequence alignment with high accuracy and high throughput
46,530 Citations2004R. C. Edgar
MUSCLE is a new computer program for creating multiple alignments of protein sequences that includes fast distance estimation using kmer counting, progressive alignment using a new profile function the authors call the log-expectation score, and refinement using tree-dependent restricted partitioning.
The Computer JournalSLINK: An optimally efficient algorithm for the single-link cluster method
1,169 Citations1973Robin Sibson
Sibson gives an O(n 2) algorithm for single-linkage clustering, and proves that this algorithm achieves the theoretically optimal lower time bound for obtaining a single- linkage dendrogram.
Journal of ClassificationEfficient algorithms for agglomerative hierarchical clustering methods
970 Citations1984W. H. Day, Herbert Edelsbrunner
A centroid SAHN clustering algorithm that requires 0(n2) time, in the worst case, for fixedk and for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics is described.
Parallel ComputingParallel algorithms for hierarchical clustering
405 Citations1995Clark F. Olson
This paper discusses parallel algorithms to perform hierarchical clustering using various distance metrics, and a general algorithm is given that can be used to perform clustering with the complete link and average link metrics on a butterfly.
Massive computingHandbook of Massive Data Sets
290 Citations2002James Abello, Pãnos M. Pardalos +1 more
This chapter discusses the development of data management techniques for string processing and data compression on the basis of external memory Algorithms and data Structures.
ACM Journal of Experimental AlgorithmicsFast hierarchical clustering and other applications of dynamic closest pairs
77 Citations2000David Eppstein
These data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects, are developed and applied to hierarchical clustering, greedy matching, and TSP heuristics.
Parallel ComputingA novel parallelization approach for hierarchical clustering
43 Citations2005Zhihua Du, F. Lin
Lecture notes in computer scienceHeterogeneous Data Integration with the Consensus Clustering Formalism
42 Citations2004Vladimir Filkov, Steven Skiena
A refinement to the consensus algorithm for integrating large numbers of microarray data sets based on consensus clustering is proposed by clustering of the source-specific clusterings as a step before finding the consensus between them, thereby improving the original results and increasing their biological relevance.
Massive computingClustering in Massive Data Sets
39 Citations2002Fionn Murtagh
The visualization of data leads to the consideration of data arrays as images, and theoretical results developed as far back as the 1960s still very often remain topical.
Computational Statistics & Data AnalysisWebmining: learning from the world wide web
38 Citations2002Jan Larsen, Lars Kai Hansen +3 more
The use of unsupervised and supervised learning methods for user behavior modeling and content-based segmentation and classification of web pages are discussed.
Information Processing LettersThe complexity of ultrametric partitions on graphs
27 Citations1988Mirko Křivánek
A polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed and the computational complexity of the approximation of w by means of an ultrametric u is investigated and systematized.
Lecture notes in computer scienceCluster Aggregate Inequality and Multi-level Hierarchical Clustering
24 Citations2005Chris Ding, Xiaofeng He
It is shown that in hierarchical clustering, many linkage functions satisfy a cluster aggregate inequality, which allows an exact O(N2) multi-level (using mutual nearest neighbor) implementation of the standard O( N3) agglomerative hierarchical clusters algorithm.
Journal of Computational BiologyNeighbor Joining Algorithms for Inferring Phylogenies via LCA Distances
18 Citations2007Ilan Gronau, Shlomo Moran
Algorithms based on a characterization of edge-weighted trees by distances to LCAs (Least Common Ancestors) are shown to reconstruct a refinement of the Buneman tree, which implies optimal robustness to noise under criteria defined by Atteson.
Accelerating phylogenetics computing on the desktop: experiments with executing UPGMA in programmable logic
15 Citations2005J.P. Davis, S. Akella +1 more
It is discussed how custom computing techniques can be used to not only accelerate phylogenetics algorithm performance on the desktop, but also on larger, high-performance computing engines, thus enabling the high-speed processing of data sets involving thousands of taxa.