Efficient pattern matching in elastic-degenerate texts

Costas S. Iliopoulos, Ritu Kundu*, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 - 11th International Conference, LATA 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
PublisherSpringer Verlag
Pages131-142
Number of pages12
ISBN (Print)9783319537320
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden
Duration: 6 Mar 20179 Mar 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Language and Automata Theory and Applications, LATA 2017
Country/TerritorySweden
City Umea
Period6/03/179/03/17

Keywords

  • Degenerate strings
  • Elastic-degenerate strings
  • Gapped strings
  • Indeterminate strings
  • String processing algorithms

Fingerprint

Dive into the research topics of 'Efficient pattern matching in elastic-degenerate texts'. Together they form a unique fingerprint.

Cite this