GASSST

GASSST performs global alignment of short sequencing reads to reference sequences, providing fast and sensitive alignment for next-generation sequencing data including long reads by using multi-tiered filtering and precomputed four-base-word alignment scores.

Key Features:

• No indel restrictions: Performs alignments without imposing limits on the number of insertions or deletions (indels), preserving accuracy for datasets with long reads.
• Seed-based alignment: Initiates alignment from a seed phase to generate candidate alignments for downstream evaluation.
• Efficient filtering mechanism: Employs a filtering step that discards most alignments from the seed phase before invoking the computationally expensive dynamic programming algorithm.
• Multi-tiered filtering system: Uses a series of progressively complex filters to rapidly eliminate non-viable candidate alignments across various configurations.
• Precomputed alignment score table: Leverages a precomputed table of alignment scores for short four-base words aligned against each other, reused multiple times by an algorithm that approximates the full dynamic programming score.
• Dynamic programming for final scoring: Applies dynamic programming for final alignment scoring after candidate reduction by filters.
• Comparative performance: Demonstrated high sensitivity and faster execution than BWA, BFAST, SSAHA2, and PASS in comparative studies.

Scientific Applications:

• High-throughput read alignment: Aligns large volumes of next-generation sequencing reads to reference sequences with sensitivity and speed.
• Genome assembly: Provides alignments useful for contig scaffolding and assembly validation when handling short and long reads.
• Variant calling: Supplies sensitive alignments that support detection of single-nucleotide variants and indels.
• Comparative genomics: Enables sequence comparison across genomes through high-sensitivity alignments.

Methodology:

GASSST uses a seed-based approach followed by a multi-tiered filtering pipeline that applies a precomputed four-base-word alignment score table to discard most candidates before using an algorithm that approximates the full dynamic programming score and finally invokes dynamic programming for final alignment scoring.