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 Citation (Scopus)

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

Fingerprint

DNA sequences

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)

SMAlign : Alignment of DNA sequences with gap constraints. / Alobaid, Faisal; Mehrotra, Kishan; Mohan, Chilukuri K; Raina, Ramesh.

4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012. 2012. p. 43-50.

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

Alobaid, F, Mehrotra, K, Mohan, CK & 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, 4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012, Las Vegas, NV, United States, 3/12/12.
Alobaid F, Mehrotra K, Mohan CK, Raina R. SMAlign: Alignment of DNA sequences with gap constraints. In 4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012. 2012. p. 43-50
Alobaid, Faisal ; Mehrotra, Kishan ; Mohan, Chilukuri K ; Raina, Ramesh. / SMAlign : Alignment of DNA sequences with gap constraints. 4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012. 2012. pp. 43-50
@inproceedings{93ca3f077b9d41fd8b06bc6f9b836fa7,
title = "SMAlign: Alignment of DNA sequences with gap constraints",
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.",
keywords = "Branch and bound, Combinatorial optimization, Dynamic programming, Gap constraints, Structured motif alignment",
author = "Faisal Alobaid and Kishan Mehrotra and Mohan, {Chilukuri K} and Ramesh Raina",
year = "2012",
language = "English (US)",
isbn = "9781618397461",
pages = "43--50",
booktitle = "4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012",

}

TY - GEN

T1 - SMAlign

T2 - Alignment of DNA sequences with gap constraints

AU - Alobaid, Faisal

AU - Mehrotra, Kishan

AU - Mohan, Chilukuri K

AU - Raina, Ramesh

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Branch and bound

KW - Combinatorial optimization

KW - Dynamic programming

KW - Gap constraints

KW - Structured motif alignment

UR - http://www.scopus.com/inward/record.url?scp=84883643455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883643455&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84883643455

SN - 9781618397461

SP - 43

EP - 50

BT - 4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012

ER -