Multiple Sequence Alignment Using Dynamic Programming Technique

Multiple Sequences alignment (MSA) is one of the prominent methods in the modern biology. MSA is used in different areas of bioinformatics, such as function prediction, structure prediction and different genes evolution. Nevertheless, the MSA is also considered as a NP-hard, hence heuristic approaches are needed to align a large set of data within a reasonable time.Many methods are used to align such as dynamic method, heuristic method, progressive method and etc. Among these existing heuristic approaches, CLUSTALW has been found to be the progressive alignment program which provides one of the best quality alignments while the POA program always provides quite fast alignments. There are many existing methods that can provide different results; however, we can’t determine which method is the best. This is because, these methods have different advantage.In this thesis, the theory of multiple sequence alignment and existing MSA program will be introduced. Afterwards, this research will present a solution based on dynamic program, there-out will give the optimal score for comparing mentioned sequences. Gradually, the study will implement from Pairwise sequences alignment, three sequences alignment to multiple sequences center star alignment (MCSA). Each implementation, sequences will be generated automatically which depend on their mutation rate and length, the sequences will be used to run in program.The innovation in this study is matrix composition based on dynamic program. Our analyzed matrix will be filled from the bottom by minimum score. Otherwise, the result of the sequence alignment depends on:"score matrix, gap, method". This thesis also expresses the effectiveness of dynamic and progressive program.