An Evolutionary Model For Maximum Likelihood Alignment Of DNA Sequences

Sequence alignment is an important fundamental subject in bioinformatics research, which is an important measure to discover the function, structure and evolutionary information in biological sequences. There are many algorithms in this area, which are based on objective functions. The objective functions use substitution matrix and gap penalty to score the processes and results of alignment, and judge the results according to the scores of alignment. The shortage of alignment algorithms which rely on objective functions is that small changes in the scoring system can abruptly change an alignment from a local to a global alignment. For this reason, this paper proposes a maximum likelihood method which is based upon a statistical model of DNA sequence evolution for alignment of two DNA sequences.At first, basic conceptions of sequences alignment are introduced in this paper, while substitution matrices, gap penalties and objective functions are all described in detail with their influences on the sequences alignment, and then the alignment algorithms of pairs of sequences are analyzed in-depth, which usually include the following methods: dot matrix analysis, the dynamic programming (DP) algorithm and word or k-tuple methods, giving the algorithm ideas or the pseudocodes of them. Then, according to the shortage of algorithm relying on objective functions, a maximum likelihood method is presented, which is composed of parameter estimation algorithm and alignment algorithm. The maximum likelihood method uses the evolutionary parameter estimation algorithm to estimate the evolutionary parameters relevant to a pair of unaligned DNA sequences at first, and then alignment procedure uses the parameters to alignment the DNA sequences. This is an independent method, which completely avoids the problems of choosing appropriate scoring matrices based upon scoring matrices' sequence alignments for their different similarities of DNA sequences. Finally, the validity and accuracy of the maximum likelihood method is testified through comparing the results of the maximum likelihood method with the results of FASTA.