Research On Similarity Comparison Algorithm For DNA Sequence

Abstract:DNA sequence alignment is the most important and basic research field in bioinformatics. It is also an important method of studying the homology between species. With the rapid increase of bio-sequence date, how to improve both efficiency and sensitivity has become an urgent problem in sequence alignment.Optimal methods are applied to improve the efficiency of sequence alignment in this thesis. The main contents and contributions can be briefly summarized as follows:When using graphical representation of DNA, partial differences are important elements to evaluate similarity of DNA sequence. With the accumulation of partial differences, some DNA sequences show great difference in global. It can lead to misjudgment. Based on the analysis of deficiency of existing DTW algorithm, a novel algorithm about similarity analysis of DNA sequences based on segmentation is proposed in this thesis. By reasonable segmentation, this method maintains effects of partial differences, meanwhile, limits the scale of partial differences. Finally, the first exon coding sequences of the P-globin of nine species were analyzed. The result was compared with existing algorithm. Our method provides more exact result, higher sensitivity, which could help to promote categorization ability of species.Ant colony algorithm which is a bionic optimization algorithm. It has shown many promising properties in solving complicated optimization problem. Applying the thought of ant colony algorithm to DNA sequence processing is presented a new dynamic time programming based on ant colony algorithm-Ant Dynamic Programming. The algorithm is used to search a global optimization path which is indicated the degree of the similarity between the DNA sequence. The new state transfer probability and updating rule of the pheromone intensity use both the global and the local character of DNA sequence. Theoretic analyses and simulation experiment all certify the method feasibility.