Search

In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection $\mathcal {G}$ G of $t$ t sequences $\mathcal {S}_{i}$ S i of length $n$ n each, we can represent $\mathcal {G}$ G succinctly in $2n\mathcal {H}_{k}(\mathcal {T}) + \mathcal {O}(n^{\prime }\ {\log \log n}) + o(q n^{\prime }) + o(tn)$ 2 n H k (T) + O (n ' log log n) + o (q n ') + o (t n) bits using $\mathcal {O}(t n^{2} + q n^{\prime })$ O (t n 2 + q n ') time, where $\mathcal {H}_{k}(\mathcal {T})$ H k (T) is the $k$ k th-order empirical entropy of the sequence $\mathcal {T} \in \mathcal {G}$ T ∈ G that is used as the reference sequence, $n^{\prime }$ n ' is the total number of variations between $\mathcal {T}$ T and the sequences in $\mathcal {G}$ G , and $q$ q is a small fixed constant. We can restore any length $ {len}$ l e n substring $\mathcal {S}[ {sp}, \dots, {sp} + {len}-1]$ S [ s p , ⋯ , s p + l e n - 1 ] of $\mathcal {S} \in \mathcal {G}$ S ∈ G in $\mathcal {O}\bigl (n_{s}^{\prime } + {len}(\log n)^{2} / {\log \log n}\bigr)$ O n s ' + l e n (log n) 2 / log log n time and report all positions where $P$ P occurs in $\mathcal {G}$ G in $\mathcal {O}\bigl (m \cdot t + {occ} \cdot t \cdot (\log n)^{2}/\log \log n \bigr)$ O m · t + o c c · t · (log n) 2 / log log n time. In addition, we propose a dynamic programming method to find the variations between $\mathcal {T}$ T and the sequences in $\mathcal {G}$ 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. [ABSTRACT FROM AUTHOR]

Graph similarity search under the graph edit distance constraint has received considerable attention in many applications, such as bioinformatics, data mining, pattern recognition and social networks. Existing methods for this problem have limited scalability because of the huge amount of memory they consume when handling very large graph databases with tens of millions of graphs. In this article, we present a succinct index that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5–15 percent of the previous state-of-the-art indexing size while at the same time achieving several times acceleration in query time on the tested data. We also improve the query performance by augmenting the global filter with range searching, which allows us to perform similarity search in a reduced region. In addition, we propose two effective lower bounds together with a boosting technique to obtain the smallest possible candidate set. Extensive experiments demonstrate that our proposed approach is superior both in space and filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index for this problem that successfully scales to cope with the large dataset of 25 million chemical structure graphs from the PubChem dataset. The source code is available online. [ABSTRACT FROM AUTHOR]

The planted (l,d) motif discovery has been successfully used to locate transcription factor binding sites in dozens of promoter sequences over the past decade. However, there has not been enough work done in identifying (l,d) motifs in the next-generation sequencing (ChIP-seq) data sets, which contain thousands of input sequences and thereby bring new challenge to make a good identification in reasonable time. To cater this need, we propose a new planted (l,d) motif discovery algorithm named MCES, which identifies motifs by mining and combining emerging substrings. Specially, to handle larger data sets, we design a MapReduce-based strategy to mine emerging substrings distributedly. Experimental results on the simulated data show that i) MCES is able to identify (l,d) motifs efficiently and effectively in thousands to millions of input sequences, and runs faster than the state-of-the-art (l,d) motif discovery algorithms, such as F-motif and TraverStringsR; ii) MCES is able to identify motifs without known lengths, and has a better identification accuracy than the competing algorithm CisFinder. Also, the validity of MCES is tested on real data sets. MCES is freely available at http://sites.google.com/site/feqond/mces. [ABSTRACT FROM PUBLISHER]

In recent years, there has been an increasing interest in planted (l, d) motif search (PMS) with applications to discovering significant segments in biological sequences. However, there has been little discussion about PMS over large alphabets. This paper focuses on motif stem search (MSS), which is recently introduced to search motifs on large-alphabet inputs. A motif stem is an l-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all (l , d) motifs present in the input sequences, and the superset is expected to be as small as possible. The three main contributions of this paper are as follows: (1) We build motif stem representation more precisely by using regular expressions. (2) We give a method for generating all possible motif stems without redundant wildcards. (3) We propose an efficient exact algorithm, called StemFinder, for solving the MSS problem. Compared with the previous MSS algorithms, StemFinder runs much faster and reports fewer stems which represent a smaller superset of all (l, d) motifs. StemFinder is freely available at http://sites.google.com/site/feqond/stemfinder. [ABSTRACT FROM PUBLISHER]

We investigate the problem of smoothing multiplexed network traffic when either a streaming server transmits data to multiple clients or a storage server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. Possible applications include improvement in the bandwidth utilization of network links and reduction in the energy consumption of server hosts. In the data transmission problem, we consider the case in which the clients have different buffer capacities and unlimited bandwidth constraints or unlimited buffer capacities and different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule. By provably minimizing the variance of the required aggregate bandwidth, lexicographically optimal smoothing makes the maximum resource requirements within the network more predictable and increases the useful resource utilization. It also improves fairness in sharing a network link among multiple users and makes new requests from future clients more likely to be successfully admitted without the need for rescheduling previously accepted traffic. With appropriate hardware and system support, data traffic smoothing can also reduce the energy consumption of the host processor and the communication links. Overall, we expect that efficient resource management at the network edges will better meet quality of service requirements without restricting the scalability of the system. [ABSTRACT FROM AUTHOR]

Introduces an interactive recovery package called Undo,Skip, & Redo (US&R). Ability of the undo/redo facilities to recover from unforseen errors; Features of the package; Implementation of US&R.

Examines the effects of choice motion vector on rate and distortion on videophone and videoconferencing applications, where low bit rates are necessary. Comparison of the use of block-matching motion compensation, rate-distortion and motion estimation algorithms within the H.261 standards techniques; Correlation between successive frames of a video sequence by coding motion vectors; Examination of the combined techniques; Results from the examination.

Finding repetitive structures in genomes and proteins is important to understand their biological functions. Many data compressors for modern genomic sequences rely heavily on finding repeats in the sequences. Small-scale and local repetitive structures are better understood than large and complex interspersed ones. The notion of maximal repeats captures all the repeats in the data in a space-efficient way. Prior work on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. We focus on finding all the maximal repeats from massive texts in a time- and space-efficient manner. Our technique uses the Burrows-Wheeler Transform and wavelet trees. For data sets consisting of natural language texts and protein data, the space usage of our method is no more than three times the text size. For genomic sequences stored using one byte per base, the space usage of our method is less than double the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external memory. For the first time, our method enables a desktop computer with 8 GB internal memory (actual internal memory usage is less than 6 GB) to find all the maximal repeats in the whole human genome in less than 17 hours. We have implemented our method as general-purpose open-source software for public use. [ABSTRACT FROM PUBLISHER]