FastGA: fast genome alignment

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Genome sequence alignment is crucial for comparative genomics and understanding evolutionary relationships.
• Existing alignment tools often face performance bottlenecks, especially with large genomes.

Purpose of the Study:

• To develop a significantly faster genome alignment tool with comparable sensitivity to existing methods.
• To introduce a novel, space-efficient alignment storage format.

Main Methods:

• Implemented a cache-local architecture utilizing MSD radix sorts and merges.
• Developed an adaptive seed hit finding algorithm using sorted k-mer tables.
• Employed a variant of the Myers adaptive wave algorithm for alignment refinement.
• Introduced a trace-point encoding and the ONEcode data system for compact alignment storage.

Main Results:

• FastGA achieves >10x speedup in genome alignment compared to previous methods.
• Alignment of two 2 Gbp bat genomes completed in 2.1 minutes on a laptop.
• Generated alignments cover 60% of each genome, stored efficiently in a compact ALN format.
• ALN files are significantly smaller than standard formats (66 MB vs 1.03 GB) and convertible to PAF.

Conclusions:

• FastGA offers a highly efficient and sensitive solution for large-scale genome alignment.
• The novel data system and encoding significantly reduce storage requirements for alignment data.
• FastGA provides a valuable tool for genomic research, accelerating comparative analyses.