Clover

Clover clusters deoxyribonucleic acid (DNA) sequences to provide scalable, accurate clustering for DNA-based data storage applications.

Key Features:

• Linear Computational Complexity: Achieves linear time complexity for clustering large-scale sequence datasets, supported by theoretical proofs.
• Low Memory Usage: Maintains low space complexity enabling execution on standard computing hardware, including a single home computer.
• Tree Structure Utilization: Employs a tree structure for interval-specific retrieval to avoid computing Levenshtein distance.
• High Accuracy Rate: Demonstrates greater than 99% clustering accuracy in experimental results.
• Performance Benchmarks: Clustered 10 million DNA sequences into 50,000 classes in 10 seconds and clustered 10 billion DNA sequences on a single home computer while maintaining linear time scaling.

Scientific Applications:

• DNA-based Data Storage: Supports clustering workflows for DNA-based data storage where synthesis and sequencing processes introduce errors into encoded sequences.
• Large-scale Sequence Clustering: Enables grouping and deduplication at scales of millions to billions of sequences where traditional biological-domain algorithms are too slow.
• Error-tolerant Sequence Analysis: Adapts to the unique characteristics and error profiles of DNA storage sequences to improve clustering reliability.

Methodology:

Leverages a tree structure for interval-specific retrieval to avoid Levenshtein distance calculations, with theoretical proofs supporting linear time and low space complexity.