Single and multiple consecutive permutation motif search

DOI10.1007/978-3-642-45030-3_7zbMATH Open1329.68307arXiv1301.4952OpenAlexW2103156536MaRDI QIDQ2872072FDOQ2872072

Authors: Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot, Stéphane Vialette 

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: Let $t$ be a permutation (that shall play the role of the {em text}) on $[n]$ and a pattern $p$ be a sequence of $m$ distinct integer(s) of $[n]$, $mleqn$. The pattern $p$ occurs in $t$ in position $i$ if and only if $p_1\mathrm{...}{p}_m$ is order-isomorphic to $t_i\mathrm{...}{t}_{i+m-1}$, that is, for all $1leqk<ellleqm$, $p_k>p_{e}ll$ if and only if $t_{i+k-1}>t_{i+ell-1}$. Searching for a pattern $p$ in a text $t$ consists in identifying all occurrences of $p$ in $t$. We first present a forward automaton which allows us to search for $p$ in $t$ in $O(m^{2}loglogm+n)$ time. We then introduce a Morris-Pratt automaton representation of the forward automaton which allows us to reduce this complexity to $O(mloglogm+n)$ at the price of an additional amortized constant term by integer of the text. Both automata occupy $O(m)$ space. We then extend the problem to search for a set of patterns and exhibit a specific Aho-Corasick like algorithm. Next we present a sub-linear average case search algorithm running in $O(fracmlogmloglogm+fracnlogmmloglogm)$ time, that we eventually prove to be optimal on average.

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

Recommendations

• A linear time algorithm for consecutive permutation pattern matching
• Permuted Pattern Matching on Multi-track Strings
• scientific article; zbMATH DE number 2081004
• Finding small patterns in permutations in linear time
• Fast multiple order-preserving matching algorithms

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cited In (13)

• Order-preserving pattern matching indeterminate strings
• Order-preserving pattern matching indeterminate strings
• The order-preserving pattern matching problem in practice
• String Periods in the Order-Preserving Model
• Order-preserving indexing
• Order-preserving pattern matching with \(k\) mismatches
• A linear time algorithm for consecutive permutation pattern matching
• A technique to find multiple motif occurrences in a biomolecular sequence
• A filtration method for order-preserving matching
• Efficient algorithms for the order preserving pattern matching problem
• An encoding for order-preserving matching
• String periods in the order-preserving model
• Improved algorithms for the boxed-mesh permutation pattern matching problem

This page was built for publication: Single and multiple consecutive permutation motif search

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