Skip to main content
Passa alla visualizzazione normale.

MARINELLA SCIORTINO

Computing matching statistics on Wheeler DFAs

  • Authors: Conte, A; Cotumaccio, N; Gagie, T; Manzini, G; Prezza, N; Sciortino, M
  • Publication year: 2023
  • Type: Contributo in atti di convegno pubblicato in volume
  • OA Link: http://hdl.handle.net/10447/620076

Abstract

Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPIRE 2010] proposed a time and space efficient algorithm for computing matching statistics which relies on some components of a compressed suffix tree - notably, the longest common prefix (LCP) array. In this paper, we show how their algorithm can be generalized from strings to Wheeler deterministic finite automata. Most importantly, we introduce a notion of LCP array for Wheeler automata, thus establishing a first clear step towards extending (compressed) suffix tree functionalities to labeled graphs.