Fast detection of specific fragments against a set of sequences

DOI10.1007/978-3-031-33264-7_5MaRDI QIDQ6067326zbMATH OpenFDO

Authors Marie-Pierre Béal, Maxime Crochemore

Publication date 16 November 2023

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.03451

zbMATH Keywords

minimal forbidden wordspecific wordSuffix Automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We design alignment-free techniques for comparing a sequence or word, called a target, against a set of words, called a reference. A target-specific factor of a target $T$ against a reference $R$ is a factor $w$ of a word in $T$ which is not a factor of a word of $R$ and such that any proper factor of $w$ is a factor of a word of $R$. 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 $TcupR$. The second result consists of 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.

Cites work

• Absent words in a sliding window with applications
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Alignment-free sequence comparison using absent words
• Automata and forbidden words
• Can formal languages help pangenomics to represent and analyze multiple genomes?
• Complete inverted files for efficient text retrieval and analysis
• Forbidden words in symbolic dynamics
• scientific article; zbMATH DE number 1344899 (Why is no real title available?)
• scientific article; zbMATH DE number 1998341 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• Suffix Arrays: A New Method for On-Line String Searches
• Transducers and repetitions
• Using minimal absent words to build phylogeny

Cited in

(2)

• Linear-time computation of generalized minimal absent words for multiple strings
• Efficient computation of discriminative absent words for string collections

This page was built for publication: Fast detection of specific fragments against a set of sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6067326)