A sequential iterative refinement optimization method to multiple sequence alignment

Abstract

The multiple sequence alignment of protein sequences or DNA sequences has become one of the most important tools in the modern molecular biology. In order to do the fast and efficient multiple sequence alignment analysis, a lot of methods and programs such as dynamic programming, progressive and iterative approaches, have been developed. This thesis introduced a a??Sequential Iterative Refinement Optimization Algorithm (SIROA)a?? approach. The basic procedure of the SIROA is a heuristic progressive approach; however, we do the iterative refinement optimization for the sub-aligned sequences group in each step of the progressive alignment. This iterative process increases the sensitivity of the traditional progressive alignment method and corrects the possible early made mistakes. In order to reduce the additional computational complexity from the iterative procedures, we partition the sequence set into some blocks before the progressive alignment. Numerical multiple sequence alignment results reference to BAliBASE database have been done for evaluating the SIROA method and comparing it with other approaches.