Stellar

STellar performs local pairwise alignment of genomic sequences, detecting all ε-alignments (local alignments defined by a minimal length and maximal error rate) with full sensitivity under the edit distance model.

Key Features:

• Full sensitivity: Guarantees detection of all ε-alignments meeting specified minimal length and maximal error rate.
• Two-step process: Combines an initial lossless filtering stage with a subsequent exact verification stage.
• Filtering (SWIFT): Uses the SWIFT algorithm for efficient lossless filtering of candidate matches.
• Verification: Employs a newly developed exact verification strategy to ensure all significant alignments are reported.
• Edit distance model: Operates under the edit distance model for alignment scoring and error-rate definitions.
• Scalability: Designed for practical, fast analysis of very long genomic sequences without compromising sensitivity.
• Sensitivity versus heuristics: Detects alignments that heuristic tools such as BLAST or BLAT may miss.

Scientific Applications:

• Large-scale genomic comparisons: Detection of local pairwise alignments in very long genomic sequences.
• Comprehensive alignment discovery: Exhaustive reporting of alignments above length and error thresholds for complete match detection.
• Validation and benchmarking: Validated on simulated and real genomic data to assess sensitivity relative to heuristic methods.

Methodology:

Two-step procedure: lossless filtering via the SWIFT algorithm followed by an exact verification strategy to report all ε-alignments under the edit distance model.