FASTGA

FASTGA finds alignments between two genome sequences more than an order of magnitude faster than previous methods with comparable sensitivity, utilizing a space-efficient trace-point encoding for storage.

Key Features:

• Cache-coherent architecture: Employs only cache-coherent MSD radix sorts and merges for high-performance computation.
• Adaptive seed hit detection: Implements a novel algorithm for finding adaptive seed hits in a linear merge of sorted k-mer tables.
• Adaptive wave alignment: Uses a variant of the Myers adaptive wave algorithm to find alignments around a chain of seed hits, detecting alignments with up to 25-30% variation.
• No pre-masking requirement: Does not require pre-masking of repetitive sequence.
• Space-efficient trace-point encoding: Stores millions of alignments in a fraction of the space of a conventional CIGAR string, further compressed by the ONEcode data system.
• Multiple output formats: Outputs ALN-formatted files, and can produce PSL-formatted alignments or PAF-formatted alignments with or without CIGAR strings.

Scientific Applications:

• Large genome comparison: Compares large genomes such as two bat genomes of size 2.2Gbp and 2.5Gbp in a little over 2 minutes using 8 threads.
• Whole-genome alignment: Produces millions of alignments covering about 60% of each genome for comprehensive comparative genomics analysis.

Methodology:

FASTGA employs a carefully engineered architecture involving cache-coherent MSD radix sorts and merges, a novel algorithm for finding adaptive seed hits in a linear merge of sorted k-mer tables, and a variant of the Myers adaptive wave algorithm to find alignments around a chain of seed hits.