Research On Algorithms Of Multiple Sequence Alignment Based On Iterative Strategy

Multiple sequence alignment is one of the core research topics of bioinformatics. Biologists can do phylogenetic analysis, construction of protein family, structure prediction of RNA and protein and so on, which will be helpful for analyzing furthermore. Multiple sequence alignment is a problem with high computation complexity, which determines that it can not use standard dynamic programming algorithm, but only to use heuristic strategies getting an approximate results. At present, the progressive multiple sequence alignment is a most widely used heuristic algorithm. First, it calculate a distance matrix through all pairwise sequences alignment, and then construct a phylogenetic tree according to the distance matrix, finally do the multiple sequence alignment one by one according to the phylogenetic tree. However, its local minimum easily leads to less accurate result and its high computation complexity leads to the long run time. This thesis mainly investigates how to improve the above two limitations. Its main works and contributions are summarized as follows:The current most widely used progressive multiple sequence alignment algorithm ClustalW is analyzed in detail. The existed limitations of ClustalW are pointed out: local minimum, and its lower accuracy to distantly related sequences. Then, a new iterative optimization algorithm based on center sequence, IS-ClustalW, is presented. First, an initial result MSA is produced by ClustalW; then according to the center sequence, the pairwise global alignment in MSA is checked, and in the iterative process pairwise local alignment information is used to correct the MSA. The test results show that IS_ClustalW has higher accuracy than original ClustalW and solves the local minimum at some extent.Based on task partition strategy and multi-thread parallel model, the pairwise alignment stage and the iterative optimization stage in IS-ClustalW are paralleled. The testing results indicate that the proposed algorithms and implementation are of high efficiency.