King's College London

Research portal

Global Sequence Alignment with a Bounded Number of Gaps

Research output: Chapter in Book/Report/Conference proceedingChapter

Original languageEnglish
Title of host publicationPattern Recognition in Computational Molecular Biology: Techniques and Approaches
EditorsMourad Elloumi, Costas S. Iliopoulos, Jason T. L. Wang, Albert Y. Zomaya
Number of pages14
ISBN (Print)9781118893685
Published19 Nov 2015

King's Authors


Alignments are a commonly used technique to compare strings and are based on notions of distance or of similarity between strings; for example, similarities among biological sequences. Alignments are often computed by dynamic programming. This chapter presents GapMis and GapsMis, two algorithms for pairwise global sequence alignment with a variable, but bounded, number of gaps. They compute different versions of the standard dynamic programming matrix. GapMis requires Θ(mk) time and space, where m is the length of the shortest sequence and k is the maximum allowed edit distance between the two sequences. GapsMis requires Θ(mk Iscr) time and Θ(mk) space, where Iscr is the maximum allowed number of gaps inserted in the alignment. These algorithms can be directly applied with an alignment score scheme such as scoring matrices and affine gap penalty scores.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454