The Parikh vector p(s) of a string s over a finite ordered alphabet Σ = a1, …, aσ is defined as the vector of multiplicities of the characters, p(s) = (p1, …, pσ), where pi = | j | sj = ai |. Parikh vector q occurs in s if s has a substring t with p(t) = q. The problem of searching for a query q in a text s of length n can be solved simply and worst-case optimally with a sliding window approach in O(n) time. We present two novel algorithms for the case where the text is fixed and many queries arrive over time. The first algorithm only decides whether a given Parikh vector appears in a binary text. It uses a linear size data structure and decides each query in O(1) time. The preprocessing can be done trivially in Θ(n2) time. The second algorithm finds all occurrences of a given Parikh vector in a text over an arbitrary alphabet of size σ ≥ 2 and has sub-linear expected time complexity. More precisely, we present two variants of the algorithm, both using an O(n) size data structure, each of which can be constructed in O(n) time. The first solution is very simple and easy to implement and leads to an expected query time of , where m = ∑i qi is the length of a string with Parikh vector q. The second uses wavelet trees and improves the expected runtime to , i.e., by a factor of log m.
An efficient algorithm for computing all Parikh fingerprints of substrings of a given string was developed in @cite_20 . Parikh fingerprints are Boolean vectors where the @math 'th entry is @math if and only if @math appears in the string. The algorithm involves storing a data point for each Parikh fingerprint, of which there are at most @math many. This approach was adapted in @cite_16 for Parikh vectors and applied to identifying all repeated Parikh vectors within a given length range; using it to search for queries of arbitrary length would imply using @math space, where @math denotes the number of different Parikh vectors of substrings of @math . This is not desirable, since, for arbitrary alphabets, there are non-trivial strings of any length with quadratic @math @cite_22 .
@cite_16 @cite_22 @cite_20
1977563497 2031705959 2032064287
Functionally related genes often appear in each other's neighborhood on the genome; however, the order of the genes may not be the same. These groups or clusters of genes may have an ancient evolutionary origin or may signify some other critical phenomenon and may also aid in function prediction of genes. Such gene clusters also aid toward solving the problem of local alignment of genes. Similarly, clusters of protein domains, albeit appearing in different orders in the protein sequence, suggest common functionality in spite of being nonhomologous. In the paper, we address the problem of automatically discovering clusters of entities, be they genes or domains: we formalize the abstract problem as a discovery problem called the πpattern problem and give an algorithm that automatically discovers the clusters of patterns in multiple data sequences. We take a model-less approach and introduce a notation for maximal patterns that drastically reduces the number of valid cluster patterns, without any loss of inf... Abstract We investigate a problem which arises in computational biology: Given a constant-size alphabet A with a weight function μ : A → N , find an efficient data structure and query algorithm solving the following problem: For a string σ over A and a weight M∈ N , decide whether σ contains a substring with weight M , where the weight of a string is the sum of the weights of its letters (O NE -S TRING M ASS F INDING P ROBLEM ). If the answer is yes , then we may in addition require a witness, i.e., indices i ⩽ j such that the substring beginning at position i and ending at position j has weight M . We allow preprocessing of the string and measure efficiency in two parameters: storage space required for the preprocessed data and running time of the query algorithm for given M . We are interested in data structures and algorithms requiring subquadratic storage space and sublinear query time, where we measure the input size as the length n of the input string σ . Among others, we present two non-trivial efficient algorithms: L OOKUP solves the problem with O( n ) storage space and O (n log n) time; I NTERVAL solves the problem for binary alphabets with O( n ) storage space in O ( log n) query time. We introduce other variants of the problem and sketch how our algorithms may be extended for these variants. Finally, we discuss combinatorial properties of weighted strings. We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S' is a substring of S, then the fingerprint of S' is the subset φ of Σ of precisely the symbols appearing in S'. In this paper we show efficient methods of answering various queries on fingerprint statistics. Our preprocessing is done in time O(n|Σ|log n log |Σ|) and enables answering the following queries: (1) Given an integer k, compute the number of distinct fingerprints of size k in time O(1). (2) Given a set φ ⊆ Σ, compute the total number of distinct occurrences in S of substrings with fingerprint φ in time O(|Σ|logn).