kClust: fast and sensitive clustering of large protein sequence databases
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
Background: Fueled by rapid progress in high-throughput sequencing, the size of public sequence databases doubles every two years. Searching the ever larger and more redundant databases is getting increasingly inefficient. Clustering can help to organize sequences into homologous and functionally similar groups and can improve the speed, sensitivity, and readability of homology searches. However, because the clustering time is quadratic in the number of sequences, standard sequence search methods are becoming impracticable. Results: Here we present a method to cluster large protein sequence databases such as UniProt within days down to 20%-30% maximum pairwise sequence identity. kClust owes its speed and sensitivity to an alignment-free prefilter that calculates the cumulative score of all similar 6-mers between pairs of sequences, and to a dynamic programming algorithm that operates on pairs of similar 4-mers. To increase sensitivity further, kClust can run in profile-sequence comparison mode, with profiles computed from the clusters of a previous kClust iteration. kClust is two to three orders of magnitude faster than clustering based on NCBI BLAST, and on multidomain sequences of 20%-30% maximum pairwise sequence identity it achieves comparable sensitivity and a lower false discovery rate. It also compares favorably to CD-HIT and UCLUST in terms of false discovery rate, sensitivity, and speed. Conclusions: kClust fills the need for a fast, sensitive, and accurate tool to cluster large protein sequence databases to below 30% sequence identity. kClust is freely available under GPL at http://toolkit.lmb.uni-muenchen.de/pub/kClust/.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Cd-hit: Accelerated for clustering the next-generation sequencing data
Fu, L., Niu, B., Zhu, Z., Wu, S., & Li, W. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts565 · Cited by 11,175
OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes
Li, L., Stoeckert, C. J., & Roos, D. S. (2003) · Genome Research · doi:10.1101/gr.1224503 · Cited by 5,707 · cited 1×
“Others use them to cluster sequences into orthologous or functionally similar groups [16-22].”
MethodThe Pfam protein families database
Finn, R. D., Mistry, J., Tate, J., Coggill, P., Heger, A., Pollington, J. E., Gavin, O. L., Gunasekaran, P., Ceric, G., Forslund, K., et al. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkp985 · Cited by 2,694
HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment
Remmert, M., Biegert, A., Hauser, A., & Söding, J. (2012) · Nature Methods · doi:10.1038/nmeth.1818 · Cited by 2,288
Self-citationUniRef: comprehensive and non-redundant UniProt reference clusters
Suzek, B. E., Huang, H., McGarvey, P., Mazumder, R., & Wu, C. H. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm098 · Cited by 1,613
A Catalog of Reference Genomes from the Human Microbiome
The Human Microbiome Jumpstart Reference Strains Consortium, Nelson, K. E., Weinstock, G. M., Highlander, S. K., Worley, K. C., Creasy, H. H., Wortman, J. R., Rusch, D. B., Mitreva, M., Sodergren, E., et al. (2010) · Science · doi:10.1126/science.1183605 · Cited by 702
Cited by
Treangen, T. J., Ondov, B., Koren, S., & Phillippy, A. M. (2014) · Genome biology · doi:10.1186/preaccept-2573980311437212 · Cited by 1,654
Clustering huge protein sequence sets in linear time
Steinegger, M., & Söding, J. (2018) · Nature Communications · doi:10.1038/s41467-018-04964-5 · Cited by 875
“Similar to the k-mer prefilter used in CD-HIT, UCLUST, kclust and MMseqs [8, 11, 26, 27], the preclustering reduces the number of comparisons by a large factor F using the slow, exact measure, but the time complexity of the ex240 act distance calculation O(N(2)/F ) is still quadratic in N .”
MethodSelf-citationImproved PEP-FOLD Approach for Peptide and Miniprotein Structure Prediction
Shen, Y., Maupetit, J., Derreumaux, P., & Tufféry, P. (2014) · Journal of Chemical Theory and Computation · doi:10.1021/ct500592m · Cited by 636
Alignment-free sequence comparison: benefits, applications, and tools
Zielezinski, A., Vinga, S., Almeida, J., & Karlowski, W. M. (2017) · Genome Biology · doi:10.1186/s13059-017-1319-7 · Cited by 542
1,520 reference genomes from cultivated human gut bacteria enable functional microbiome analyses
Zou, Y., Xue, W., Luo, G., Deng, Z., Qin, P., Guo, R., Sun, H., Xia, Y., Liang, S., Dai, Y., et al. (2019) · Nature Biotechnology · doi:10.1038/s41587-018-0008-8 · Cited by 542
Metadata
- Authors
- Hauser, M., Mayer, C. E., & Söding, J.
- Venue
- BMC Bioinformatics
- Published
- 2013-08-15
- Volume
- 14
- Issue
- 1
- Pages
- 248-248
- ISSN
- 1471-2105 (ISSN-L)
- OpenAlex
- W2103187775
- Cited by
- 98
- References
- 6
- FWCI
- 4.57
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: kClust: fast and sensitive clustering of large protein sequence databases. https://app.cochat.ai/papers/10.1186/1471-2105-14-248
- The paper
- Hauser, M., Mayer, C. E., & Söding, J. (2013). kClust: fast and sensitive clustering of large protein sequence databases. BMC Bioinformatics. https://doi.org/10.1186/1471-2105-14-248
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.