Fast and memory efficient partial order alignment with minipoa

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Partial order alignment (POA) is crucial for long-read sequencing applications like error correction, genome assembly, and pangenomics.
• Existing POA algorithms face challenges with high time and memory demands, limiting their scalability for large datasets.

Purpose of the Study:

• To introduce minipoa, a novel tool designed for fast and memory-efficient partial order alignment.
• To demonstrate minipoa's effectiveness in improving computational efficiency and accuracy for large-scale genomic analyses.

Main Methods:

• Minipoa integrates seed-chain-align heuristics, adaptive/static banding, and SIMD optimizations for enhanced performance.
• The tool was evaluated on simulated long-read datasets (PacBio, ONT) and real-world multiple sequence alignment datasets.

Main Results:

• Minipoa offers up to a 5-fold speedup and 16-fold memory reduction compared to abPOA.
• Achieves superior alignment accuracy, outperforming MAFFT in low-similarity scenarios with higher Total Column scores.
• Successfully aligned large datasets, including megabase-long genomes and millions of sequences (e.g., SARS-CoV-2).

Conclusions:

• Minipoa provides a computationally efficient and accurate solution for partial order alignment, addressing limitations of previous methods.
• Its scalability and performance make it suitable for integration into existing long-read analysis workflows and large-scale pangenomics.