COMPREHENSIVE STUDY ON ITERATIVE ALGORITHMS OF MULTIPLE SEQUENCE ALIGNMENT

Multiple sequence alignment is an important problem in the biosciences . To date, most multiple alignment systems have employed a tree-based algorithm, which combines the results of two-way dynamic programming i n a tree-like order of sequence similarity. The alignment quality is n ot, however; high enough when the sequence similarity is low. Once an error occur's in the alignment process, that error can never be correc ted. Recently, an effective new class of algorithms has been developed . These algorithms iteratively apply dynamic programming to partially aligned sequences to improve their alignment quality. The iteration co rrects any errors that may have occurred in the alignment process. Suc h an iterative strategy requires heuristic search methods to solve pra ctical alignment problems. Incorporating such methods yields various i terative algorithms. This paper reports our comprehensive comparison o f iterative algorithms. We proved that performance improves remarkably when using a tree-based iterative method, which iteratively refines a n alignment whenever two subalignments are merged in a tree-based way. We propose a tree-dependent, restricted partitioning technique to eff iciently reduce the execution time of iterative algorithms.