ABSTRACT
The optimum solution to any sequence alignment problem depends on the choice of a number of parameters, such as the penalties for mismatches and gaps. Even slight changes in the parameter values can result in a complete structural change in the optimum alignment. Parametric sequence alignment explores the effect of parameter variation on the optimum alignment over a range of parameter values, to assist in making the right choice for the given circumstances. Several specific problems are of interest. For instance, in sensitivity analysis, the goal is to assess the robustness of an optimum alignment by determining the amount by which the current parameter values can be perturbed without altering the optimality of the alignment. The goal in inverse alignment is to locate the parameter values for which the optimum alignment exhibits certain desired features, for example, a certain number of matches or gaps. These and other questions are the subject of this chapter, which is organized around four interrelated topics: combinatorial complexity, parametric search, construction, and parametric problems in hidden Markov models of sequence alignment. We now give an overview of these issues; more precise definitions can be found in the next section.
