XPARAL

XPARAL characterizes how pairwise sequence alignment optimality depends on scoring parameters by partitioning the scoring-parameter space into maximal convex regions corresponding to equivalence classes of optimal alignments.

Key Features:

• Parametric decomposition: Computes the complete partitioning of the scoring-parameter space into maximal convex regions for a pair of sequences.
• Linear scoring model: Treats the alignment score as a linear function of selected variable parameters, including matches, mismatches, insertions/deletions (indels), and gap penalties.
• Substitution matrix support: Accepts objective functions with or without character-specific substitution matrices (e.g., PAM).
• Convex region construction: Constructs convex polygonal regions in which the same alignment configuration (counts of matches, mismatches, indels, gaps) remains optimal.
• Cooptimal enumeration: Enumerates cooptimal alignment alternatives and reports representative optimal alignments for parameter regions.
• Sensitivity analysis: Quantifies sensitivity of alignment outcomes to scoring weights across the parameter space.

Scientific Applications:

• Secondary-structure alignment: Facilitates exploration of score-parameter effects relevant to secondary-structure alignment robustness.
• Evolutionary inference: Supports principled selection of gap and substitution penalties to inform evolutionary inference.
• Motif analysis: Aids interpretation of alignment robustness and parameter-dependent preservation of motif alignments.

Methodology:

Per pair of sequences, perform parametric decomposition by treating the alignment score as a linear function of selected variable parameters, construct the convex polygonal regions in parameter space where a single alignment configuration (counts of matches, mismatches, indels, gaps) is optimal, and enumerate cooptimal alternatives with representative optimal alignments.