Parallel and Scalable Precise Clustering

Details

Serval ID
serval:BIB_D9BAD3B1327F
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
Parallel and Scalable Precise Clustering
Title of the conference
Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques
Author(s)
Byma Stuart, Dhasade Akash, Altenhoff Adrian, Dessimoz Christophe, Larus James R.
Publisher
ACM
ISBN
9781450380751
Publication state
Published
Issued date
30/09/2020
Language
english
Abstract
This paper describes a new technique for parallelizing protein clustering, an important bioinformatics computation for the analysis of protein sequences. Protein clustering identifies groups of proteins that are similar because they share long sequences of similar amino acids. Given a collection of protein sequences, clustering can significantly reduce the computational effort required to identify all similar sequences by avoiding many negative comparisons. The challenge, however, is to build a clustering that misses as few similar sequences (or elements, more generally) as possible.
In this paper, we introduce precise clustering, a property that requires each pair of similar elements to appear together in at least one cluster. We show that transitivity in the data can be leveraged to merge clusters while maintaining a precise clustering, providing a basis for independently forming clusters. This allows us reformulate clustering as a bottom-up merge of independent clusters in a new algorithm called ClusterMerge. ClusterMerge exposes parallelism, enabling fast and scalable implementations.
We apply ClusterMerge to find similar amino acid sequences in a collection of proteins. ClusterMerge identifies 99.8% of similar pairs found by a full O(n2) comparison, with only half as many comparisons. More importantly, ClusterMerge is highly amenable to parallel and distributed computation. Our implementation achieves a speedup of 604 times on 768 cores (1400 times faster than a comparable single-threaded clustering implementation), a strong scaling efficiency of 90%, and a weak scaling efficiency of nearly 100%.
Open Access
Yes
Create date
23/01/2020 15:29
Last modification date
22/01/2021 6:24
Usage data