Approximate string-matching with a single gap for sequence alignment

Tomas Flouri; Kunsoo Park; Kimon Frousios; Solon P. Pissis; Costas S. Iliopoulos; German Tischler

doi:10.1145/2147805.2147879

Approximate string-matching with a single gap for sequence alignment

Tomas Flouri, Kunsoo Park, Kimon Frousios, Solon P. Pissis, Costas S. Iliopoulos, German Tischler

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

6 Citations (Scopus)

Abstract

This paper deals with the approximate string-matching problem with Hamming distance and a single gap for sequence alignment. We consider an extension of the approximate string-matching problem with Hamming distance, by also allowing the existence of a single gap, either in the text, or in the pattern. This problem is strongly and directly motivated by the next-generation re-sequencing procedure. We present a general algorithm that requires O (nm) time, where n is the length of the text and m is the length of the pattern, but this can be reduced to O (mβ) time, if the maximum length β of the gap is given.

Original language	English
Title of host publication	BCB '11 Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine
Publisher	ACM
Pages	490-492
Number of pages	3
ISBN (Print)	978-1-4503-0796-3
DOIs	https://doi.org/10.1145/2147805.2147879
Publication status	Published - 2011

Access to Document

10.1145/2147805.2147879

Cite this

@inbook{afd91d4a8ed84e77b72e8d617482758d,

title = "Approximate string-matching with a single gap for sequence alignment",

abstract = "This paper deals with the approximate string-matching problem with Hamming distance and a single gap for sequence alignment. We consider an extension of the approximate string-matching problem with Hamming distance, by also allowing the existence of a single gap, either in the text, or in the pattern. This problem is strongly and directly motivated by the next-generation re-sequencing procedure. We present a general algorithm that requires O (nm) time, where n is the length of the text and m is the length of the pattern, but this can be reduced to O (mβ) time, if the maximum length β of the gap is given.",

author = "Tomas Flouri and Kunsoo Park and Kimon Frousios and Pissis, {Solon P.} and Iliopoulos, {Costas S.} and German Tischler",

year = "2011",

doi = "10.1145/2147805.2147879",

language = "English",

isbn = "978-1-4503-0796-3",

pages = "490--492",

booktitle = "BCB '11 Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine",

publisher = "ACM",

}

TY - CHAP

T1 - Approximate string-matching with a single gap for sequence alignment

AU - Flouri, Tomas

AU - Park, Kunsoo

AU - Frousios, Kimon

AU - Pissis, Solon P.

AU - Iliopoulos, Costas S.

AU - Tischler, German

PY - 2011

Y1 - 2011

N2 - This paper deals with the approximate string-matching problem with Hamming distance and a single gap for sequence alignment. We consider an extension of the approximate string-matching problem with Hamming distance, by also allowing the existence of a single gap, either in the text, or in the pattern. This problem is strongly and directly motivated by the next-generation re-sequencing procedure. We present a general algorithm that requires O (nm) time, where n is the length of the text and m is the length of the pattern, but this can be reduced to O (mβ) time, if the maximum length β of the gap is given.

AB - This paper deals with the approximate string-matching problem with Hamming distance and a single gap for sequence alignment. We consider an extension of the approximate string-matching problem with Hamming distance, by also allowing the existence of a single gap, either in the text, or in the pattern. This problem is strongly and directly motivated by the next-generation re-sequencing procedure. We present a general algorithm that requires O (nm) time, where n is the length of the text and m is the length of the pattern, but this can be reduced to O (mβ) time, if the maximum length β of the gap is given.

U2 - 10.1145/2147805.2147879

DO - 10.1145/2147805.2147879

M3 - Conference paper

SN - 978-1-4503-0796-3

SP - 490

EP - 492

BT - BCB '11 Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine

PB - ACM

ER -

Approximate string-matching with a single gap for sequence alignment

Abstract

Access to Document

Fingerprint

Cite this