Efficient Pattern Matching in Elastic-Degenerate Texts

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

doi:10.1007/978-3-319-53733-7_9

Efficient Pattern Matching in Elastic-Degenerate Texts

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

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

28 Citations (Scopus)

261 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 language	English
Title of host publication	Language and Automata Theory and Applications
Subtitle of host publication	11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
Editors	Frank Drewes, Carlos Martín-Vide, Bianca Truthe
Place of Publication	Cham
Publisher	Springer International Publishing Switzerland
Pages	131-142
Number of pages	12
ISBN (Print)	9783319537337
DOIs	https://doi.org/10.1007/978-3-319-53733-7_9
Publication status	E-pub ahead of print - 16 Feb 2017

Access to Document

10.1007/978-3-319-53733-7_9

Efficient Pattern Matching_ILIOPOULOS_Publishedonline16February2017_GREEN AAM
This is the peer-reviewed, accepted manuscript of a paper published as "Efficient Pattern Matching in Elastic-Degenerate Texts", in: Drewes F., Martín-Vide C., Truthe B. (eds) Language and Automata Theory and Applications. LATA 2017. Lecture Notes in Computer Science, vol 10168. Springer, Cham. The final publication is available at link.springer.com, DOI (https://doi.org/10.1007/978-3-319-53733-7_9)
Accepted author manuscript, 412 KBLicence: Other

https://arxiv.org/abs/1610.08111

Cite this

Iliopoulos, C. S., Kundu, R., & Pissis, S. P. (2017). Efficient Pattern Matching in Elastic-Degenerate Texts. In F. Drewes, C. Martín-Vide, & B. Truthe (Eds.), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings (pp. 131-142). Springer International Publishing Switzerland. Advance online publication. https://doi.org/10.1007/978-3-319-53733-7_9

Iliopoulos, Costas S. ; Kundu, Ritu ; Pissis, Solon P. / Efficient Pattern Matching in Elastic-Degenerate Texts. Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. editor / Frank Drewes ; Carlos Martín-Vide ; Bianca Truthe. Cham : Springer International Publishing Switzerland, 2017. pp. 131-142

@inbook{3ee77cdcfc4d40c9b458238392eca1f4,

title = "Efficient Pattern Matching in Elastic-Degenerate Texts",

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).",

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

year = "2017",

month = feb,

day = "16",

doi = "10.1007/978-3-319-53733-7_9",

language = "English",

isbn = "9783319537337",

pages = "131--142",

editor = "Frank Drewes and Carlos Mart{\'i}n-Vide and Bianca Truthe",

booktitle = "Language and Automata Theory and Applications",

publisher = "Springer International Publishing Switzerland",

}

Iliopoulos, CS , Kundu, R & Pissis, SP 2017, Efficient Pattern Matching in Elastic-Degenerate Texts. in F Drewes, C Martín-Vide & B Truthe (eds), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Springer International Publishing Switzerland, Cham, pp. 131-142. https://doi.org/10.1007/978-3-319-53733-7_9

Efficient Pattern Matching in Elastic-Degenerate Texts. / Iliopoulos, Costas S.; Kundu, Ritu ; Pissis, Solon P.
Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. ed. / Frank Drewes; Carlos Martín-Vide; Bianca Truthe. Cham: Springer International Publishing Switzerland, 2017. p. 131-142.

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

TY - CHAP

T1 - Efficient Pattern Matching in Elastic-Degenerate Texts

AU - Iliopoulos, Costas S.

AU - Kundu, Ritu

AU - Pissis, Solon P.

PY - 2017/2/16

Y1 - 2017/2/16

N2 - 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).

AB - 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).

U2 - 10.1007/978-3-319-53733-7_9

DO - 10.1007/978-3-319-53733-7_9

M3 - Other chapter contribution

SN - 9783319537337

SP - 131

EP - 142

BT - Language and Automata Theory and Applications

A2 - Drewes, Frank

A2 - Martín-Vide, Carlos

A2 - Truthe, Bianca

PB - Springer International Publishing Switzerland

CY - Cham

ER -

Iliopoulos CS , Kundu R , Pissis SP. Efficient Pattern Matching in Elastic-Degenerate Texts. In Drewes F, Martín-Vide C, Truthe B, editors, Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Cham: Springer International Publishing Switzerland. 2017. p. 131-142 Epub 2017 Feb 16. doi: 10.1007/978-3-319-53733-7_9

Efficient Pattern Matching in Elastic-Degenerate Texts

Abstract

Access to Document

Fingerprint

Cite this