Abstract
We design a new algorithm of computing constrained multiple sequence alignment (CMSA) for guaranteeing that generated alignment satisfies the user- specified constraints that some particular residues should be aligned together. The first step of our strategy is design a constrained pairwise sequence alignment. Next, based on the concept of progressive alignment, we use the constrained pairwise sequence alignment to progressively merge the sequences. The time complexity of our CMSA algorithm for aligning K sequences is O(Kn4),where n is the maximum of lengths of sequences. We experimented our algorithm on RNases sequences with known structure and results of our experiment are all the important residues of active sites are well aligned together.