3GOLD: optimized Levenshtein distance for clustering third-generation sequencing data.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Third-generation sequencing technologies produce data with higher error rates than previous methods.
• Accurate clustering of error-rich sequencing data requires accounting for error types and frequencies.
• Traditional Levenshtein distance has limitations for biological sequence analysis.

Purpose of the Study:

• To modify the Levenshtein distance algorithm for improved clustering of error-rich biological sequencing data.
• To enhance the speed and accuracy of sequence clustering for third-generation sequencing datasets.
• To develop a robust clustering approach suitable for datasets with known or unknown cluster centroids.

Main Methods:

• Introduced bidirectional frameshift allowance with accommodation caps.
• Implemented weighted error discrimination for insertions, deletions, and substitutions.
• Optimized the Levenshtein distance algorithm for computational speed and accuracy.

Main Results:

• The modified algorithm, 3GOLD, demonstrated significantly higher clustering sensitivity compared to Sequence-Levenstein distance, Levenshtein distance, Starcode, CD-HIT-EST, and DNACLUST on simulated and biological datasets.
• Achieved substantial improvements in clustering sensitivity, particularly for third-generation sequencing data (e.g., ONT MinION, PacBio Sequel).
• Significantly enhanced computational speed of the Levenshtein distance algorithm.

Conclusions:

• The modified Levenshtein distance (3GOLD) offers superior speed and accuracy for clustering third-generation sequencing data.
• The approach effectively handles datasets with both known and unknown cluster centroids, including those with unique molecular identifiers or barcodes.
• Demonstrated high accuracy in resolving small clusters and reducing the number of singletons, making it valuable for diverse biological applications.