Efficient Pattern Matching in Elastic-Degenerate Texts

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

26 Citations (Scopus)
199 Downloads (Pure)

Abstract

Motivated by applications in bioinformatics, in what follows, we extend the notion of gapped strings to elastic-degenerate strings. An elastic-degenerate string can been seen as an ordered collection of solid (standard) strings interleaved by elastic-degenerate symbols; each such symbol corresponds to a set of two or more variable-length solid strings. In this article, we present an algorithm for solving the pattern matching problem with a solid pattern and an elastic-degenerate text running in O(N+αγmn) time; where m is the length of the pattern; n and N are the length and total size of the elastic-degenerate text, respectively; α and γ are parameters, respectively representing the maximum number of strings in any elastic-degenerate symbol of the text and the maximum number of elastic-degenerate symbols spanned by any occurrence of the pattern in the text. The space used by the proposed algorithm is O(N).
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Pages131-142
Number of pages12
ISBN (Print)9783319537337
DOIs
Publication statusE-pub ahead of print - 16 Feb 2017

Fingerprint

Dive into the research topics of 'Efficient Pattern Matching in Elastic-Degenerate Texts'. Together they form a unique fingerprint.

Cite this