Search

Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to $\tau$ bits, performs $q=O(\tau)$ substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length $n$ over an integer alphabet of size $\sigma$ with $rle$ runs can be reconstructed with $q=O(rle (\sigma + \log \frac{n}{rle}))$ substring queries in linear time and space. We then present an algorithm that spends $q \in O(\sigma g\log n)$ substring queries and runs in $O(n(\log n + \log \sigma)+ q)$ time using linear space, where $g$ is the size of a smallest straight-line program generating the string., Comment: Accepted for publication in Theoretical Computer Science

Modelling of chromosomes with permutations has triggered the research of sorting permutations using global rearrangement operations in computational molecular biology. One such rearrangement is transposition which swaps two adjacent substrings. If one of the substrings is restricted to be the prefix of the permutation then that operation is called a prefix transposition. The symmetric prefix transposition distance between two permutations is defined to be the minimum number of prefix transpositions required to transform one into another. Group theory dictates that an upper bound for prefix transposition distance between any pair of permutations in the symmetric group S n is equivalent to the upper bound for sorting any permutation with prefix transpositions. In this paper, we improve the upper bound for sorting permutations with prefix transpositions to n − log 2 ⁡ n .

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an $$O(n\log \sigma ')$$ O ( n log σ ′ ) -time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where $$\sigma '\le d$$ σ ′ ≤ d is the maximum number of distinct characters in every window.

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.

We introduce the concept of a prime band in a string algebra $\Lambda$ and use it to associate to $\Lambda$ its finite bridge quiver. Then we introduce a new technique of `recursive systems' for showing that a graph map between finite dimensional string modules lies in its stable radical. Further we study two classes of non-domestic string algebras in terms of some connectedness properties of its bridge quiver. `Meta-$\bigcup$-cyclic' string algebras constitute the first class that is essentially characterized by the statement that each finite string is a substring of a band. Extending this class we have `meta-torsion-free' string algebras that are characterized by a dichotomy statement for ranks of graph maps between string modules--such maps either have finite rank or are in the stable radical. Their stable ranks can only take values from $\{\omega,\omega+1,\omega+2\}$., Comment: 23 pages, minor changes in Corollary 4.3.3, added funding details for one author

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O ( n ) time by Manacher's algorithm [12] . In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O ( n ) time and space for preprocessing, and answers the length of the LPSs in O ( log ⁡ ( min ⁡ { σ , log ⁡ n } ) ) time after a single character substitution, insertion, or deletion, where σ denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O ( n ) time and space for preprocessing, and answers the length of the LPSs in O ( l + log ⁡ log ⁡ n ) time, after an existing substring in T is replaced by a string of arbitrary length l.

The Closest Substring problem asks whether there exists a consensus string w of given length l such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP -hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE -complete. The problem remains PSPACE -hard even when the input is a deterministic finite automaton and the length l and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP -hard and coNP -hard.

Let P be a collection of d patterns { P 1 , P 2 , … , P d } of total length n characters, which are chosen from an alphabet Σ of size σ. Given a text T (over Σ), the dictionary indexing problem is to create a data structure using which we can report all positions j (called occurrences) where at least one of the patterns P i ∈ P is a match with the same-length substring of T that starts at j. We consider this problem under the following definitions of matching. • Parameterized Matching: The characters of Σ are partitioned into static characters and parameterized characters. Two equal length strings S and S ′ are a parameterized match iff the static characters match exactly, and there exists a one-to-one function which renames the parameterized characters in S to those in S ′ . • Order-Preserving Matching: The alphabet Σ is ordered. Two equal length strings S and S ′ are an order-preserving match iff for any two integers i , j ∈ [ 1 , | S | ] , S [ i ] ≺ S [ j ] ⇔ S ′ [ i ] ≺ S ′ [ j ] , where ≺ denotes the precedence order in Σ. Let e > 0 be an arbitrarily small constant. For parameterized matching, we first present a compact O ( n log ⁡ σ + d log ⁡ n ) -bit index that reports all occ occurrences in O ( | T | ( log ⁡ σ + log σ ⁡ n ) + o c c ) time, and then a succinct n log ⁡ σ + o ( n log ⁡ σ ) + O ( d log ⁡ n ) -bit index that reports all occ occurrences in O ( | T | ( log ⁡ σ + log e ⁡ n log σ ⁡ n ) + o c c ) time. For order-preserving matching, we present indexes of the same sizes, but with slightly increased query time.

Given a string T of length n, a substring u = T [ i . . j ] of T is called a shortest unique substring (SUS) for an interval [ s , t ] if (a) u occurs exactly once in T, (b) u contains the interval [ s , t ] (i.e. i ≤ s ≤ t ≤ j ), and (c) every substring v of T with | v | | u | containing [ s , t ] occurs at least twice in T. Given a query interval [ s , t ] ⊂ [ 1 , n ] , the interval SUS problem is to output all the SUSs for the interval [ s , t ] . In this article, we propose a 4 n + o ( n ) bits data structure answering an interval SUS query in output-sensitive O ( o c c ) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s = t . Here, we propose a ⌈ ( log 2 ⁡ 3 + 1 ) n ⌉ + o ( n ) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.

A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages., To appear in Theoretical Computer Science. arXiv admin note: text overlap with arXiv:1401.6346

Models of sequence evolution typically assume that all sequences are possible. However, restriction enzymes that cut DNA at specific recognition sites provide an example where carrying a recognition site can be lethal. Motivated by this observation, we studied the set of strings over a finite alphabet with taboos, that is, with prohibited substrings. The taboo-set is referred to as $$\mathbb {T}$$ T and any allowed string as a taboo-free string. We consider the so-called Hamming graph $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) , whose vertices are taboo-free strings of length n and whose edges connect two taboo-free strings if their Hamming distance equals one. Any (random) walk on this graph describes the evolution of a DNA sequence that avoids taboos. We describe the construction of the vertex set of $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) . Then we state conditions under which $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) and its suffix subgraphs are connected. Moreover, we provide an algorithm that determines if all these graphs are connected for an arbitrary $$\mathbb {T}$$ T . As an application of the algorithm, we show that about $$87\%$$ 87 % of bacteria listed in REBASE have a taboo-set that induces connected taboo-free Hamming graphs, because they have less than four type II restriction enzymes. On the other hand, four properly chosen taboos are enough to disconnect one suffix subgraph, and consequently connectivity of taboo-free Hamming graphs could change depending on the composition of restriction sites.

