Study Of Multiple Alignment Algorithm For DNA Sequences Based On Graph

Bioinformatics is a science using computers as a tool for biological information storage, retrieval and analysis in the life science research. In bioinformatics, sequence alignment is the most foundation problem. How to obtain better alignment of sequences efficiently is the important theme in it. The research of sequence alignment algorithm plays an important role in bioinformatics, and multiple sequences alignment question the harder to solve.After giving a introduction of the prime pairwise sequence alignment algorithm——the global dynamic programming algorithm, we study the function to gap punishment of pairwise sequence alignment. Then we study the multiple sequences alignment question and introduce the global dynamic programming algorithm of multiple sequences alignment and some typical multiple sequences alignment algorithm i.e. tree alignment algorithm, star alignment algorithm and the widely used CLUSTLAW algorithm. For judging the result of alignment, the paper give us object function.A new algorithm to global multiple alignment——A Multiple Star Alignment Algorithm for DNA Sequences Based on the graph is proposed in this paper. In this algorithm the input sequences are deleaved into sequence of partitions, and the information of the sequence of partitions is recorded in the de Bruijn graph. So if we get the path applying a greedy algorithm from the de Bruijn graph, we will get the consensus sequence which matches the input sequences best. And this algorithm obtains almost linear computation speed of the multiple sequences alignment problem. At last we get the result of multiple alignment with the centre sequence using the star alignment algorithm. In this approach, we improve the star alignment algorithm. Experimental results show that the proposed algorithm is feasible, especially for a large number of sequences with mutation rate lower, the result is better and cost fewer time compairing with the algorithm used widely.