The Study Of Optimization Algorithm For Multiple Sequence Alignment

Sequence alignment is an important part of bioinformatics, which is the foundation to analyse and mine the data from the biomolecule sequences. Using sequence alignment, we can conclude the structure of a proteid sequence according to the DNA sequences. We can also search a new sequence within the base database. Through sequence alignment, we can get the evolution of biology and get the structure and the function of biomolecules.Firstly, we describe the concepts about the molecular biology. We describe the technology of sequence alignment in the round, including the basic principle of sequence alignment, global alignment, local alignment, pair-wise sequence alignment, multiple sequence alignment. There are several software systems to align sequences. FASTA and BLAST systems can align two sequences in order to search the database. ClustalW can align multiple sequences, which is a much better software system of sequence alignment at present.In the study of multiple sequence alignment, we focus our minds on the progressive algorithm for global multiple sequence alignment. We expound the theory of the progressive algorithm, which contain some other algorithms such as dynamic programming, Needleman-Wunsch algorithm. We discuss the construction of a phylogenetic tree with neighbor-joining method. The functions of gap penalty and substitution matrix have been analysed. Above all, we design the software system of global multiple sequence alignment based on the progressive algorithm with object-oriented technology. We give the activity diagrams and the class diagrams of the system. Under JBuilderX programming environment, we can get the UML diagrams created automatically. The alignment results have been analysed correctly.On the basis of the progressive algorithm, we put forward the iterative algorithm can improve global multiple sequence alignment. And we give the design of iterative algorithm to improve the system. 142 files have been test in BAliBASE, of which there are some examples in the thesis. We compare the results of the improved system with the results of the system before, and conclude that the iterative algorithm improve the system based on the progressive algorithm effectively.