[1] Department of Information Science, University of Tokyo
Hongo, Bunkyo-ku, Tokyo 113, Japan
[2] Information Technology Research Laboratories, NEC Corporation
This paper proposes a k-group alignment algorithm for multiple alignment as a practical method. In iterative improvement methods for multiple alignment, the so-called group-to-group two-dimensional dynamic programming has been used, and in this respect our proposal is to extend the ordinary two-group dynamic programming to a k-group alignment programming. This extension is conceptually straightforward, and here our contribution is to demonstrate that the k-group alignment can be implemented so as to run in a reasonable time and space under standard computing environments. This is established by generalizing the A* search approach for multiple alignment devised by Ikeda and Imai [8]. The k-group alignment method can be directly incorporated in existing methods such as iterative improvement algorithms (Berger and Munson [2], Gotoh [4]) and tree-based (iterative) algorithms (Hirosawa et al. [6]). This paper performs computational experiments of applying the k-group method to iterative improvement algorithms, and shows that our approach can find better alignments in reasonable time.