Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space

By Yaniv Loewenstein, Elon Portugaly, Menachem Fromer, Michal Linial. 2008

160 citations recorded by the source corpus.

Motivation: UPGMA (average linking) is probably the most popular algorithm for hierarchical data clustering, especially in computational biology. However, UPGMA requires the entire dissimilarity matrix in memory. Due to this prohibitive requirement, UPGMA is not scalable to very large datasets. Application: We present a novel class of memory-constrained UPGMA (MC-UPGMA) algorithms. Given any practical memory size constraint, this framework guarantees the correct clustering solution without explicitly requiring all dissimilarities in memory. The algorithms are general and are applicable to any dataset. We present a data-dependent characterization of hardness and clustering efficiency. The presented concepts are applicable to any agglomerative clustering formulation. Results: We apply our algorithm to the entire collection of protein sequences, to automatically build a comprehensive evolutionary-driven hierarchy of proteins from sequence alone. The newly created tree captures protein families better than state-of-the-art large-scale methods such as CluSTr, ProtoNet4 or single-linkage clustering. We demonstrate that leveraging the entire mass embodied in all sequence similarities allows to significantly improve on current protein family clusterings which are unable to directly tackle the sheer mass of this data. Furthermore, we argue that non-metric constraints are an inherent complexity of the sequence space and should not be overlooked. The robustness of UPGMA allows significant improvement, especially for multidomain proteins, and for large or divergent families. Availability: A comprehensive tree built from all UniProt sequence similarities, together with navigation and classification tools will be made available as part of the ProtoNet service. A C++ implementation of the algorithm is available on request. Contact: lonshy@cs.huji.ac.il

Subfields: Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

Citations in the corpus

UniRef clusters: a comprehensive and scalable alternative for improving sequence similarity searches (2014, background): “…functional screening of metagenomics data (Foerstner et al., 2008; Wommack et al., 2012), developing large-scale hierarchical clustering algorithms (Loewenstein et al., 2008), studying gene duplication (Rivera et al., 2010) and conducting genomic studies of peptide and oligonucleotide frequencies…”
An integrated metagenomics pipeline for strain profiling reveals novel patterns of bacterial transmission and biogeography (2016, methodology): “To increase clustering performance, we took the average pairwise distances across these 30 gene families and used these newdistances to recluster genomes using MC-UPGMA (Supplemental Table S3).”
A Deep Learning Approach to Antibiotic Discovery. (2020, methodology): “The average linkage uses the algorithm called unweighted pair group method with arithmetic mean (UPGMA), which is the most popular and preferred algorithm for hierarchical data clustering (Jaskowiak et al., 2014; Loewenstein et al., 2008).”
Biogeographic patterns of microbial association networks in paddy soil within Eastern China (2020, methodology): “The nifH sequences were clustered into OTUs with complete linkage clustering (Loewenstein et al., 2008) at the 95% amino acid identity (Penton et al.”
FunGene: the functional gene pipeline and repository (2013, methodology): “FGP uses the mcClust (http://github . com/rdpstaff/Clustering) clustering tool. mcClust is our implementation of a proposed single round memory-constrained clustering algorithm (Loewenstein et al., 2008).”
CAVER 3.0: A Tool for the Analysis of Transport Pathways in Dynamic Protein Structures (2012, methodology): “Average-link hierarchical clustering [50] is used to construct a tree hierarchy of pathway axes based on their pairwise distances.”