kClust: fast and sensitive clustering of large protein sequence databases

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• High-throughput sequencing rapidly expands public sequence databases, leading to inefficiencies in searching and redundancy.
• Traditional sequence clustering methods face computational challenges due to quadratic time complexity with increasing database size.
• Effective clustering is crucial for organizing homologous sequences, enhancing homology search performance, and improving data readability.

Purpose of the Study:

• To develop a fast and sensitive method for clustering large protein sequence databases.
• To enable clustering of massive datasets down to 20%-30% maximum pairwise sequence identity.
• To provide a practical solution for the growing challenge of sequence database redundancy and search inefficiency.

Main Methods:

• Introduced kClust, a novel clustering method utilizing an alignment-free prefilter based on cumulative 6-mer similarity scores.
• Employed a dynamic programming algorithm operating on 4-mer similarities for efficient pairwise sequence comparison.
• Incorporated an optional profile-sequence comparison mode for enhanced sensitivity, using profiles from previous clustering iterations.

Main Results:

• kClust achieves clustering of large protein databases like UniProt within days, down to 20%-30% sequence identity.
• Demonstrated a speed increase of two to three orders of magnitude compared to NCBI BLAST-based clustering.
• kClust shows comparable sensitivity and a lower false discovery rate than BLAST, CD-HIT, and UCLUST for multidomain sequences.

Conclusions:

• kClust addresses the need for a fast, sensitive, and accurate tool for clustering large protein sequence databases below 30% identity.
• The method offers significant improvements in speed and accuracy over existing tools for large-scale sequence analysis.
• kClust is freely available, promoting its adoption in bioinformatics research and applications.