Title: A space-efficient algorithm for three sequence alignment and ancestor inference

Authors: Feng Yue, Jijun Tang

Addresses: Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA. ' Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA

Abstract: We propose a novel algorithm to simultaneously align three biological sequences with affine gap model and infer their common ancestral sequence. It applies the divide-and-conquer strategy to reduce the memory usage from O(n³) to O(n²). At the same time, it is based on dynamic programming and thus the optimal alignment is guaranteed. We implemented the algorithm and tested it extensively with both BAliBASE dataset and simulation data generated by Random Model of Sequence Evolution (ROSE). Compared with other popular multiple sequence alignment tools such as ClustalW and T-Coffee, our program produces not only better alignment, but also better ancestral sequence.

Keywords: three sequence alignment; median sequences; tree alignment; phylgogeny reconstruction; bioinformatics; data mining; ancestor inference; affine gap model; ancestral sequences.

DOI: 10.1504/IJDMB.2009.024851

International Journal of Data Mining and Bioinformatics, 2009 Vol.3 No.2, pp.192 - 204

Published online: 01 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article