For a string S, a palindromic substring S[i..j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if S[i..j] occurs exactly once in S, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter than S[i..j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLES of size m in O(m) space and $O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})$ time so that all SUPSs for any subsequent query interval can be answered in $O(\sqrt {\log m / \log \log m} + \alpha )$ time, where α is the number of outputs, and $\sigma _{\mathit {RLE}_{S}}$ is the number of distinct runs of RLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in $O(\sqrt {\log \log m /\log \log \log m} + \alpha )$ time and can be built in $O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})$ time, and the second one answers queries in $O(\log \log m + \alpha )$ time and can be built in $O(m \log \sigma _{\mathit {RLE}_{S}})$ time. Both of these data structures require O(m) space.

Given a pattern x of length m and a text y of length n , both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods, reducing the number of false positives up to 99%. We also present a new efficient approach inspired by the well-known Skip Search algorithm for the exact string matching problem. It makes use of efficient SIMD SSE instructions for speeding up the searching phase. Experimental results show that our proposed algorithms are up to twice faster than previous solutions.

Delta encoding represents a target file making use of a source file by replacing common substrings by pointer references. Two similar, yet different, models are introduced and investigated in this paper: the Compressed Transitive Delta Encoding (CTDE) and the Compressed Source Delta Encoding (CSDE) paradigms. In these models we are given two delta files and the goal is to construct a third delta file working directly on the given compressed forms. Formally, given a source file S and two differencing files Δ ( S , T ) and Δ ( T , R ) , where Δ ( X , Y ) is used to denote the delta file of the target file Y with respect to the source file X , the objective of the CTDE problem is to be able to attain R . Unlike the traditional way which uses S to decompress Δ ( S , T ) , in order to attain T , and then applies Δ ( T , R ) on T to obtain R , CTDE constructs a delta file Δ ( S , R ) working directly on the two given delta files Δ ( S , T ) and Δ ( T , R ) , without any decompression or the use of the base file S . Thus, avoiding the storage of the redundant intermediate file T . An algorithm for solving CTDE is proposed and its compression performance is compared to the traditional “double delta decompression”. Not only does it use constant space, as opposed to linear memory storage used by the traditional method, experiments show that the compression efficiency of the constructed delta file Δ ( S , R ) is usually better than both Δ ( S , T ) and Δ ( T , R ) . The CSDE problem deals with a source file S and two differencing files Δ ( S , T ) and Δ ( S , R ) , and the goal is still to be able to attain R . Although it is not always possible to construct the target file R by processing only the two input delta files, empirical experiments show that on typical real life data, usually about 99% of the file can be constructed using the proposed algorithm for the CSDE problem.

