Efficient pattern matching in elastic-degenerate strings

Costas S. Iliopoulos; Ritu Kundu; Solon P. Pissis

doi:10.1016/j.ic.2020.104616

Efficient pattern matching in elastic-degenerate strings

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k−1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.

Original language	English
Article number	104616
Journal	INFORMATION AND COMPUTATION
DOIs	https://doi.org/10.1016/j.ic.2020.104616
Publication status	Accepted/In press - 1 Jan 2020

Keywords

Algorithms on strings
Degenerate strings
Elastic-degenerate strings
Gapped strings
Indeterminate strings

Access to Document

10.1016/j.ic.2020.104616

https://arxiv.org/pdf/1610.08111.pdf

Cite this

@article{dab86260bd694c3ebbae58334cccc9c6,

title = "Efficient pattern matching in elastic-degenerate strings",

abstract = "Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k−1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.",

keywords = "Algorithms on strings, Degenerate strings, Elastic-degenerate strings, Gapped strings, Indeterminate strings",

author = "Iliopoulos, {Costas S.} and Ritu Kundu and Pissis, {Solon P.}",

year = "2020",

month = jan,

day = "1",

doi = "10.1016/j.ic.2020.104616",

language = "English",

journal = "INFORMATION AND COMPUTATION",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Efficient pattern matching in elastic-degenerate strings

AU - Iliopoulos, Costas S.

AU - Kundu, Ritu

AU - Pissis, Solon P.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k−1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.

AB - Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k−1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.

KW - Algorithms on strings

KW - Degenerate strings

KW - Elastic-degenerate strings

KW - Gapped strings

KW - Indeterminate strings

UR - http://www.scopus.com/inward/record.url?scp=85089138933&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104616

DO - 10.1016/j.ic.2020.104616

M3 - Article

AN - SCOPUS:85089138933

SN - 0890-5401

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

M1 - 104616

ER -

Efficient pattern matching in elastic-degenerate strings

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this