Progressive multiple alignment with constraints

A progressive alignment algorithm produces a multialignment of a set of sequences by repeatedly aligning pairs of sequences and/or previously generated alignments. We describe a method for guaranteeing that the alignment generated by a progressive alignment strategy satisfies a user-specified collection of constraints about where certain sequence positions should appear relative to others. Our main result is an algorithm to compute just the prime constraints that are implied by the user-given constraints; these are shown to be precisely the constraints that the alignment algorithm must obey. In practice, the time required to handle constraints is negligible and frequently much less than the time saved because the constraints permit searching a restricted region of the dynamic-programming grid. An alignment of the beta-like globin gene cluster of several mammals illustrates the practicality of the method.