Abstract—Multiple sequence alignment (MSA) is a difficult yet important problem for bioinformatics research. In most cases, large-scale biological sequence data with high similarity have to be analyzed. Center star method is always used to deal with lots of long sequences. However, square time complexity is a bottleneck for large data. In this paper, a novel method for the MSA problem is proposed, which employs the keyword tree and the sliding window to match a set of substrings and the rest regions are aligned by dynamic programming. The method provides the dynamic adaptive mechanism for the sliding window size and step length. The self-adaptive parameters play a extremely important part for improving the performance of the method. Experimental results show that the proposed method is computational efficient and can obtain good performance.

Index Terms—Multiple sequence alignment, center star method, keyword tree, sliding window.

Yong Sun, Zili Zhang, and Jun Wang are with School of Computer and Information Science, Southwest University, Chongqing, 400715, China (e-mail: likesy999@yahoo.com.cn, zhangzl@swu.edu.cn, kingjun@swu.edu.cn).
Zili Zhang is with School of IT, Deakin University, Australia.

 

Cite:Yong Sun, Zili Zhang, and Jun Wang, "A Novel Algorithm for DNA Multiple Sequence Alignment Based on the Sliding Window and the Keyword Tree," International Journal of Bioscience, Biochemistry and Bioinformatics vol. 3, no. 3, pp. 271-275, 2013.