Nongreedy Unbalanced Huffman Tree Compressor for Single and Multifasta Files.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Science

Background:

• Next-generation sequencing generates massive genomic datasets, posing storage and transmission challenges.
• General-purpose compressors like gzip and bzip2 do not leverage unique DNA data properties (small alphabet, repeats).
• Existing DNA-specific Huffman encoding methods (UHT) show promise but are greedy.

Purpose of the Study:

• To develop an improved lossless compressor for genomic data.
• To enhance compression ratios and speed for FASTA and multi-FASTA files.
• To address limitations of existing greedy unbalanced Huffman tree (UHT) algorithms.

Main Methods:

• Development of a novel nongreedy unbalanced Huffman tree (NUHT) algorithm.
• Implementation of a lossless, non-reference-based compressor for genomic sequences.
• Comparative analysis against gzip, bzip2, and UHT using compression ratio and speed metrics.

Main Results:

• The proposed NUHT algorithm achieved superior compression ratios compared to gzip, bzip2, and UHT.
• NUHT demonstrated a seven-fold increase in speed over the UHT algorithm.
• The compressor effectively handles FASTA and multi-FASTA formats losslessly.

Conclusions:

• NUHT offers a significant advancement in genomic data compression.
• The algorithm's efficiency in compression and speed makes it valuable for handling large-scale genomic data.
• NUHT provides a more effective solution than general-purpose and existing specialized compressors.