How to find optimal alignment parameters

John Kececioglu

For as long as biologists have been computing alignments of sequences, the
question of what are the right values to use for scoring substitutions and gaps
has persisted.  While some choices for substitution scores have become common,
largely by convention, there is certainly no standard for choosing gap
penalties.  One way to resolve this question is to learn the appropriate
parameter values by solving the Inverse String Alignment Problem: given examples
of correct alignments, find parameter values that make all the examples be
optimal-scoring alignments of their strings.

We present a new polynomial-time algorithm for Inverse String Alignment that is
simple to implement, fast in practice, numerically robust, and for the first
time, can learn hundreds of parameters simultaneously.  The approach actually
solves Inverse Alignment for any version of string alignment in which (1) the
objective function is a linear function of the scoring parameters (such as
standard local and global alignment), and for which (2) an optimal alignment can
be efficiently computed when the values of the parameters are fixed.  The
approach is also flexible: minor modifications allow us to solve inverse unique
alignment (find parameter values that make the input alignments be the unique
optimal alignments of their strings), and inverse near-optimal alignment (find
parameter values that make the input alignments be as close to optimal as
possible).  Computational results with an implementation for global alignment
show that, for the first time, we can find best-possible values for all 212
parameters of the standard protein-sequence scoring-model from hundreds of
alignments in a few minutes of computation.