3GOLD

3GOLD optimizes Levenshtein distance–based sequence comparison to improve clustering of third-generation sequencing (TGS) data, including Oxford Nanopore Technologies (ONT) MinION and Pacific Biosciences (PacBio) Sequel, that exhibit high sequencing error rates.

Key Features:

• Optimized Levenshtein Distance: Introduces novel modifications to the traditional Levenshtein distance algorithm to account for insertions, deletions, and substitutions characteristic of TGS errors.
• Bidirectional Frameshift Allowance: Permits bidirectional frameshifts with accommodation caps to flexibly handle indels in sequence alignment.
• Weighted Error Discrimination: Applies weights to discriminate between different types of sequencing errors during distance calculation.
• Enhanced Computational Speed: Implements computational optimizations to accelerate Levenshtein distance calculations for large-scale genomic datasets.
• Supports Unknown and Known Centroids: Handles datasets with unknown cluster centroids such as unique molecular identifiers (UMIs) and known centroids such as barcoded datasets.
• Improved Cluster Resolution: Resolves small clusters and reduces the number of singletons in high-error TGS datasets.
• Comparative Performance: Demonstrates higher clustering sensitivity relative to Sequence-Levenshtein distance, traditional Levenshtein distance, Starcode, CD-HIT-EST, and DNACLUST on simulated and biological datasets.

Scientific Applications:

• Clustering of TGS reads: Clusters reads generated by ONT MinION and PacBio Sequel where long reads and high error rates complicate traditional clustering methods.
• UMI-based datasets: Clusters sequences from datasets labeled with unique molecular identifiers (UMIs) when centroids are unknown.
• Barcoded datasets: Clusters barcoded datasets with known centroids to improve assignment accuracy.
• Small-cluster recovery: Improves detection and grouping of small clusters and reduces singletons in sequencing datasets.

Methodology:

Modifies the traditional Levenshtein distance algorithm with bidirectional frameshift allowance and accommodation caps, applies weighted error discrimination, implements computational optimizations to speed distance calculations, and evaluates clustering sensitivity on simulated ONT MinION and PacBio Sequel datasets and biological ONT MinION data versus Sequence-Levenshtein distance, traditional Levenshtein distance, Starcode, CD-HIT-EST, and DNACLUST.