Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

Fast index for approximate string matching

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k from the pattern are reported in $O(m+\log \log n+\text{\#}\text{matches})$ time (for constant k). The space complexity of the index is $O(n^{1+?})$ for any constant $?>0$.     

Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t₁t₂…t_n and pattern p=p₁p₂…p_m over respective alphabets Σ_t and Σ_p, the injection π_i from Σ_p to Σ_t maximizing the number of matches between π_i(p) and t_it_i+1…t_i+m−1 (i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r_p×r_t)α(r_t)log(r_t)), where r_p and r_t denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.     

Some string matching problems from Bioinformatics which still need better solutions

Bioinformatics, the discipline which studies the computational problems arising from molecular biology, poses many interesting problems to the string searching community. We will describe two problems arising from Bioinformatics, their preliminary solutions, and the more general problem that they pose. The first problem is searching for α-helices in protein sequences. This particular instance of the search is based on matching of hydrophobicity/hydrophilicity. We find an algorithm which is linear in the sequence length for fixed helix length and is O(nlogn) for any helix length. The second problem is on matching probabilistic sequences against sequences or against other probabilistic sequences. In both cases we derive efficient formulas to compute scores according to a Markovian model of evolution.     

(Prefix) reversal distance for (signed) strings with few blocks or small alphabets

We study the String Reversal Distance problem, an extension of the well-known Sorting by Reversals problem. String Reversal Distance takes two strings S and T built on an alphabet Σ as input, and asks for a minimum number of reversals to obtain T from S. We consider four variants: String Reversal Distance, String Prefix Reversal Distance (a constrained version of the previous problem, in which any reversal must include the first letter of the string), and the signed variants of these problems, namely Signed String Reversal Distance and Signed String Prefix Reversal Distance. We study algorithmic properties of these four problems, in connection with two parameters of the input strings: the number of blocks they contain (a block being a maximal substring such that all letters in the substring are equal), and the alphabet size $|\mathrm{\Sigma }|$. Concerning the number of blocks, we show that the four problems are fixed-parameter tractable (FPT) when the considered parameter is the maximum number of blocks among the two input strings. Concerning the alphabet size, we first show that String Reversal Distance and String Prefix Reversal Distance are NP-hard even if the input strings are built on a binary alphabet $\mathrm{\Sigma }=\{0,1\}$, each 0-block has length at most two and each 1-block has length one. We also show that Signed String Reversal Distance and Signed String Prefix Reversal Distance are NP-hard even if the input strings have only one letter. Finally, when $|\mathrm{\Sigma }|=O(1)$, we provide a singly-exponential algorithm that computes the exact distance between any pair of strings, for a large family of distances that we call well-formed, which includes the four distances we study here.     

Approximate range searching using binary space partitions

We show how any BSP tree for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(nlogn) such that -approximate range searching queries with any constant-complexity convex query range can be answered in O(min_>0{(1/)+k}logn) time, where k is the number of segments intersecting the -extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves.We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in such that -approximate range searching with any constant-complexity convex query range can be done in O(logn+min_>0{(1/^d−1)+k}) time.     

Space efficient linear time construction of suffix arrays

We present a linear time algorithm to sort all the suffixes of a string over a large alphabet of integers. The sorted order of suffixes of a string is also called suffix array, a data structure introduced by Manber and Myers that has numerous applications in pattern matching, string processing, and computational biology. Though the suffix tree of a string can be constructed in linear time and the sorted order of suffixes derived from it, a direct algorithm for suffix sorting is of great interest due to the space requirements of suffix trees. Our result is one of the first linear time suffix array construction algorithms, which improve upon the previously known O(nlogn) time direct algorithms for suffix sorting. It can also be used to derive a different linear time construction algorithm for suffix trees. Apart from being simple and applicable for alphabets not necessarily of fixed size, this method of constructing suffix trees is more space efficient.     

Using pattern matching for tiling and packing problems

This paper describes a new placement method based on pattern matching for 2D tiling problems. Tiling problem can be considered as a special case of bin packing. In the proposed method, the representation of the figures and the board is based on directional chain codes. Contrary to other works that the area has been used for the board and the figures, the proposed method is based on usage of their boundaries instead. With this representation, consideration of the area has been replaced with that of the exact string matching. With the proposed knowledge representation, rotation and reflection of the figures can be considered easily. The results of a hybrid approach of genetic algorithm and simulated annealing have been shown. This new method, introduces a novel approach for handling and solving a variety of 2D-packing problems.     

Chromatic nearest neighbor searching: A query sensitive approach

The nearest neighbor problem is that of preprocessing a set P of n data points in so that, given any query point q, the closest point in P to q can be determined efficiently. In the chromatic nearest neighbor problem, each point of P is assigned a color, and the problem is to determine the color of the nearest point to the query point. More generally, given k1, the problem is to determine the color occurring most frequently among the k nearest neighbors. The chromatic version of the nearest neighbor problem is used in many applications in pattern recognition and learning. In this paper we present a simple algorithm for solving the chromatic k nearest neighbor problem. We provide a query sensitive analysis, which shows that if the color classes form spatially well separated clusters (as often happens in practice), then queries can be answered quite efficiently. We also allow the user to specify an error bound 0, and consider the same problem in the context of approximate nearest neighbor searching. We present empirical evidence that for well clustered data sets, this approach leads to significant improvements in efficiency.     

Fast and flexible packed string matching

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time.In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design a very fast string matching algorithm. We evaluate our solution in terms of efficiency, stability and flexibility, where we propose to use the deviation in running time of an algorithm on distinct equal length patterns as a measure of stability.From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithm becomes the clear winner on the average in many cases, when compared against the most recent and effective algorithms known in literature.     

Extracting approximate patterns

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis.

We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q−1 times, in time O(|Σ|Nn²logn), where Σ is the alphabet. In the particular case where q=2, the complexity in time is only O(|Σ|n²logn). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential.