Global Sequence Alignment with a Bounded Number of Gaps

Carl Barton*, Tomáš Flouri, Costas S. Iliopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review


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.

Original languageEnglish
Title of host publicationPattern Recognition in Computational Molecular Biology
Subtitle of host publicationTechniques and Approaches
Number of pages14
ISBN (Electronic)9781119078845
ISBN (Print)9781118893685
Publication statusPublished - 28 Dec 2015
Externally publishedYes


  • Affine gap penalty scores
  • Dynamic programming matrix
  • GapMis
  • GapsMis
  • Pairwise global sequence alignment
  • Scoring matrices


Dive into the research topics of 'Global Sequence Alignment with a Bounded Number of Gaps'. Together they form a unique fingerprint.

Cite this