Minia

Minia assembles short-read next-generation sequencing (NGS) data into genome sequences using a compact de Bruijn graph representation to minimize memory usage during assembly.

Key Features:

• Compact de Bruijn Graph Representation: Employs Bloom filters to represent de Bruijn graphs following improvements inspired by Chikhi and Rizk (WABI'12), reducing memory usage by approximately 30%–40%.
• Efficient Memory Utilization: Optimizes the de Bruijn graph data structure to achieve substantial memory savings for large NGS datasets without increasing graph construction time.
• Improved Query Performance: Provides faster graph traversal and query times compared to earlier methods, enabling efficient manipulation of graph data during assembly.

Scientific Applications:

• Human Genome Assembly: Assembly of human genomes from short-read NGS data enabled by the reduced memory footprint for large-genome reconstruction.
• Large-Scale Genomic Studies: Supports analysis of multiple genomes and complex genomic regions in comparative, population, and evolutionary genomics by lowering computational resource requirements.

Methodology:

Represents de Bruijn graphs using Bloom filters to conserve memory while maintaining efficient graph traversal and query operations, optimizing space and time complexity.