Linear algorithm for conservative degenerate pattern matching

Maxime Crochemore; Costas S. Iliopoulos; Ritu Kundu; Manal Mohamed; Fatima Vayani

doi:10.1016/j.engappai.2016.01.009

Linear algorithm for conservative degenerate pattern matching

Maxime Crochemore, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed^*, Fatima Vayani

^*Corresponding author for this work

Department of Informatics

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

8 Citations (Scopus)

Abstract

A degenerate symbol x˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k non-solid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.

Original language	English
Pages (from-to)	109-114
Number of pages	6
Journal	ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
Volume	51
Early online date	28 Jan 2016
DOIs	https://doi.org/10.1016/j.engappai.2016.01.009
Publication status	Published - May 2016

Keywords

Algorithm
Degenerate string
Pattern matching

Access to Document

10.1016/j.engappai.2016.01.009

Cite this

@article{0d1a4ab3f4fa4db5960bb0cbb1f7868f,

title = "Linear algorithm for conservative degenerate pattern matching",

abstract = "A degenerate symbol x˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k non-solid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.",

keywords = "Algorithm, Degenerate string, Pattern matching",

author = "Maxime Crochemore and Iliopoulos, {Costas S.} and Ritu Kundu and Manal Mohamed and Fatima Vayani",

year = "2016",

month = may,

doi = "10.1016/j.engappai.2016.01.009",

language = "English",

volume = "51",

pages = "109--114",

journal = "ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE",

issn = "0952-1976",

publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Linear algorithm for conservative degenerate pattern matching

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Kundu, Ritu

AU - Mohamed, Manal

AU - Vayani, Fatima

PY - 2016/5

Y1 - 2016/5

N2 - A degenerate symbol x˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k non-solid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.

AB - A degenerate symbol x˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k non-solid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.

KW - Algorithm

KW - Degenerate string

KW - Pattern matching

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

U2 - 10.1016/j.engappai.2016.01.009

DO - 10.1016/j.engappai.2016.01.009

M3 - Article

AN - SCOPUS:84961599127

SN - 0952-1976

VL - 51

SP - 109

EP - 114

JO - ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

JF - ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

ER -

Linear algorithm for conservative degenerate pattern matching

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Succinct and compressed data structures for string indexing and processing

Cite this

Linear algorithm for conservative degenerate pattern matching

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Succinct and compressed data structures for string indexing and processing

Cite this