Abstract
In this paper, we design an algorithm of computing a constrained multiple sequence alignment (CMSA) for guaranteeing that the generated alignment satisfies the user-specified constraints that some particular residues should be aligned together If the number of residues needed to be aligned together is a constant a, then the time-complexity of our CMSA algorithm for aligning K sequences is O(αKn 4 ), where n is the maximum of the lengths of sequences. In addition, we have build up such a CMSA software system and made several experiments on the RNase sequences, which mainly function in catalyzing the degradation of RNA molecules. The resulting alignments illustrate the practicability of our method.