Search

Gagie, Navarro and Prezza's r -index (SODA, 2018) promises to speed up DNA alignment and variation calling by allowing us to index entire genomic databases, provided certain obstacles can be overcome. In this paper we first strengthen and simplify Policriti and Prezza's Toehold Lemma (DCC '16; Algorithmica , 2017), which inspired the r -index and plays an important role in its implementation. We then show how to update the r -index efficiently after adding a new genome to the database, which is likely to be vital in practice. As a by-product of this result, we obtain an online version of Policriti and Prezza's algorithm for constructing the LZ77 parse from a run-length compressed Burrows-Wheeler Transform. Our experiments demonstrate the practicality of all three of these results. Finally, we show how to augment the r -index such that, given a new genome and fast random access to the database, we can quickly compute the matching statistics and maximal exact matches of the new genome with respect to the database. [ABSTRACT FROM AUTHOR]

Abstract 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 SUPS s 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 SUPS s for any subsequent query interval can be answered in O (α + 1) time, where α is the number of outputs. We also discuss the number of SUPS s in a string. [ABSTRACT FROM AUTHOR]

Abstract: We present simple and efficient algorithms for calculating q-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP of size n that represents string T, we present an time and space algorithm that computes the occurrence frequencies of all q-grams in T. Computational experiments show that our algorithm and its variation are practical for small q, actually running faster on various real string data, compared to algorithms that work on the uncompressed text. We also discuss applications in data mining and classification of string data, for which our algorithms can be useful. [Copyright &y& Elsevier]

Abstract: Position-specific score matrices (PSSMs) have been applied to various problems in computational molecular biology. In this paper, we study the following problem: given positive examples (sequences) and negative examples (sequences), find a PSSM which correctly discriminates between positive and negative examples. We prove that this problem is solved in polynomial time if the size of a PSSM is bounded by a constant. On the other hand, we prove that this problem is NP-hard if the size is not bounded. We also prove hardness results for deriving multiple PSSMs and related problems. [Copyright &y& Elsevier]

Abstract: It is known that there is a close analogy between “Euclidean -designs vs. spherical -designs” and “Relative -designs in binary Hamming association schemes vs. combinatorial -designs”. In this paper, we want to prove how much we can develop a similar theory in the latter situation, imitating the theory in the former one. We first prove that the weight function is constant on each shell for tight relative -designs on shells on a wide class of -polynomial association schemes, including Hamming association schemes. In the theory of Euclidean -designs on 2 concentric spheres (shells), it is known that the structure of coherent configurations is naturally attached. However, it seems difficult to prove this claim in a general context. In the case of tight 2-designs in combinatorial 2-designs, there are great many tight 2-designs, i.e., symmetric 2-designs, while there are very few tight -designs for . So, as a starting point, we concentrate our study to the existence problem of tight relative 2-designs, in particular on 2 shells, in binary Hamming association schemes . We prove that every tight relative 2-design on 2 shells in has the structure of coherent configuration. We determine all the possible parameters of coherent configurations attached to such tight relative 2-designs for . Moreover for each of them we determine whether there exists such a tight relative 2-design or not, either by constructing them from symmetric 2-designs or Hadamard matrices, or theoretically showing the non-existence. In particular, we show that for , there exist such tight relative 2-designs whose weight functions are not constant. These are the first examples of those with non-constant weight. [Copyright &y& Elsevier]

Abstract: A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree accompanied with a node-to-node transition function , infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to and , respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. [Copyright &y& Elsevier]

A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where each edge is labeled with a single symbol, and the endpoints of the path must be a descendant/ancestor of the other. For a trie with n edges, we show that the number of runs is less than n. We also show an asymptotic lower bound on the maximum density of runs in tries: lim n → ∞ ⁡ ρ T (n) / n > 0.9932348 where ρ T (n) is the maximum number of runs in a trie with n edges. Furthermore, we also show an O (n log ⁡ log ⁡ n) time and O (n) space algorithm for finding all runs. [ABSTRACT FROM 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 (ℓ + log ⁡ log ⁡ n) time, after an existing substring in T is replaced by a string of arbitrary length ℓ. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider the problem of reverse-engineering the Lyndon tree, i.e., given a full binary ordered tree T with n leaves as input, we are to compute a string w of length n of which Lyndon tree is isomorphic to the input tree T. Hereby we call such a string a solution string. Although the problem is easily solvable in linear time for binary alphabets and unbounded-size alphabets, it is not known how to efficiently find the smallest alphabet size for a solution string. In this paper, we show several new observations concerning this problem. Namely, we show that: 1) For any positive integer n , there exists a full binary ordered tree T with n leaves, s.t. the smallest alphabet size of a solution string for T is ⌊ n 2 ⌋ + 1. 2) For any full binary ordered tree T with n leaves, there exists a solution string w over an alphabet of size at most ⌊ n 2 ⌋ + 1. 3) For any full binary ordered tree T , there exists a solution string w over an alphabet of size at most h + 1 , where h is the height of T. 4) For any complete binary ordered tree T with 2 k leaves, there exists a solution string w over an alphabet of size at most 4. [ABSTRACT FROM AUTHOR]

The Lyndon factorization of a string w is a unique factorization ℓ 1 p 1 , … , ℓ m p m of w such that ℓ 1 , … , ℓ m is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization : Given a sequence S = ( ( s 1 , p 1 ) , … , ( s m , p m ) ) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S , i.e., the Lyndon factorization of w is in a form of ℓ 1 p 1 , … , ℓ m p m with | ℓ i | = s i for all 1 ≤ i ≤ m . Firstly, we show that there exists a simple O ( n ) -time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O ( n ) -time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O ( m ) time. Fourthly, we give an O ( m ) -time algorithm to compute an O ( m ) -size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S . [ABSTRACT FROM AUTHOR]

We present two efficient algorithms which, given a compressed representation of a string w of length N , compute the Lyndon factorization of w . Given a straight line program (SLP) S of size n that describes w , the first algorithm runs in O ( n 2 + P ( n , N ) + Q ( n , N ) n log ⁡ n ) time and O ( n 2 + S ( n , N ) ) space, where P ( n , N ) , S ( n , N ) , Q ( n , N ) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Given the Lempel–Ziv 78 encoding of size s for w , the second algorithm runs in O ( s log ⁡ s ) time and space. [ABSTRACT FROM AUTHOR]

Let ≈ be a substring consistent equivalence relation ( SCER ) on strings such that for any two strings x , y , x ≈ y implies that (1) | x | = | y | and (2) x [ i . . j ] ≈ y [ i . . j ] for all 0 ≤ i ≤ j < | x | . Examples of SCER are parameterized pattern matching and order-preserving pattern matching. We present a generalized and efficient algorithm for pattern matching with SCER ≈. Also, we show analogues of Fine and Wilf's periodicity lemma hold for SCER. [ABSTRACT FROM AUTHOR]