GENERAL ENQUIRIES: Tel: + 27 12 841 2911 | Email: callcentre@csir.co.za

Show simple item record

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


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ResearchSpace


Advanced Search

Browse

My Account