Biological Sequence Alignment Algorithm And A Comparative Study

With the development of Human Genome Project(HGP),bioinformatics(the core discipline of life science)is also developing fast.Sequence alignment is the most important manipulation and the fundamental information processing method as well in bioinformatics.Aligning a number of cumulated nucleic acid and protein sequences is significant for discovering functional,structural,and evolutionary information in biological sequences.If two sequences have enough similarity, the two sequences may have common ancestor;if two orginisms are homologous.their sequence should have similarity by certain degree.When a DNA sequence which was newly found is very similar to a known gene sequence ,the DNA sequence has the similar structure and function to that gene sequence.Thus,application of sequence aligning method has significance to the research of genome's structure and function.In this thesis, it introduces the development, research and database of bioinformatics first, then some methods of alignment are described,such as dot matrix sequence comparison,dynamic programming algorithm for sequence global alignment,Smith-Waterman algorithm31ast algorithm,MUMmer,PatternHunter and so on. Comparison is made among above algorithms from angle of running speed and sensitivity. It implemented some algorithms with VC++, such as dot matrix sequence comparison,dynamic programming algorithm for sequence global alignment,Smith-Waterman algorithm.The strategy of gap penalty and substitution matrix is added into the dynamic programming.This paper also related to estimation about homology ,i.e. how to judge the significance of the similarity score,and detail introduction combined with some concrete examples is presented from the angle of statistics.