Sequence clustering method and device

Abstract

The embodiment of the invention discloses a sequence clustering method. The method comprises the steps that each computing node reads whole sequence data and builds a PBP tree independently; the nearest neighbour (NN) of each sequence is searched for concurrently; all pairs (a, b) meeting NN(a)=b and NN(b)=a are selected; each pair is deleted from the PBP tree and is combined into a new cluster, and all the newly-built clusters are inserted into the PBP tree; the newly-built clusters and all affected NN lists of the clusters are updated concurrently through NN searching until only one cluster is left or cluster distance exceeds a given threshold value. The embodiment of the invention further discloses a sequence clustering device. By the adoption of the sequence clustering method and device, hierarchical clustering of millions of sequences can be processed efficiently and accurately, the clustering result equivalent to standard hierarchical clustering is achieved, and the expansibility is good.

Description

technical field [0001] The invention relates to the field of data mining, in particular to a sequence clustering method and device. Background technique [0002] Genome sequencing is a commonly used tool in biological and biomedical research. In the past few years, the data generation capacity of high-throughput sequencing has improved significantly, and the speed exceeds Moore's Law. The rapid accumulation of genetic information is a valuable resource for biological knowledge mining, and at the same time poses a severe challenge to data analysis, requiring new computing algorithms for efficient data processing. Amplified sequencing, one of the two main genome sequencing methods currently, is a powerful tool for in-depth analysis of phylogenetic and evolutionary details, especially for viruses, microbial groups (including bacteria, fungi, and plankton), etc. A critical step in the analysis of amplified sequencing data is the clustering of sequences into taxonomic or genoty...

AI Technical Summary

Problems solved by technology

However, efficient parallelization of hierarchical clustering is inherently difficult. HPC-Clust[2] and ESPRIT[3] are currently the only two parallel methods for sequence clustering. HPC-Clust adopts profile-based alignment to reduce Computational burden, the clustering quality is poor when dealing with unknown classification, and ESPRIT is accurate but the calculation efficiency is low, it takes almost a week to cluster one million sequences with 200 CPU cores

The shortcomings of the existing technology are: (1) ESPRIT-Tree can efficiently perform hierarchical clustering, but its single-threaded nature limits its performance

(2) Sequence clustering parallel methods HPC-Clust and ESPRIT, HPC-Clust has poor clustering quality when dealing with unknown classifications, while ESPRIT has low computational efficiency

Images