A new heuristic for multiple sequence alignment

Ankit Agrawal*, Siddhartha Kumar Khaitan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Multiple sequence alignment is an important task in bioinformatics which forms the basis of many other tasks like protein structure prediction, protein function prediction and phylogenetic analysis. An optimal multiple sequence alignment for a given set of sequences is difficult to determine by standard dynamic programming algorithms because of impractically high computational complexity. Therefore, heuristics are commonly used to reduce the alignment construction time, even though the resulting alignment may not be optimal. ClustalW is one of the most popular progressive multiple sequence alignment algorithm where the pairwise sequence alignments are done according to a static guide-tree based on the sequences alone. For a multiple sequence alignment of N sequences, each of length O(n), the ClustalW algorithm takes O(N 2n2) time. In this paper, a modification to the algorithm is proposed which reduces the time complexity of the algorithm to O(N log 2 Nn2). The proposed heuristic also makes the alignment process more dynamic as the order of sequences added to the multiple sequence alignment also depends on the already computed multiple sequence alignments.

Original languageEnglish (US)
Title of host publication2008 IEEE International Conference on Electro/Information Technology, IEEE EIT 2008 Conference
Pages215-217
Number of pages3
DOIs
StatePublished - Sep 15 2008
Event2008 IEEE International Conference on Electro/Information Technology, IEEE EIT 2008 Conference - Ames, IA, United States
Duration: May 18 2008May 20 2008

Other

Other2008 IEEE International Conference on Electro/Information Technology, IEEE EIT 2008 Conference
CountryUnited States
CityAmes, IA
Period5/18/085/20/08

ASJC Scopus subject areas

  • Information Systems and Management
  • Electrical and Electronic Engineering
  • Communication

Fingerprint Dive into the research topics of 'A new heuristic for multiple sequence alignment'. Together they form a unique fingerprint.

  • Cite this

    Agrawal, A., & Khaitan, S. K. (2008). A new heuristic for multiple sequence alignment. In 2008 IEEE International Conference on Electro/Information Technology, IEEE EIT 2008 Conference (pp. 215-217). [4554299] https://doi.org/10.1109/EIT.2008.4554299