Grammar-Based Distance in Progressive Multiple Sequence Alignment

DSpace/Manakin Repository

Grammar-Based Distance in Progressive Multiple Sequence Alignment

Citable link to this page


Title: Grammar-Based Distance in Progressive Multiple Sequence Alignment
Author: Russell, David J; Sayood, Khalid; Otu, Hasan H

Note: Order does not necessarily reflect citation order of authors.

Citation: Russell, David J., Hasan H. Otu, and Khalid Sayood. 2008. Grammar-based distance in progressive multiple sequence alignment. BMC Bioinformatics 9: 306.
Full Text & Related Files:
Abstract: Background: We propose a multiple sequence alignment (MSA) algorithm and compare the alignment-quality and execution-time of the proposed algorithm with that of existing algorithms. The proposed progressive alignment algorithm uses a grammar-based distance metric to determine the order in which biological sequences are to be pairwise aligned. The progressive alignment occurs via pairwise aligning new sequences with an ensemble of the sequences previously aligned. Results: The performance of the proposed algorithm is validated via comparison to popular progressive multiple alignment approaches, ClustalW and T-Coffee, and to the more recently developed algorithms MAFFT, MUSCLE, Kalign, and PSAlign using the BAliBASE 3.0 database of amino acid alignment files and a set of longer sequences generated by Rose software. The proposed algorithm has successfully built multiple alignments comparable to other programs with significant improvements in running time. The results are especially striking for large datasets. Conclusion: We introduce a computationally efficient progressive alignment algorithm using a grammar based sequence distance particularly useful in aligning large datasets.
Published Version: doi:10.1186/1471-2105-9-306
Other Sources:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search