Global Sequence Alignment with a Bounded Number of Gaps

Carl Barton; Tomas Flouri; Costas S. Iliopoulos; Solon P. Pissis

doi:10.1002/9781119078845.ch5

Global Sequence Alignment with a Bounded Number of Gaps

Carl Barton, Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

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 language	English
Title of host publication	Pattern Recognition in Computational Molecular Biology: Techniques and Approaches
Editors	Mourad Elloumi, Costas S. Iliopoulos, Jason T. L. Wang, Albert Y. Zomaya
Publisher	Wiley
Pages	83-96
Number of pages	14
ISBN (Print)	9781118893685
DOIs	https://doi.org/10.1002/9781119078845.ch5
Publication status	Published - 19 Nov 2015

Access to Document

10.1002/9781119078845.ch5

Cite this

@inbook{a69147c1fb444154ba0044dd5403de56,

title = "Global Sequence Alignment with a Bounded Number of Gaps",

abstract = "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.",

author = "Carl Barton and Tomas Flouri and Iliopoulos, {Costas S.} and Pissis, {Solon P.}",

year = "2015",

month = nov,

day = "19",

doi = "10.1002/9781119078845.ch5",

language = "English",

isbn = "9781118893685",

pages = "83--96",

editor = "Mourad Elloumi and Iliopoulos, {Costas S.} and Wang, {Jason T. L.} and Zomaya, {Albert Y.}",

booktitle = "Pattern Recognition in Computational Molecular Biology: Techniques and Approaches",

publisher = "Wiley",

}

Global Sequence Alignment with a Bounded Number of Gaps. / Barton, Carl; Flouri, Tomas; Iliopoulos, Costas S. et al.
Pattern Recognition in Computational Molecular Biology: Techniques and Approaches. ed. / Mourad Elloumi; Costas S. Iliopoulos; Jason T. L. Wang; Albert Y. Zomaya. Wiley, 2015. p. 83-96.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Global Sequence Alignment with a Bounded Number of Gaps

AU - Barton, Carl

AU - Flouri, Tomas

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2015/11/19

Y1 - 2015/11/19

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

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

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

U2 - 10.1002/9781119078845.ch5

DO - 10.1002/9781119078845.ch5

M3 - Chapter

SN - 9781118893685

SP - 83

EP - 96

BT - Pattern Recognition in Computational Molecular Biology: Techniques and Approaches

A2 - Elloumi, Mourad

A2 - Iliopoulos, Costas S.

A2 - Wang, Jason T. L.

A2 - Zomaya, Albert Y.

PB - Wiley

ER -

Global Sequence Alignment with a Bounded Number of Gaps

Abstract

Access to Document

Other files and links

Fingerprint

Cite this