2026-07-22T11:41:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23813 2026-02-09T06:17:20Z ddc:004 open_access

Specific Patterns Against Reference Sequences Béal, Marie-Pierre Crochemore, Maxime Specific pattern Minimal absent word Minimal forbidden word Directed Acyclic Word Graph (DAWG) Suffix automaton We design alignment-free techniques for comparing a set of sequences or just a word, called a target, against another set of words, called a reference. This is done with the detection of factor patterns that distinguish the target from the reference. A target-specific factor of a target T against a reference R is then a factor w of a word in T that is not a factor of a word in R but whose proper factors of w are factors of a word in R. The strategy is based on the notion of minimal absent/forbidden words. We first address the computation of the set of target-specific factors of a target T against a reference R, where T and R are finite sets of sequences. The result is the construction of an automaton accepting the set of all considered target-specific factors. The construction algorithm runs in linear time according to the size of T ∪ R. The second result is the design of an algorithm to compute all the occurrences in a single sequence T of its target-specific factors against a reference R. The algorithm runs in real-time on the target sequence, independently of the number of occurrences of target-specific factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marie-Pierre Béal and Maxime Crochemore 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.14 urn:nbn:de:0030-drops-238130 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.14 eng https://creativecommons.org/licenses/by/4.0/legalcode