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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publication2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011
Pages490-492
Number of pages3
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011 - Chicago, IL, United States
Duration: 1 Aug 20113 Aug 2011

Publication series

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

Conference

Conference2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011
CountryUnited States
CityChicago, IL
Period1/08/113/08/11

Fingerprint

Dive into the research topics of 'Approximate string-matching with a single gap for sequence alignment'. Together they form a unique fingerprint.

Cite this