Search

In genome assembly graphs, motifs such as tips, bubbles, and cross links are studied in order to find sequencing errors and to understand the nature of the genome. Superbubble, a complex generalization of bubbles, was recently proposed as an important subgraph class for analyzing assembly graphs. At present, a quadratic time algorithm is known. This paper gives an O(m log m)-time algorithm to solve this problem for a graph with m edges.

In memory-constrained algorithms, access to the input is restricted to be read-only, and the number of extra variables that the algorithm can use is bounded. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose main memory consumption takes the form of a stack into memory-constrained algorithms. Given an algorithm $$\mathcal {A}$$ that runs in $$O(n)$$ time using a stack of length $$\Theta (n)$$ , we can modify it so that it runs in $$O(n^2\log n/2^s)$$ time using a workspace of $$O(s)$$ variables (for any $$s\in o(\log n)$$ ) or $$O(n^{1+1/\log p})$$ time using $$O(p\log _p n)$$ variables (for any $$2\le p\le n$$ ). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, a 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach improves or matches up to a $$O(\log n)$$ factor the running time of the best-known results for these problems in constant-workspace models (when they exist), and gives a trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms. [ABSTRACT FROM AUTHOR]

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel-Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let S be a string of length N compressed into a context-free grammar S of size n. We present two representations of S achieving O(logN) random access time, and either O(n.αk(n)) construction time and space on the pointer machine model, or O(n) construction time and space on the RAM. Here, αk(n) is the inverse of the kth row of Ackermann's function. Our representations also efficiently support decompression of any substring in S: we can decompress any substring of length m in the same complexity as a single random access query and additional O(m) time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern P with at most k errors in time O(n(min{ [ABSTRACT FROM AUTHOR]

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(| P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log| T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear ( o( n)) time and sublinear ( o( nlog σ) bits) working space for small alphabets ( $\sigma= 2^{o(\log n \frac{\log\log\log n}{(\log\log n)^{2}})}$). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size. [ABSTRACT FROM AUTHOR]

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n. [ABSTRACT FROM AUTHOR]

Background: Two biomolecular 3-D structures are said to be similar if the RMSD (root mean square deviation) between the two molecules' sequences of 3-D coordinates is less than or equal to some given constant bound. Tools for searching for similar structures in biomolecular 3-D structure databases are becoming increasingly important in the structural biology of the post-genomic era. Results: We consider an important, fundamental problem of reporting all substructures in a 3-D structure database of chain molecules (such as proteins) which are similar to a given query 3-D structure, with consideration of indels (i.e., insertions and deletions). This problem has been believed to be very difficult but its exact computational complexity has not been known. In this paper, we first prove that the problem in unbounded dimensions is NPhard. We then propose a new algorithm that dramatically improves the average-case time complexity of the problem in 3-D in case the number of indels k is bounded by a constant. Our algorithm solves the above problem for a query of size m and a database of size N in average-case O(N) time, whereas the time complexity of the previously best algorithm was O(Nmk+1). Conclusions: Our results show that although the problem of searching for similar structures in a database based on the RMSD measure with indels is NP-hard in the case of unbounded dimensions, it can be solved in 3-D by a simple average-case linear time algorithm when the number of indels is bounded by a constant. [ABSTRACT FROM AUTHOR]

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n). [ABSTRACT FROM AUTHOR]

We propose a fast and memory-efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string matching. Our algorithm eliminates much of the overhead of previous specialized approaches while maintaining their robustness for degenerate inputs. For input size , our algorithm operates in only two integer arrays of size , and has worst-case time complexity . We demonstrate experimentally that our algorithm has stable performance compared with other approaches. [Copyright &y& Elsevier]

Let T be a string with n characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [Ferragina and Manzini 2000; Grossi and Vitter 2000]. Yet the compressed nature of such indexes also makes them difficult to update dynamically. This article extends the work on optimal-space indexing to a dynamic collection of texts. Our first result is a compressed solution to the library management problem, where we show an index of O(n) bits for a text collection L of total length n, which can be updated in O(∣T∣ log n) time when a text T is inserted or deleted from L; also, the index supports searching the occurrences of any pattern P in all texts in L in O(∣P∣ log n + occ log2 n) time, where occ is the number of occurrences. Our second result is a compressed solution to the dictionary matching problem, where we show an index of O(d) bits for a pattern collection D of total length d, which can be updated in O(∣P∣ log² d) time when a pattern P is inserted or deleted from D; also, the index supports searching the occurrences of all patterns of D in any text T in O((∣T∣+occ) log² d) time. When compared with the O(d log d)-bit suffix-tree-based solution of Amir et al. [1995], the compact solution increases the query time by roughly a factor of log d only. The solution to the dictionary matching problem is based on a new compressed representation of a suffix tree. Precisely, we give an O(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text T in O(∣T∣ log² n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. In the study of the aforementioned result, we also derive the first O(n)-bit representation for maintaining n pairs of balanced parentheses in O(log n/ log log n) time per operation, matching the time complexity of the previous O(n log n)-bit solution. [ABSTRACT FROM AUTHOR]

Abstract: We discuss the problem of computing all the integer sequences obtained by rounding an input sequence of n real numbers such that the discrepancy between the input sequence and each output binary sequence is less than one. The problem arises in the design of digital halftoning methods in computer graphics. We show that the number of such roundings is at most if we consider the discrepancy with respect to the set of all subintervals, and give an efficient algorithm to report all of them. Then, we give an optimal method to construct a compact graph to represent the set of global roundings satisfying a weaker discrepancy condition. [Copyright &y& Elsevier]

Depth-first search (DFS) is a well-known graph traversal algorithm and can be performed in O (n + m) time for a graph with n vertices and m edges. We consider the dynamic DFS problem, that is, to maintain a DFS tree of an undirected graph G under the condition that edges and vertices are gradually inserted into or deleted from G. We present an algorithm for this problem, which takes worst-case O (m n · polylog (n)) time per update and requires only (3 m + o (m)) log n bits of space. This algorithm reduces the space usage of dynamic DFS algorithm to only 1.5 times as much space as that of the adjacency list of the graph. We also show applications of our dynamic DFS algorithm to dynamic connectivity, biconnectivity, and 2-edge-connectivity problems under vertex insertions and deletions. [ABSTRACT FROM AUTHOR]

Abstract: Given a finite graph and a probability distribution on , Metropolis walks, i.e., random walks on building on the Metropolis–Hastings algorithm, obey a transition probability matrix defined by, for any , and are guaranteed to have as the stationary distribution, where is the set of adjacent vertices of and is the degree of . This paper shows that the hitting and the cover times of Metropolis walks are and , respectively, for any graph of order and any probability distribution such that . We also show that there are a graph and a stationary distribution such that any random walk on realizing attains hitting and cover times. It follows that the hitting and the cover times of Metropolis walks are and , respectively. [Copyright &y& Elsevier]

This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor O(1) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(logk) times faster (Proc. 12th Ann. ACM–SIAM Symp. on Discrete Algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only O(1) times faster. [Copyright &y& Elsevier]