In order to define a DNF version of first-order sentences over strings in which atomic sentences represent substring properties of strings, we use results of the Ehrenfeucht–Fraisse game over strings. Then, given a sample of strings and the number of disjunctive clauses, we investigate the problem of finding a DNF formula that is consistent with the sample. We show that this problem is NP-complete, and we solve it by a translation into Boolean satisfiability. We also present an extension of this problem that is robust concerning noisy samples. We solve the generalized version by a codification into the maximum satisfiability problem. As first-order logic over strings defines exactly the class of locally threshold testable (LTT) languages, our results can be useful in the grammatical inference framework when the goal is to find a model of a LTT language from a sample of strings.

Compared to conventional data storage media, DNA has several advantages, including high data density, energy efficiency, longevity, and ease of generating copies. However, challenges arising from the prevalence and variety of errors in the DNA data storage pipeline, which include substitutions, duplications, insertions, and deletions, must be addressed. This paper focuses on simultaneously correcting an arbitrary number of short tandem duplications and at most $p$ substitutions, where a short tandem duplication error consists of inserting a copy of a substring of length at most 3 immediately after it. Interacting with tandem duplications, the substitutions may affect segments of unbounded lengths in the stored sequence. However, if the codewords are irreducible, i.e., they do not have any short tandem repeats, the problem can be cast as correcting edits in at most $p$ substrings of bounded lengths. We construct irreducible codes with a structure that allows identifying where edit errors have occurred, which are then corrected using an MDS code. The rate of the proposed code correcting duplications and at most $p$ substitutions, when $\log p=o(\log n)$ , is shown to be at least $\log(q-2)(1-o(1)$ , where $q$ is the alphabet size and $n$ is the length of the code.

A string X = X [ 1 . . n ] , n > 1 , is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X ; for n = 1 , every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k , where X 1 is the longest closed prefix of X , X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O ( log ⁡ n ) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X . We first describe an off-line O ( n log 2 ⁡ n ) -time algorithm to compute M C F ( X ) , then we present an on-line algorithm for the same problem. In fact, we show that M C F ( X ) can be computed in O ( L log ⁡ n ) time from M C F ( X ′ ) , where X ′ = X [ 1 . . n − 1 ] , and L is the largest integer such that the suffix X [ n − L + 1 . . n ] is a substring of X ′ .

Insertion–deletion (or ins–del for short) systems are simple models of bio-inspired computing. They are well studied in formal language theory, especially regarding their computational completeness. This concerns the question if all recursively enumerable languages can be generated. This ultimately addresses the question if one can build general-purpose computers rooted in this formalism. The descriptional complexity of an ins–del system is typically measured by its size, a 6-dimensional tuple of non-negative integers $$(e,e',e'';d,d',d'')$$ where e is the maximum length of the insertion string, $$e'$$ (and $$e''$$ ) is the maximum length of the left (and right) context used for insertion; the last three parameters $$d,d',d''$$ are similarly understood for deletion rules. Computational completeness for ins–del systems can even be achieved with rule size (1, 1, 1; 1, 1, 1) but with no rule size strictly smaller than this. This fact has motivated to study ins–del systems in combination with regulation mechanisms. In this context, the six-tuple explained above is called the ID size of a system. Several regulations like graph-control, matrix and semi-conditional have been imposed on ins–del systems. Typically, the computational completeness results are obtained as trade-offs, reducing the ID size, say, to (1, 1, 0; 1, 1, 0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins–del systems, where an ins–del rule can be applied only in the presence or absence of substrings of the derivation string. This brings along two further natural parameters to measure descriptional complexity, namely, the maximum permitting string length p and the maximum forbidden string length f, usually summarized as the degree $$d=(p,f)$$ . We show that simple semi-conditional ins–del systems of degree (2, 1) and with ID sizes $$(1+e,e',e'';1+d,d',d'')$$ are computationally complete for any $$e,e',e'',d,d',d''\in \{0,1\}$$ , with $$e+e'+e''=1$$ and $$d+d'+d''=1$$ . The obtained results complement and improve on the existing results known from the literature. To prove our results, we also show a new normal form for type-0 grammars that appears to be interesting in its own right.

The generalized Fibonacci cube Q h ( f ) is the graph obtained from the h -cube Q h by removing all vertices that contain a given binary string f as a substring. If G is an induced subgraph of Q h , then the cube-complement of G is the graph induced by the vertices of Q h which are not in G . In particular, the cube-complement of a generalized Fibonacci cube Q h ( f ) is the subgraph of Q h induced by the set of all vertices that contain f as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied.

Order-preserving pattern matching was introduced recently but it has already attracted much attention. Given a reference sequence and a pattern, we want to locate all substrings of the reference sequence whose elements have the same relative order as the pattern elements. For this problem we consider the offline version in which we build an index for the reference sequence so that subsequent searches can be completed very efficiently. We propose a space-efficient index that works well in practice despite its lack of good worst-case time bounds. Our solution is based on the new approach of decomposing the indexed sequence into an order component, containing ordering information, and a delta component, containing information on the absolute values. Experiments show that this approach is viable, faster than the available alternatives, and it is the first one offering simultaneously small space usage and fast retrieval., Comment: 16 pages. A preliminary version appeared in the Proc. IEEE Data Compression Conference, DCC 2017, Snowbird, UT, USA, 2017

Consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE shortest substring search problem is to find all shortest substrings of T matching r. The previous algorithm proposed by Clarke and Cormack uses an e-free nondeterministic finite automaton (NFA) and runs in O ( k s n ) time and O ( s ) space, where k is the maximum number of outgoing transitions for any state and symbol, and s is the number of states. Generally, an e-free NFA obtained from a regular expression has s = O ( m ) and k = O ( m ) ; thus the algorithm takes O ( m 2 n ) time and O ( m ) space. We propose a faster algorithm that runs in O ( m n ) time and O ( m ) space. The proposed algorithm is based on a Thompson automaton which is an NFA with e-transitions.

This presentation is an exposition of an application of the theory of recurrence relations to enumerating strings over an alphabet with a forbidden factor (consecutive substring). As an illustration we examine the case of binary strings with a forbidden factor of k consecutive symbols 1 for given k, using generating function techniques that deserve to be better known. This allows us to derive a known upper bound for the number of prefix normal binary words: words with the property that no factor has more occurrences of the symbol 1 than the prefix of the same length. Such words arise in the context of indexed binary jumbled pattern matching.

The following metric dimension of join two paths $P_2 + P_t$ is determined as follows. For every $k = 1, 2, 3, ...$ and $t = 2 + 5k$ or $t = 3 + 5k$, the dimension of $P_2 + P_t$ is $2 + 2k$ whereas for $t = 4 + 5k, t = 5(k+1)$ or $t = 1 + 5(k+1)$, the dimension is $3 + 2k$. In case $t \geq 7$, the dimension is determined by a chosen (maximal) ordered basis for $P_2 + P_t$ in which the integers 1, 2 are the two consecutive vertices of $P_2$ and the next integers $3, 4, ..., t + 2$ are the $t$ consecutive vertices of $P_t$. If $t \geq 10$, the ordered binary string contains repeated substrings of length 5. For $t < 7$, the dimension is easily found using a computer search, or even just using hand computations.

We investigate inference of variable-length codes in other domains of computer science, such as noisy information transmission or information retrieval-storage: in such topics, traditionally mostly constant-length codewords act. The study is relied upon the two concepts of independent and closed sets: given an alphabet A and a binary relation τ ⊆ A ⁎ × A ⁎ , a set X ⊆ A ⁎ is τ-independent if τ ( X ) ∩ X = ∅ ; X is τ-closed if τ ( X ) ⊆ X . We focus to those word relations whose images are computed by applying some peculiar combinations of deletion, insertion, or substitution. In particular, characterizations of variable-length codes that are maximal in the families of τ-independent or τ-closed codes are provided.

An absent factor of a string w is a string u which does not occur as a contiguous substring (a.k.a. factor) inside w. We extend this well-studied notion and define absent subsequences: a string u is an absent subsequence of a string w if u does not occur as subsequence (a.k.a. scattered factor) inside w. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets; we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind; also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed.

A palindrome is a string that reads the same forward and backward. A palindromic substring w of a string T is called a minimal unique palindromic substring (MUPS) of T if w occurs only once in T and any proper palindromic substring of w occurs at least twice in T. MUPSs are utilized for answering the shortest unique palindromic substring problem, which is motivated by molecular biology [Inoue et al., 2018]. Given a string T of length n, all MUPSs of T can be computed in O(n) time. In this paper, we study the problem of updating the set of MUPSs when a character in the input string T is substituted by another character. We first analyze the number d of changes of MUPSs when a character is substituted, and show that d is in \(O(\log n)\). Further, we present an algorithm that uses O(n) time and space for preprocessing, and updates the set of MUPSs in \(O(\log \sigma + (\log \log n)^2 + d)\) time where \(\sigma \) is the alphabet size. We also propose a variant of the algorithm, which runs in optimal \(O(1+d)\) time when the alphabet size is constant.

A grammar self-index of a text T (Claude et al. 2012) consists of a grammar \({\mathcal {G}}\) that only produces T and a geometric data structure that indexes the string cuts of the right-hand sides of \({\mathcal {G}}\)’s rules. This representation uses space proportional to G, the size of the grammar, which is small when the text is repetitive. However, the index is slow for matching long patterns; it finds the occ occurrences of a pattern P[1..m] in \(O((m^{2}+occ)\log G)\) time. The most expensive part is a set of binary searches for the different cuts \(P[1..j]P[j+1..m]\) in the geometric data structure. Christiansen et al. 2010 solved this problem by building a locally consistent grammar that only searches for \(O(\log m)\) cuts of P. Their representation, however, requires significant extra space (tough still in O(G)) to store a set of permutations for the nonterminal symbols. In this work, we propose another locally consistent grammar that builds on the idea of LMS substrings (Nong et al. 2009). Our grammar also requires to try \(O(\log m)\) cuts when searching for P, but it does not need to store permutations. As a result, we obtain a self-index that searches in time \(O((m\log m+occ) \log G)\) and is of practical size. Our experiments showed that our index is faster than previous grammar-based indexes at the price of increasing the space by a 1.8x factor on average. Other experimental results showed that our data structure becomes convenient when the patterns to search for are long.

A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kreft & Navarro, TCS 2013). One of the interests for LZ-End factorizations is the possible difference between the size of LZ-End and LZ77 factorizations. They also showed families of strings where the approximation ratio of the number of LZ-End phrases to the number of LZ77 phrases asymptotically approaches 2. However, the alphabet size of these strings is unbounded. In this paper, we analyze the LZ-End factorization of the period-doubling sequence. We also show that the approximation ratio for the period-doubling sequence asymptotically approaches 2 for the binary alphabet.

This paper describes the application of the cycles merging algorithm for data compression using an approximate solution to the Shortest Common Superstring (SCS) problem, which is reduced to solving the asymmetric traveling salesman problem to the maximum (MaxTSP). SCS is as follows: given a collection of strings $s_{1},\ldots, s_{m}$, find the shortest string s such that each s i appears as a substring (a consecutive block) of s. The algorithm is tested for data compression on randomly generated data with the specified parameters, the results are compared with the results of data compression by greedy and 4-approximation algorithms. The efficiency of the CMA algorithm for the maximum problem is investigated.

We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS in sublinear space, which we obtain by extending an algorithm by Senanayaka (2019) and combining it with a result on sketching by Gawrychowski and Starikovskaya (2019). We first describe how, given a text T of length n and m words of workspace, with high probability we can find an SUS of length L in O(n(L/m)logL) time using random access to T, or in O(n(L/m)log2(L)loglog&sigma, ) time using O((L/m)log2L) sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in O(n1+ϵL/m) time using O(nϵL/m) sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes O(n&tau, log&sigma, logn) time to find an SUS using O(n/&tau, ) words of workspace, where &tau, is a parameter.

Because of its high data density and longevity, DNA is emerging as a promising candidate for satisfying increasing data storage needs. Compared to conventional storage media, however, data stored in DNA is subject to a wider range of errors resulting from various processes involved in the data storage pipeline. In this paper, we consider correcting duplication errors for both exact and noisy tandem duplications of a given length k. An exact duplication inserts a copy of a substring of length k of the sequence immediately after that substring, e.g., ACGT to ACGACGT, where k = 3, while a noisy duplication inserts a copy suffering from substitution noise, e.g., ACGT to ACGATGT. Specifically, we design codes that can correct any number of exact duplication and one noisy duplication errors, where in the noisy duplication case the copy is at Hamming distance 1 from the original. Our constructions rely upon recovering the duplication root of the stored codeword. We characterize the ways in which duplication errors manifest in the root of affected sequences and design efficient codes for correcting these error patterns. We show that the proposed construction is asymptotically optimal, in the sense that it has the same asymptotic rate as optimal codes correcting exact duplications only., 14 pages, 2 figures, Allerton, TIT draft

We study the duplication with transposition distance between strings of length $n$ over a $q$-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form $x = (abcd) \to y = (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their substrings, needed to get a $q$-ary string of length $n$ starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most $n$ and its root has the asymptotic order $n/\log n$. For approximate duplication, where a $\beta$-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order $n/\log n$ to $\log n$ at $\beta=(q-1)/q$. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence., Comment: 6 pages, 1 table, submitted to International Symposium on Information Theory (ISIT) 2020

The shortest superstring problem for a given set of strings is to find a string of minimum length such that each input string is a substring of the resulting string. This problem is known to be NP-complete. A simple and popular approximation algorithm for this problem is GREEDY, which at each step merges a pair of strings that have maximum overlap. If more than one pair have maximum overlap, it takes a pair in random. In this paper, we modify GREEDY such that instead of taking a pair in random, it takes the pair for which the overlap in the next step is maximum. We analyze our algorithm and compare it with GREEDY for different types of input. We implement both the algorithms and the experimental results show that our algorithm can outperform GREEDY substantially in many cases, and in general our algorithm is same or better than GREEDY.

This paper revisits the $k$ k -mismatch shortest unique substring finding problem and demonstrates that a technique recently presented in the context of solving the $k$ k -mismatch average common substring problem can be adapted and combined with parts of the existing solution, resulting in a new algorithm which has expected time complexity of $O(n\;\log \!^{k}\;{n})$ O ( n log k n ) , while maintaining a practical space complexity at $O(kn)$ O ( k n ) , where $n$ n is the string length. When $k>0$ k > 0 , which is the hard case, our new proposal significantly improves the any-case $O(n^2)$ O ( n 2 ) time complexity of the prior best method for $k$ k -mismatch shortest unique substring finding. Experimental study shows that our new algorithm is practical to implement and demonstrates significant improvements in processing time compared to the prior best solution's implementation when $k$ k is small relative to $n$ n . For example, our method processes a 200 KB sample DNA sequence with $k=1$ k = 1 in just 0.18 seconds compared to 174.37 seconds with the prior best solution. Further, it is observed that significant portions of the adapted technique can be executed in parallel, using two different simple concurrency models, resulting in further significant practical performance improvement. As an example, when using 8 cores, the parallel implementations both achieved processing times that are less than $1/4$ 1 / 4 of the serial implementation's time cost, when processing a 10 MB sample DNA sequence with $k=2$ k = 2 . In an age where instances with thousands of gigabytes of RAM are readily available for use through Cloud infrastructure providers, it is likely that the trade-off of additional memory usage for significantly improved processing times will be desirable and needed by many users. For example, the best prior solution may spend years to finish a DNA sample of 200MB for any $k>0$ k > 0 , while this new proposal, using 24 cores, can finish processing a sample of this size with $k=1$ k = 1 in 206.376 seconds with a peak memory usage of 46 GB, which is both easily available and affordable on Cloud. It is expected that this new efficient and practical algorithm for $k$ k -mismatch shortest unique substring finding will prove useful to those using the measure on long sequences in fields such as computational biology. We also give a theoretical bound that the $k$ k -mismatch shortest unique substring finding problem can be solved using $O(n\;\log \!^{k}\;{n})$ O ( n log k n ) time and $O(n)$ O ( n ) space, asymptotically much better than the one we implemented, serving as a new discovery of interest.

In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection $G$ of t sequences $S_i$ of length n each, we can represent G succinctly in $2n\mathcal{H_k}(T) + O(n^\prime \log\log\;n) + o(qn^\prime) + o(tn)$ bits using $O(tn^2 + qn^\prime)$ time, where $\mathcal{H_k}(T)$ is the k-order empirical entropy of the sequence $T \in G$ that is used as the reference sequence, $n^\prime$ is the total number of variations between T and the sequences in G, and q is a small fixed constant. We can restore any length len substring $S[sp, \dots, sp + len - 1]$ of $S \in G$ in $O(n_{s}^{\prime} + len(\log\;n)^2/ \log\;n)$ time and report all positions where P occurs in G in $O(m\cdot t + occ\cdot t \cdot (\log\;n)^2/ \log\; \log\;n)$ time. In addition, we propose a dynamic programming method to find the variations between T and the sequences in G in a space-efficient way, with which we can build succinct structures to enable efficient search. For highly repetitive sequences, experimental results on the tested data demonstrate that the proposed method has significant advantages in space usage and retrieval time over the current state-of-the-art methods. The source code is available online.

We show that the size \(\gamma (t_n)\) of the smallest string attractor of the n-th Thue-Morse word \(t_n\) is 4 for any \(n\ge 4\), disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is n. We also show that \(\delta (t_n) = \frac{10}{3+2^{4-n}}\) for \(n \ge 3\), where \(\delta (w)\) is the maximum over all \(k = 1,\ldots ,|w|\), the number of distinct substrings of length k in w divided by k, which is a measure of repetitiveness recently studied by Kociumaka et al. [LATIN 2020]. Furthermore, we show that the number \(z(t_n)\) of factors in the self-referencing Lempel-Ziv factorization of \(t_n\) is exactly 2n.

Indexing highly repetitive texts - such as genomic databases, software repositories and versioned text collections - has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is r, the number of runs in their Burrows-Wheeler Transforms (BWTs). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used O(r) space and was able to efficiently count the number of occurrences of a pattern of length m in the text (in loglogarithmic time per pattern symbol, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of r. In this paper we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the occ occurrences efficiently within O(r) space (in loglogarithmic time each), and reaching optimal time, O(m + occ), within O(r log log w ({\sigma} + n/r)) space, for a text of length n over an alphabet of size {\sigma} on a RAM machine with words of w = {\Omega}(log n) bits. Within that space, our index can also count in optimal time, O(m). Multiplying the space by O(w/ log {\sigma}), we support count and locate in O(dm log({\sigma})/we) and O(dm log({\sigma})/we + occ) time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using O(r log(n/r)) space that replaces the text and extracts any text substring of length ` in almost-optimal time O(log(n/r) + ` log({\sigma})/w). Within that space, we similarly provide direct access to suffix array, inverse suffix array, and longest common prefix array cells, and extend these capabilities to full suffix tree functionality, typically in O(log(n/r)) time per operation., Comment: submitted version; optimal count and locate in smaller space: O(r log log_w(n/r + sigma))

The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was recently proven by Alzamel et al. [2] that finding whether or not a k-anticover exists is \(\mathcal {NP}\)-Hard for \(k \ge 3\).

The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings A and B. More recently, a set of four constrained LCS problems (called generalized constrained LCS problem) were proposed by Chen and Chao [J. Comb. Optim, 2011]. In this paper, we consider the substring-excluding constrained LCS (STR-EC-LCS) problem. A string Z is said to be an STR-EC-LCS of two given strings A and B excluding P if, Z is one of the longest common subsequences of A and B that does not contain P as a substring. Wang et al. proposed a dynamic programming solution which computes an STR-EC-LCS in O(mnr) time and space where \(m = |A|, n = |B|, r = |P|\) [Inf. Process. Lett., 2013]. In this paper, we show a new solution for the STR-EC-LCS problem. Our algorithm computes an STR-EC-LCS in \(O(n|\varSigma | + (L+1)(m-L+1)r)\) time where \(|\varSigma | \le \min \{m, n\}\) denotes the set of distinct characters occurring in both A and B, and L is the length of the STR-EC-LCS. This algorithm is faster than the O(mnr)-time algorithm for short/long STR-EC-LCS (namely, \(L \in O(1)\) or \(m-L \in O(1)\)), and is at least as efficient as the O(mnr)-time algorithm for all cases.

Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation \(\approx \) over strings is called a substring consistent equivalence relation (SCER) iff \(X \approx Y\) implies (1) \(|X| = |Y|\) and (2) \(X[i:j] \approx Y[i:j]\) for all \(1 \le i \le j \le |X|\). In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.

Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky’s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested \((k+1)\)-component grammars.

A factorization of a string w is a partition of w into substrings \(u_1,\dots ,u_k\) such that \(w=u_1 u_2 \cdots u_k\). Such a partition is called equality-free if no two factors are equal: \(u_i \ne u_j, \forall i,j\) with \(i \ne j\). The maximum equality-free factorization problem is to decide, for a given string w and integer k, whether w admits an equality-free factorization with k factors.

We consider the problem of correcting mass readout errors in information encoded in binary polymer strings. Our work builds on results for string reconstruction problems using composition multisets [Acharya et al., 2015] and the unique string reconstruction framework proposed in [Pattabiraman et al., 2019]. Binary polymer-based data storage systems [Laure et al., 2016] operate by designing two molecules of significantly different masses to represent the symbols $\{{0,1\}}$ and perform readouts through noisy tandem mass spectrometry. Tandem mass spectrometers fragment the strings to be read into shorter substrings and only report their masses, often with errors due to imprecise ionization. Modeling the fragmentation process output in terms of composition multisets allows for designing asymptotically optimal codes capable of unique reconstruction and the correction of a single mass error [Pattabiraman et al., 2019] through the use of derivatives of Catalan paths. Nevertheless, no solutions for multiple-mass error-corrections are currently known. Our work addresses this issue by describing the first multiple-error correction codes that use the polynomial factorization approach for the Turnpike problem [Skiena et al., 1990] and the related factorization described in [Acharya et al., 2015]. Adding Reed-Solomon type coding redundancy into the corresponding polynomials allows for correcting $t$ mass errors in polynomial time using $t^2\, \log\,k$ redundant bits, where $k$ is the information string length. The redundancy can be improved to $\log\,k + t$. However, no decoding algorithm that runs polynomial-time in both $t$ and $n$ for this scheme are currently known, where $n$ is the length of the coded string.

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. A string w is called a minimal absent word (MAW) of T if w does not occur in T and any proper substring of w occurs in T. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string T. We first show how the set of MUSs can change in a sliding window over T, and present an \(O(n\log \sigma )\)-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where \(\sigma \) is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over T. Our bounds improve on the previous results in Crochemore et al. (2017).

Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary matching problem can be solved efficiently by using the Aho-Corasick algorithm. Recently, Matsuoka et al. [TCS, 2016] proposed a generalization of pattern matching problem under substring consistent equivalence relations and presented a generalization of the Knuth-Morris-Pratt algorithm to solve this problem. An equivalence relation \(\approx \) is a substring consistent equivalence relation (SCER) if for two strings X, Y, \(X \approx Y\) implies \(|X| = |Y|\) and \(X[i:j] \approx Y[i:j]\) for all \(1 \le i \le j \le |X|\). In this paper, we propose a generalization of the dictionary matching problem and present a generalization of the Aho-Corasick algorithm for the dictionary matching under SCER. We present an algorithm that constructs SCER automata and an algorithm that performs dictionary matching under SCER by using the automata. Moreover, we show the time and space complexity of our algorithms with respect to the size of input strings.

We study a central problem of string processing: the compact representation of a string by its frequently-occurring substrings. In this paper we propose an effective, easily-computed form of quasi-periodicity in strings, the frequency cover; that is, the longest of those repeating substrings u of w, |u| > 1, that occurs the maximum number of times in w. The advantage of this generalization is that it is not only applicable to all strings but also that it is the only generalized notion of cover yet proposed, which can be computed efficiently in linear time and space. We describe a simple data structure called the repeating substring frequency array (ℛ

The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS can be computed in O(n) space and time, where n=x+y is the input size. The compressed string matching is the study of string matching problems with the following twist: the input data is in a compressed format and the underling task must be performed with little or no decompression. In this paper, we revisit the ACS problem under this paradigm where the input sequences are given in their run-length encoded format. We present an algorithm to compute ACS(X,Y) in O(Nlog N) time using O(N) space, where N is the total length of sequences after run-length encoding.

A palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [ s , t ] in S, if P occurs exactly once in S, this occurrence of P contains interval [ s , t ] , and every palindromic substring of S which contains interval [ s , t ] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [ s , t ] all the SUPSs for interval [ s , t ] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O ( n ) time and space so that all SUPSs for any subsequent query interval can be answered in O ( α + 1 ) time, where α is the number of outputs. We also discuss the number of SUPSs in a string.

The Longest Common Extension of a pair of positions ( i , j ) in a string, or word, is the longest substring starting at i and j . The LCE problem considers a word and a set of pairs of positions and computes for each pair in the set, the longest common extension starting at both positions in the pair. This problem finds applications in matching with don’t-care characters, approximate string searching, finding all exact or approximate tandem repeats, to name a few. From a practical point of view, Ilie et al. (Journal of Discrete Algorithms, 2010) looked for simple and efficient algorithms for the LCE problem. In this paper, we extend their analyses to partial words, strings with don’t-cares or holes. We compute the Longest Common Compatible Extension of each pair of positions ( i , j ) in a partial word, i.e., the longest substrings starting at i and j that are compatible via a combinatorial approach. We also estimate the LCCE of each pair of positions in a partial word via a probabilistic approach. We show that our results match with those of total words (partial words without holes). We find that one of the simplest algorithms for implementing the LCE problem is optimal on average in the context of partial words.

Patterns within strings enable us to extract vital information regarding a string&rsquo, s randomness. Understanding whether a string is random (Showing no to little repetition in patterns) or periodic (showing repetitions in patterns) are described by a value that is called the kth Subword Complexity of the character string. By definition, the kth Subword Complexity is the number of distinct substrings of length k that appear in a given string. In this paper, we evaluate the expected value and the second factorial moment (followed by a corollary on the second moment) of the kth Subword Complexity for the binary strings over memory-less sources. We first take a combinatorial approach to derive a probability generating function for the number of occurrences of patterns in strings of finite length. This enables us to have an exact expression for the two moments in terms of patterns&rsquo, auto-correlation and correlation polynomials. We then investigate the asymptotic behavior for values of k = &Theta, ( log n ) . In the proof, we compare the distribution of the kth Subword Complexity of binary strings to the distribution of distinct prefixes of independent strings stored in a trie. The methodology that we use involves complex analysis, analytical poissonization and depoissonization, the Mellin transform, and saddle point analysis..