GENERAL ENQUIRIES: Tel: + 27 12 841 2911 | Email:

Show simple item record Daykin, JW Groult, R Guesnet, Y Lecroq, T Lefebvre, A Leonard, M Mouchard, L Prieur-Gaston, E Watson, Bruce A 2020-03-24T09:10:07Z 2020-03-24T09:10:07Z 2019-03
dc.identifier.citation Daykin, J.W. ( 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.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

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ResearchSpace

Advanced Search


My Account