Minimal absent words in a sliding window and applications to on-line pattern matching

Maxime Crochemore, Alice Héliou*, Gregory Kucherov, Laurent Mouchard, Solon P. Pissis, Yann Ramusat

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

An absent (or forbidden) word of a word y is a word that does not occur in y. It is then called minimal if all its proper factors occur in y. There exist linear-time and linear-space algorithms for computing all minimal absent words of y (Crochemore et al. in Inf Process Lett 67:111–117, 1998; Belazzougui et al. in ESA 8125:133–144, 2013; Barton et al. in BMC Bioinform 15:388, 2014). Minimal absent words are used for data compression (Crochemore et al. in Proc IEEE 88:1756–1768, 2000, Ota and Morita in Theoret Comput Sci 526:108–119, 2014) and for alignment-free sequence comparison by utilizing a metric based on minimal absent words (Chairungsee and Crochemore in Theoret Comput Sci 450:109–116, 2012). They are also used in molecular biology; for instance, three minimal absent words of the human genome were found to play a functional role in a coding region in Ebola virus genomes (Silva et al. in Bioinformatics 31:2421–2425, 2015). In this article we introduce a new application of minimal absent words for on-line pattern matching. Specifically, we present an algorithm that, given a pattern x and a text y, computes the distance between x and every window of size |x| on y. The running time is O(σ|y|), where σ is the size of the alphabet. Along the way, we show an O(σ|y|)-time and O(σ|x|)-space algorithm to compute the minimal absent words of every window of size |x| on y, together with some new combinatorial insight on minimal absent words.

Original languageEnglish
Title of host publicationFundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings
EditorsMarc Zeitoun, Ralf Klasing
PublisherSpringer Verlag
Pages164-176
Number of pages13
ISBN (Print)9783662557501
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event21st International Symposium on Fundamentals of Computation Theory, FCT 2017 - Bordeaux, France
Duration: 11 Sep 201713 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10472 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Symposium on Fundamentals of Computation Theory, FCT 2017
CountryFrance
CityBordeaux
Period11/09/1713/09/17

Fingerprint

Dive into the research topics of 'Minimal absent words in a sliding window and applications to on-line pattern matching'. Together they form a unique fingerprint.

Cite this