A Maximum Weighted Path Approach To Multiple Alignment For DNA Sequences

Sequence alignment is the most common fundamental subject in modern bioinformatics. Through sequence alignment, we can predict the structure and function of new sequence, analysis the evolutionary linkage of sequences, do phylogenetic analysis. Still there is not an optimal algorithm of multiple sequence alignments. We present a novel approach called MWPAlign to do global and local multiple alignment for DNA sequences.Firstly, we describe the basic problem about sequence alignment like: gap penalty, substitution matrix and standard of assessing alignment result. Secondly, the accurate method called dynamic programming algorithm of pairwise alignment is studied and implemented in the form of global and local. For the multiple sequence alignment, we mainly study and describe the algorithm ClustalW which is based on the progressive alignment strategy and the POA algorithm which is based on the graph method. The main production can be briefly summarized as follows:①Through analysising the structure of de Bruijn graph and the DNA fragment assembly algorithm based on the Eulerian path approach, we proposed a maximum weighted path approach to global multiple alignment for DNA sequences. We implemented this algorithm and compared it with currently used method, the result show that our algorithm get a lower computation speed, and for large number of sequences with lower mutation rate than 5.2%, MWPAlign generates better alignment results as compared to ClustalW, T-Coffee and HMMT.②Through researching the declumping algorithm of pairwise alignment and the application of the Poisson distribution in assessing sequence alignment result, we extend our maximum weighted path approach , and proposed a maximum weighted path approach to local multiple alignment for DNA sequences. We apply this local method to the simulated sequences, the result show that our method is a feasible local multiple sequence alignment algorithm.The research contents are innovated algorithm of sequence alignment in bioinformatics. These algorithms are advanced more evidently than traditional algorithms in biology sensitivity and computing efficiency.