Multiple Sequence Alignment using DP

Multiple sequence alignment (MSA) is an important problem in molecular biology. Biological sequences are aligned with each other vertically to show possible similarities or differences among these sequences. The similarities may reveal evolutionary history and are clues about common biological functions of the sequences. The information of similarity and difference can then be used to predict the secondary or tertiary structure of new sequences and to find the relationships between sequences. MSA is also often used for constructing evolutionary trees from DNA sequences and for analyzing the structures to help in designing new proteins. Usually, to solve an MSA problem is to find an alignment of multiple sequences with the highest score based on a given scoring criterion among sequences.