2019/08/28 by Stuart Byma, Byma, Stuart, Akash Dhasade +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Artificial intelligence #Bioinformatics and Genomic Networks #Cluster (spacecraft) #Cluster analysis #Computation #Computer science #Data mining #Database #Distributed #FOS: Computer and information sciences #Gene expression and cancer classification #Machine Learning in Bioinformatics #Mathematics #Parallel #Parallel computing #Scalability #Scaling #Set (abstract data type) #Speedup #Theoretical computer science #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1908.10574
11 pages, 11 figures. Submitted for publication
arxiv created 2019/08/28 · openalex publication_date 2019/08/28 · arxiv updated 2019/08/29 · openalex created_date 2022/07/28 · openalex updated_date 2026/08/06
This paper presents a new, parallel implementation of clustering and\ndemonstrates its utility in greatly speeding up the process of identifying\nhomologous proteins. Clustering is a technique to reduce the number of\ncomparison needed to find similar pairs in a set of n elements such as\nprotein sequences. Precise clustering ensures that each pair of similar\nelements appears together in at least one cluster, so that similarities can be\nidentified by all-to-all comparison in each cluster rather than on the full\nset. This paper introduces ClusterMerge, a new algorithm for precise clustering\nthat uses transitive relationships among the elements to enable parallel and\nscalable implementations of this approach. We apply ClusterMerge to the\nimportant problem of finding similar amino acid sequences in a collection of\nproteins. ClusterMerge identifies 99.8% of similar pairs found by a full\nO(n2) comparison, with only half as many operations. More importantly,\nClusterMerge is highly amenable to parallel and distributed computation. Our\nimplementation achieves a speedup of 604\× on 768 cores (1400\×\nfaster than a comparable single-threaded clustering implementation), a strong\nscaling efficiency of 90%, and a weak scaling efficiency of nearly 100%.\n