Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform

Authors Organisations
  • Jacqueline Daykin(Author)
    King's College London
    Normandy University
  • Richard Groult(Author)
    University of Picardie Jules Verne
    Normandy University
  • Yannick Guesnet(Author)
    Normandy University
  • Thierry Lecroq(Author)
    Normandy University
  • Arnaud Lefebvre(Author)
    Normandy University
  • Martine Léonard(Author)
    Normandy University
  • Laurent Mouchard(Author)
    Normandy University
  • Élise Prieur-Gaston(Author)
    Normandy University
  • Bruce Watson(Author)
    Stellenbosch University
    Centre for Artificial Intelligence Research
Type Working paper
Original languageEnglish
Publication statusPublished - 03 Aug 2017
Permanent link
View graph of relations
Citation formats


A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n, we present a new method based on the Burrows--Wheeler transform 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 complexity time is O(qm2). Experimental results show that our method performs well in practice