Exonerate

Exonerate performs pairwise sequence alignment for DNA-DNA and DNA-protein comparisons to support sequence comparison and genome annotation.

Key Features:

• Pairwise alignment: Supports both DNA-DNA and DNA-protein alignments for sequence comparison.
• Bounded Sparse Dynamic Programming (BSDP): Implements BSDP to produce rapid approximations of exhaustive alignment methods.
• Model-based alignment framework: Describes alignment algorithms based on their underlying models to enable systematic algorithm specification.
• Automated heuristic development: Enables automated development of efficient heuristic implementations from model descriptions.
• Speed–accuracy trade-off: Balances computational speed and alignment complexity to achieve high accuracy with efficiency.

Scientific Applications:

• Genome annotation: Provides rapid and accurate alignments used in genome annotation workflows.
• Sequence comparison problems: Applies model-derived heuristics across a broad spectrum of sequence comparison tasks.

Methodology:

Uses bounded sparse dynamic programming (BSDP) to approximate exhaustive alignment methods and employs a model-based framework to automate the development of efficient heuristic alignment implementations.