dc.contributor.author |
Daykin, JW
|
|
dc.contributor.author |
Groult, R
|
|
dc.contributor.author |
Guesnet, Y
|
|
dc.contributor.author |
Lecroq, T
|
|
dc.contributor.author |
Lefebvre, A
|
|
dc.contributor.author |
Leonard, M
|
|
dc.contributor.author |
Mouchard, L
|
|
dc.contributor.author |
Prieur-Gaston, E
|
|
dc.contributor.author |
Watson, Bruce A
|
|
dc.date.accessioned |
2020-03-24T09:10:07Z |
|
dc.date.available |
2020-03-24T09:10:07Z |
|
dc.date.issued |
2019-03 |
|
dc.identifier.citation |
Daykin, J.W. (et.al). 2019. Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform. Information Processing Letters, (v)147, pp 82-87. |
en_US |
dc.identifier.issn |
0020-0190 |
|
dc.identifier.issn |
1872-6119 |
|
dc.identifier.uri |
https://doi.org/10.1016/j.ipl.2019.03.003
|
|
dc.identifier.uri |
https://www.sciencedirect.com/science/article/pii/S0020019019300535
|
|
dc.identifier.uri |
http://hdl.handle.net/10204/11385
|
|
dc.description |
Copyright: 2019 Under a Creative Commons license. This is the fulltext version of the work. |
en_US |
dc.description.abstract |
A degenerate or indeterminate string on an alphabet is a sequence of non-empty subsets of . Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O(mn) time on a constant size alphabet . Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O(qm2) for counting the number of occurrences and O(qm2 + occ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice. |
en_US |
dc.language.iso |
en |
en_US |
dc.publisher |
Elsevier |
en_US |
dc.relation.ispartofseries |
Worklist;23380 |
|
dc.subject |
Algorithms |
en_US |
dc.subject |
Burrows-Wheeler transform |
en_US |
dc.subject |
Degenerate |
en_US |
dc.subject |
Pattern matching |
en_US |
dc.subject |
String |
en_US |
dc.title |
Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform |
en_US |
dc.type |
Article |
en_US |
dc.identifier.apacitation |
Daykin, J., Groult, R., Guesnet, Y., Lecroq, T., Lefebvre, A., Leonard, M., ... Watson, B. A. (2019). Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform. http://hdl.handle.net/10204/11385 |
en_ZA |
dc.identifier.chicagocitation |
Daykin, JW, R Groult, Y Guesnet, T Lecroq, A Lefebvre, M Leonard, L Mouchard, E Prieur-Gaston, and Bruce A Watson "Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform." (2019) http://hdl.handle.net/10204/11385 |
en_ZA |
dc.identifier.vancouvercitation |
Daykin J, Groult R, Guesnet Y, Lecroq T, Lefebvre A, Leonard M, et al. Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform. 2019; http://hdl.handle.net/10204/11385. |
en_ZA |
dc.identifier.ris |
TY - Article
AU - Daykin, JW
AU - Groult, R
AU - Guesnet, Y
AU - Lecroq, T
AU - Lefebvre, A
AU - Leonard, M
AU - Mouchard, L
AU - Prieur-Gaston, E
AU - Watson, Bruce A
AB - A degenerate or indeterminate string on an alphabet is a sequence of non-empty subsets of . Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O(mn) time on a constant size alphabet . Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O(qm2) for counting the number of occurrences and O(qm2 + occ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice.
DA - 2019-03
DB - ResearchSpace
DP - CSIR
KW - Algorithms
KW - Burrows-Wheeler transform
KW - Degenerate
KW - Pattern matching
KW - String
LK - https://researchspace.csir.co.za
PY - 2019
SM - 0020-0190
SM - 1872-6119
T1 - Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform
TI - Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform
UR - http://hdl.handle.net/10204/11385
ER -
|
en_ZA |