Efficient and robust search of microbial genomes via phylogenetic compression

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Large-scale genomic datasets are crucial for life sciences research.
• Exponential growth in sequenced genomes challenges traditional search tools like BLAST.
• Efficiently searching vast microbial genome collections is a significant computational hurdle.

Purpose of the Study:

• To introduce phylogenetic compression for efficient searching of large genome collections.
• To improve data compression ratios for genomic data structures.
• To enable rapid, accessible searches of microbial genomes on standard hardware.

Main Methods:

• Developed a technique called phylogenetic compression utilizing evolutionary history.
• Applied lossless phylogenetic compression to assemblies, de Bruijn graphs, and k-mer indexes.
• Created a pipeline for BLAST-like searches on phylogeny-compressed genomic data.

Main Results:

• Achieved compression ratio improvements of one to two orders of magnitude for genomic data structures.
• Demonstrated a BLAST-like search capability on compressed data, aligning genes and plasmids.
• Successfully searched all sequenced bacteria up to 2019 on desktop computers within hours.

Conclusions:

• Phylogenetic compression offers a highly effective solution for searching massive genomic datasets.
• The technique significantly enhances data compression and search efficiency for microbial genomes.
• This approach has broad implications for future genomics infrastructure and computational biology.