Daykin, JWGroult, RGuesnet, YLecroq, TLefebvre, ALeonard, MMouchard, LPrieur-Gaston, EWatson, Bruce A2020-03-242020-03-242019-03Daykin, J.W. (et.al). 2019. Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform. Information Processing Letters, (v)147, pp 82-87.0020-01901872-6119https://doi.org/10.1016/j.ipl.2019.03.003https://www.sciencedirect.com/science/article/pii/S0020019019300535http://hdl.handle.net/10204/11385Copyright: 2019 Under a Creative Commons license. This is the fulltext version of the work.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.enAlgorithmsBurrows-Wheeler transformDegeneratePattern matchingStringArticleDaykin, 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/11385Daykin, 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/11385Daykin 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.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 -