<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Computing matching statistics on Wheeler DFAs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Part of book or chapter of book , Conference object 01 Mar 2023Embargo end date: 01 Jan 2023 Italy Publisher:IEEEJournal:2023 Data Compression Conference (DCC)Funded by:NSERC | unidentified, EC | REGINDEX, NSF | IIBR Informatics: An Effi... +2 projects

Authors: Conte A.; Cotumaccio N.; Gagie T.; Manzini G.; Prezza N.; Sciortino M.;

doi: 10.1109/dcc55655.2023.00023 , 10.48550/arxiv.2301.05338

pmid: 38832320

pmc: PMC11146637

arXiv: http://arxiv.org/abs/2301.05338

handle: 10447/620076 , 10278/5024922 , 11568/1187767

Computing matching statistics on Wheeler DFAs

- Summary
- Subjects
- Metrics

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.

Country

Italy

Related Organizations

View all View all

Keywords

FOS: Computer and information sciences, Burrows Wheeler transform, pattern matching, LCP array, Matching statistics, Computer Science - Data Structures and Algorithms, Burrows Wheeler transform; FM index; LCP array; Matching statistics; pattern matching; Wheeler graphs, Data Structures and Algorithms (cs.DS), FM index, Wheeler graphs

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average