Normalized compression distance for DNA classification

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Genomic sequence analysis is crucial for understanding biological systems, including the human microbiome.
• Normalized Compression Distance (NCD) is a low-resource technique that approximates Kolmogorov complexity, showing potential beyond text classification.
• Existing tools like Many-against-Many sequence searching (MMseqs) and Kraken2 are effective but can be resource-intensive.

Purpose of the Study:

• To explore the application of a gzip-based NCD for gene labeling of open reading frames (ORFs) and taxonomic classification of short genomic reads.
• To evaluate NCD's performance as an alternative to deep neural networks (DNNs) and traditional sequence analysis tools in genomics.
• To assess NCD's effectiveness in both in-distribution and out-of-distribution classification tasks.

Main Methods:

• Implementation of a gzip-based Normalized Compression Distance (NCD) algorithm.
• Application of NCD for gene labeling of open reading frames (ORFs).
• Utilizing NCD for taxonomic classification of short sequencing reads.

Main Results:

• Achieved 0.89 accuracy and 0.88 macro-F1 for human gene classification, outperforming other NCD methods.
• Demonstrated superior classification accuracy compared to alignment and exact-match tools in out-of-distribution prokaryotic gene labeling.
• Outperformed sequence-embedding methods in in-distribution prokaryotic gene labeling tasks.

Conclusions:

• Compression-based approaches, specifically NCD, offer an effective alternative for genomic sequence classification.
• NCD shows particular strength in low-data environments and out-of-distribution scenarios.
• Computational complexity (O(MN)) is a limitation for extremely large datasets, but NCD remains a viable low-resource strategy.