SMAlign: Alignment of DNA sequences with gap constraints

Faisal Alobaid, Kishan Mehrotra, Chilukuri K Mohan, Ramesh Raina

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

1 Scopus citations

Abstract

Optimal alignment of structured motifs, where the gaps between the motif boxes have known positions and known minimum and maximum sizes, is an important problem. The well known classical algorithms by Needleman-Wunsch and Smith-Waterman do not provide optimal solutions. We present SMAlign, an efficient algorithm for optimal pairwise alignment of DNA sequences with known gap constraints, based on the branch and bound approach. The time and space complexities of SMAlign are O(lMlN) and O(bl MlN), respectively, for aligning two structured motifs of lengths lM and lN having at most b boxes.

Original languageEnglish (US)
Title of host publication4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012
Pages43-50
Number of pages8
StatePublished - 2012
Event4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012 - Las Vegas, NV, United States
Duration: Mar 12 2012Mar 14 2012

Other

Other4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012
CountryUnited States
CityLas Vegas, NV
Period3/12/123/14/12

Keywords

  • Branch and bound
  • Combinatorial optimization
  • Dynamic programming
  • Gap constraints
  • Structured motif alignment

ASJC Scopus subject areas

  • Biomedical Engineering
  • Health Information Management

Cite this

Alobaid, F., Mehrotra, K., Mohan, C. K., & Raina, R. (2012). SMAlign: Alignment of DNA sequences with gap constraints. In 4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012 (pp. 43-50)