MOTIVATION: Many heuristic algorithms have been designed to approximate P-values of DNA motifs described by position weight matrices, for evaluating their statistical significance. They often significantly deviate from the true P-value by orders of magnitude. Exact P-value computation is needed for ranking the motifs. Furthermore, surprisingly, the complexity of the problem is unknown. RESULTS: We show the problem to be NP-hard, and present MotifRank, software based on dynamic programming, to calculate exact P-values of motifs. We define the exact P-value on a general and more precise model. Asymptotically, MotifRank is faster than the best exact P-value computing algorithm, and is in fact practical. Our experiments clearly demonstrate that MotifRank significantly improves the accuracy of existing approximation algorithms. AVAILABILITY: MotifRank is available from http://bio.dlg.cn. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Abstract Summary: While achieving the best compression ratios for DNA sequences, our new DNACompress program significantly improves the running time of all previous DNA compression programs. Availability: http://dna.cs.ucsb.edu/DNACompress Contact: [email protected]@cs.ucsb.edu * To whom correspondence should be addressed.

MOTIVATION: Genomics and proteomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The exploding genomic data growth presents a dilemma for DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation. RESULTS: We present a new homology search algorithm 'PatternHunter' that uses a novel seed model for increased sensitivity and new hit-processing techniques for significantly increased speed. At Blast levels of sensitivity, PatternHunter is able to find homologies between sequences as large as human chromosomes, in mere hours on a desktop. AVAILABILITY: PatternHunter is available at http://www.bioinformaticssolutions.com, as a commercial package. It runs on all platforms that support Java. PatternHunter technology is being patented; commercial use requires a license from BSI, while non-commercial use will be free.

While Kolmogorov (1965, 1983) complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data, for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. We develop the algorithmic theory of statistic, sufficient statistic, and minimal sufficient statistic. This theory is based on two-part codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the model-to-data code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. We distinguish implicit and explicit descriptions of the models. We give characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modes-in the explicit mode under some constraints. We also strengthen and elaborate on earlier results for the "Kolmogorov structure function" and "absolutely nonstochastic objects"-those objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves. We demonstrate a close relation between the probabilistic notions and the algorithmic ones: (i) in both cases there is an "information non-increase" law; (ii) it is shown that a function is a probabilistic sufficient statistic iff it is with high probability (in an appropriate sense) an algorithmic sufficient statistic.

We introduce a search problem called “mutual search” where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form “Anybody at site i ?”. We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols, we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed), there is no savings: n -1 queries are required and are sufficient. In a nonoblivious setting, we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case 0.586 n queries are required; in the asynchronous case 0.896 n queries suffice and a fortiori 0.536 n queries are required; for o(√n) agents using a synchronous deterministic protocol less than n queries suffice; there is a simple randomized protocol for two agents with worst-case expected 0.5 n queries and all radomized protocols require at least 0.25 n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.

Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of an n -user atomic variable directly from single-writer, single-reader atomic variables uses O(n) control bits and O(n) accesses per Read/Write running in O(1) parallel time.

We consider the following problem: given a collection of strings s 1 ,…, s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s . Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2 n ), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n ) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4 n . Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3 n . We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.

Article Free Access Share on Linear approximation of shortest superstrings Authors: Avrim Blum Massachusetts Institute of Technology, Cambridge, MA Massachusetts Institute of Technology, Cambridge, MAView Profile , Tao Jiang McMaster Univ., Hamilton, Ontario, CANADA McMaster Univ., Hamilton, Ontario, CANADAView Profile , Ming Li Univ. of Waterloo, Ontario, CANADA Univ. of Waterloo, Ontario, CANADAView Profile , John Tromp CWI, Amsterdam, The Netherlands CWI, Amsterdam, The NetherlandsView Profile , Mihalis Yannakakis AT&T Bell Labs. Murray Hill, NJ AT&T Bell Labs. Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 328–336https://doi.org/10.1145/103418.103455Published:03 January 1991Publication History 37citation440DownloadsMetricsTotal Citations37Total Downloads440Last 12 Months21Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF