Introducing Variable Gap Penalties into Three-Sequence Alignment for Protein Sequences

The common-use gap penalty strategies, constant penalty and affine gap penalty, have been adopted in the traditional three-sequence alignment algorithm which considers the insertion, deletion and substitution. However, these strategies are not suitable to protein sequence alignments. For the alignment accuracy of protein sequences, the gap penalty is a major determinant. Incorporating protein structure information to vary the gap penalties can lead to more biologically correct alignments. Here, we present an algorithm to find a global and optimal alignment among three protein sequences by using position- specific gap penalties which allow gap penalties to be varied. Thus, residue-dependent information and protein structure information can be applied to the three-sequence alignment. The experimental results show that our algorithm achieves the significant improvement in the accuracy of alignments than the three-sequence alignment algorithm with the affine gap penalty for protein sequences.