Approximate string-matching with a single gap for sequence alignment

Tomáš Flouri; Kimon Frousios; Costas S. Iliopoulos; Kunsoo Park; Solon P. Pissis; German Tischler

doi:10.1145/2147805.2147879

Approximate string-matching with a single gap for sequence alignment

Tomáš Flouri^*
, Kimon Frousios
, Costas S. Iliopoulos
, Kunsoo Park
, Solon P. Pissis
, German Tischler

^*Corresponding author for this work

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

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	2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011
Pages	490-492
Number of pages	3
DOIs	https://doi.org/10.1145/2147805.2147879
Publication status	Published - 1 Dec 2011
Externally published	Yes
Event	2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011 - Chicago, IL, United States Duration: 1 Aug 2011 → 3 Aug 2011

Publication series

Name	2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011

Conference

Conference	2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011
Country/Territory	United States
City	Chicago, IL
Period	1/08/11 → 3/08/11

Access to Document

10.1145/2147805.2147879

Persistent URL (handle)

Persistent link

Cite this

Flouri, T., Frousios, K., Iliopoulos, C. S., Park, K., Pissis, S. P., & Tischler, G. (2011). Approximate string-matching with a single gap for sequence alignment. In 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011 (pp. 490-492). (2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011). https://doi.org/10.1145/2147805.2147879

@inproceedings{7384de2e1d864c15a895ed27b5ebbff3,

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 = "Tom{\'a}{\v s} Flouri and Kimon Frousios and Iliopoulos, \{Costas S.\} and Kunsoo Park and Pissis, \{Solon P.\} and German Tischler",

year = "2011",

month = dec,

day = "1",

doi = "10.1145/2147805.2147879",

language = "English",

isbn = "9781450307963",

series = "2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011",

pages = "490--492",

booktitle = "2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011",

note = "2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011 ; Conference date: 01-08-2011 Through 03-08-2011",

}

Flouri, T, Frousios, K, Iliopoulos, CS, Park, K, Pissis, SP & Tischler, G 2011, Approximate string-matching with a single gap for sequence alignment. in 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011. 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011, pp. 490-492, 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011, Chicago, IL, United States, 1/08/11. https://doi.org/10.1145/2147805.2147879

Approximate string-matching with a single gap for sequence alignment. / Flouri, Tomáš; Frousios, Kimon; Iliopoulos, Costas S. et al.
2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011. 2011. p. 490-492 (2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011).

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

TY - GEN

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

AU - Flouri, Tomáš

AU - Frousios, Kimon

AU - Iliopoulos, Costas S.

AU - Park, Kunsoo

AU - Pissis, Solon P.

AU - Tischler, German

PY - 2011/12/1

Y1 - 2011/12/1

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.

UR - https://www.scopus.com/pages/publications/84858974166

UR - https://www.scopus.com/pages/publications/84858974166#tab=citedBy

U2 - 10.1145/2147805.2147879

DO - 10.1145/2147805.2147879

M3 - Conference contribution

AN - SCOPUS:84858974166

SN - 9781450307963

T3 - 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011

SP - 490

EP - 492

BT - 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011

T2 - 2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011

Y2 - 1 August 2011 through 3 August 2011

ER -

Approximate string-matching with a single gap for sequence alignment

Abstract

Publication series

Conference

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this