MeShClust

MeShClust v3.0 performs high-quality clustering of DNA sequences using the mean shift algorithm to identify accurate sequence cluster centers for downstream biological analyses.

Key Features:

• Mean Shift Algorithm: Employs the unsupervised mean shift algorithm with theoretical convergence to cluster centers to improve cluster quality relative to CD-HIT and UCLUST.
• Alignment-Free Identity Scores: Uses alignment-free identity scores to assess sequence similarity without performing sequence alignments.
• Out-of-Core Strategy: Implements an out-of-core processing strategy to scale to large datasets beyond main memory limits.
• Performance Evaluation: Evaluated on 22 synthetic datasets and five real-world datasets, showing superior cluster quality compared to CD-HIT, UCLUST, and MeShClust v1.0 across similarity levels.
• Application to Diverse Data Sets: Demonstrated improvements in cluster quality (reported ranges 55%–300%) on real datasets including human microbiomes and maize transposons and on long bacterial sequences where other tools are not applicable.
• Parameter Estimation: Includes estimation of a key parameter that governs cluster membership to refine clustering outcomes.
• Resource Requirements: Requires higher computational time and memory compared to some predecessors such as CD-HIT and UCLUST.

Scientific Applications:

• Human microbiome analysis: Clustering of microbiome-derived DNA sequences to define operational taxonomic units or sequence clusters.
• Plant genetics (maize transposons): Clustering of transposon sequences for analyses of transposable element families and diversity.
• Viral sequence analysis: Grouping viral sequences for diversity, epidemiology, and evolutionary studies.
• Long bacterial sequence clustering: Clustering of long bacterial sequences where alignment-based tools are not applicable or perform poorly.

Methodology:

Uses the mean shift algorithm with alignment-free identity scores, an out-of-core processing strategy, and estimation of a cluster-membership parameter; performance was assessed on 22 synthetic and five real datasets.