Accurately clustering biological sequences in linear time by relatedness sorting

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Clustering biological sequences is crucial due to exponential data growth.
• Existing super-linear clustering methods are computationally expensive for large datasets.
• Current linear-time algorithms sacrifice accuracy for speed.

Purpose of the Study:

• Develop a linear-time sequence clustering algorithm with high accuracy.
• Characterize the performance of the new algorithm.
• Enable efficient clustering of millions of biological sequences.

Main Methods:

• Developed Clusterize, an algorithm that sorts sequences by relatedness.
• Linearized the clustering problem through sequence sorting.
• Evaluated Clusterize against established tools like CD-HIT, MMseqs2, UCLUST, and Linclust.

Main Results:

• Clusterize achieves accuracy comparable to popular super-linear methods.
• Demonstrates linear asymptotic scalability, practical for large datasets.
• Outperforms Linclust in both accuracy and cluster size for linear-time clustering.
• Successfully clustered millions of nucleotide and protein sequences.

Conclusions:

• Clusterize offers a scalable and accurate solution for biological sequence clustering.
• Provides a valuable tool for analyzing large-scale genomic and proteomic data.
• Addresses the need for efficient yet precise sequence grouping in bioinformatics.