@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 Chilukuri Mohan and Ramesh Raina",
year = "2012",
language = "English (US)",
isbn = "9781618397461",
series = "4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012",
pages = "43--50",
booktitle = "4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012",
note = "4th International Conference on Bioinformatics and Computational Biology 2012, BICoB 2012 ; Conference date: 12-03-2012 Through 14-03-2012",
}