MOTIVATION: High-throughput ChIP-seq studies typically identify thousands of peaks for a single transcription factor (TF). It is common for traditional motif discovery tools to predict motifs that are statistically significant against a naïve background distribution but are of questionable biological relevance. RESULTS: We describe a simple yet effective algorithm for discovering differential motifs between two sequence datasets that is effective in eliminating systematic biases and scalable to large datasets. Tested on 207 ENCODE ChIP-seq datasets, our method identifies correct motifs in 78% of the datasets with known motifs, demonstrating improvement in both accuracy and efficiency compared with DREME, another state-of-art discriminative motif discovery tool. More interestingly, on the remaining more challenging datasets, we identify common technical or biological factors that compromise the motif search results and use advanced features of our tool to control for these factors. We also present case studies demonstrating the ability of our method to detect single base pair differences in DNA specificity of two similar TFs. Lastly, we demonstrate discovery of key TF motifs involved in tissue specification by examination of high-throughput DNase accessibility data. AVAILABILITY: The motifRG package is publically available via the bioconductor repository. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Over the last decade, the number of known biologically important non-coding RNAs (ncRNAs) has increased by orders of magnitude. The function performed by a specific ncRNA is partially determined by its structure, defined by which nucleotides of the molecule form pairs. These correlations may span large and variable distances in the linear RNA molecule. Because of these characteristics, algorithms that search for ncRNAs belonging to known families are computationally expensive, often taking many CPU weeks to run. To improve the speed of this search, multiple search algorithms arranged into a series of progressively more stringent filters can be used. In this paper, we present an FPGA based implementation of some of these algorithms. This is the first FPGA based approach to attempt to accelerate multiple filters used in ncRNA search. The FPGA is reconfigured for each filter, resulting in a total system speedup of 25x when compared with a single CPU.

Bioinformatics is an emerging field with seemingly limitless possibilities for advances in numerous areas of research and applications. We propose a scalable FPGA-based solution to the short read mapping problem in DNA sequencing, which greatly accelerates the task of aligning short length reads to a known reference genome. We compare the runtime, power consumption, and sensitivity of the hardware system to the BFAST and Bowtie software tools. The hardware system demonstrates a 250X speedup versus BFAST and a 31X speedup versus Bowtie on eight CPU cores. Also, the hardware system is more sensitive than Bowtie, which aligns approximately 80% of the short reads, as compared to 91% aligned by the hardware.

MOTIVATION: Quantification of sequence abundance in RNA-Seq experiments is often conflated by protocol-specific sequence bias. The exact sources of the bias are unknown, but may be influenced by polymerase chain reaction amplification, or differing primer affinities and mixtures, for example. The result is decreased accuracy in many applications, such as de novo gene annotation and transcript quantification. RESULTS: We present a new method to measure and correct for these influences using a simple graphical model. Our model does not rely on existing gene annotations, and model selection is performed automatically making it applicable with few assumptions. We evaluate our method on several datasets, and by multiple criteria, demonstrating that it effectively decreases bias and increases uniformity. Additionally, we provide theoretical and empirical results showing that the method is unlikely to have any effect on unbiased data, suggesting it can be applied with little risk of spurious adjustment. AVAILABILITY: The method is implemented in the seqbias R/Bioconductor package, available freely under the LGPL license from http://bioconductor.org CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Assessing the statistical significance of structured RNA predicted from multiple sequence alignments relies on the existence of a good null model. We present here a random shuffling algorithm, Multiperm, that preserves not only the gap and local conservation structure in alignments of arbitrarily many sequences, but also the approximate dinucleotide frequencies. No shuffling algorithm that simultaneously preserves these three characteristics of a multiple (beyond pairwise) alignment has been available to date. As one benchmark, we show that it produces shuffled exonic sequences having folding free energy closer to native sequences than shuffled alignments that do not preserve dinucleotide frequencies. AVAILABILITY: The Multiperm GNU Cb++ source code is available at http://www.anandam.name/multiperm

BACKGROUND: Multiple alignment of homologous DNA sequences is of great interest to biologists since it provides a window into evolutionary processes. At present, the accuracy of whole-genome multiple alignments, particularly in noncoding regions, has not been thoroughly evaluated. RESULTS: We evaluate the alignment accuracy of certain noncoding regions using noncoding RNA alignments from Rfam as a reference. We inspect the MULTIZ 17-vertebrate alignment from the UCSC Genome Browser for all the human sequences in the Rfam seed alignments. In particular, we find 638 instances of chimeric and partial alignments to human noncoding RNA elements, of which at least 225 can be improved by straightforward means. As a byproduct of our procedure, we predict many novel instances of known ncRNA families that are suggested by the alignment. CONCLUSION: MULTIZ does a fairly accurate job of aligning these genomes in these difficult regions. However, our experiments indicate that better alignments exist in some regions.

Noncoding RNAs (ncRNAs) are important functional RNAs that do not code for proteins. We present a highly efficient computational pipeline for discovering cis-regulatory ncRNA motifs de novo. The pipeline differs from previous methods in that it is structure-oriented, does not require a multiple-sequence alignment as input, and is capable of detecting RNA motifs with low sequence conservation. We also integrate RNA motif prediction with RNA homolog search, which improves the quality of the RNA motifs significantly. Here, we report the results of applying this pipeline to Firmicute bacteria. Our top-ranking motifs include most known Firmicute elements found in the RNA family database (Rfam). Comparing our motif models with Rfam's hand-curated motif models, we achieve high accuracy in both membership prediction and base-pair-level secondary structure prediction (at least 75% average sensitivity and specificity on both tasks). Of the ncRNA candidates not in Rfam, we find compelling evidence that some of them are functional, and analyze several potential ribosomal protein leaders in depth.

MOTIVATION: Non-coding RNAs (ncRNAs) are functional RNA molecules that do not code for proteins. Covariance Models (CMs) are a useful statistical tool to find new members of an ncRNA gene family in a large genome database, using both sequence and, importantly, RNA secondary structure information. Unfortunately, CM searches are extremely slow. Previously, we created rigorous filters, which provably sacrifice none of a CM's accuracy, while making searches significantly faster for virtually all ncRNA families. However, these rigorous filters make searches slower than heuristics could be. RESULTS: In this paper we introduce profile HMM-based heuristic filters. We show that their accuracy is usually superior to heuristics based on BLAST. Moreover, we compared our heuristics with those used in tRNAscan-SE, whose heuristics incorporate a significant amount of work specific to tRNAs, where our heuristics are generic to any ncRNA. Performance was roughly comparable, so we expect that our heuristics provide a high-quality solution that--unlike family-specific solutions--can scale to hundreds of ncRNA families. AVAILABILITY: The source code is available under GNU Public License at the supplementary web site.

MOTIVATION: The recent discoveries of large numbers of non-coding RNAs and computational advances in genome-scale RNA search create a need for tools for automatic, high quality identification and characterization of conserved RNA motifs that can be readily used for database search. Previous tools fall short of this goal. RESULTS: CMfinder is a new tool to predict RNA motifs in unaligned sequences. It is an expectation maximization algorithm using covariance models for motif description, featuring novel integration of multiple techniques for effective search of motif space, and a Bayesian framework that blends mutual information-based and folding energy-based approaches to predict structure in a principled way. Extensive tests show that our method works well on datasets with either low or high sequence similarity, is robust to inclusion of lengthy extraneous flanking sequence and/or completely unrelated sequences, and is reasonably fast and scalable. In testing on 19 known ncRNA families, including some difficult cases with poor sequence conservation and large indels, our method demonstrates excellent average per-base-pair accuracy--79% compared with at most 60% for alternative methods. More importantly, the resulting probabilistic model can be directly used for homology search, allowing iterative refinement of structural models based on additional homologs. We have used this approach to obtain highly accurate covariance models of known RNA motifs based on small numbers of related sequences, which identified homologs in deeply-diverged species.

BACKGROUND: As a variety of functional genomic and proteomic techniques become available, there is an increasing need for functional analysis methodologies that integrate heterogeneous data sources. METHODS: In this paper, we address this issue by proposing a general framework for gene function prediction based on the k-nearest-neighbor (KNN) algorithm. The choice of KNN is motivated by its simplicity, flexibility to incorporate different data types and adaptability to irregular feature spaces. A weakness of traditional KNN methods, especially when handling heterogeneous data, is that performance is subject to the often ad hoc choice of similarity metric. To address this weakness, we apply regression methods to infer a similarity metric as a weighted combination of a set of base similarity measures, which helps to locate the neighbors that are most likely to be in the same class as the target gene. We also suggest a novel voting scheme to generate confidence scores that estimate the accuracy of predictions. The method gracefully extends to multi-way classification problems. RESULTS: We apply this technique to gene function prediction according to three well-known Escherichia coli classification schemes suggested by biologists, using information derived from microarray and genome sequencing data. We demonstrate that our algorithm dramatically outperforms the naive KNN methods and is competitive with support vector machine (SVM) algorithms for integrating heterogenous data. We also show that by combining different data sources, prediction accuracy can improve significantly CONCLUSION: Our extension of KNN with automatic feature weighting, multi-class prediction, and probabilistic inference, enhance prediction accuracy significantly while remaining efficient, intuitive and flexible. This general framework can also be applied to similar classification problems involving heterogeneous datasets.

Non-coding RNAs (ncRNAs) are functional RNA molecules that do not code for proteins. Covariance Models (CMs) are a useful statistical tool to find new members of an ncRNA gene family in a large genome database, using both sequence and, importantly, RNA secondary structure information. Unfortunately, CM searches are slow. This paper shows how to make CMs faster while provably sacrificing none of their accuracy. Specifically, based on the CM, our software builds a profile hidden Markov model (HMM), which filters the genome database. This HMM is a gorous filter i.e., its filtering eliminates only sequences that provably could not be annotated as homologs. The CM is run only on what remains. Optimizing the HMM for filtering involves minimizing an exponential objective function with linear inequality constraints. For most known ncRNA families, this allows an 8-gigabase database to be scanned in 2-20 days instead of years, and yields new family members missed by other techniques to improve CM speed.

MOTIVATION: Clustering is a useful exploratory technique for the analysis of gene expression data. Many different heuristic clustering algorithms have been proposed in this context. Clustering algorithms based on probability models offer a principled alternative to heuristic algorithms. In particular, model-based clustering assumes that the data is generated by a finite mixture of underlying probability distributions such as multivariate normal distributions. The issues of selecting a 'good' clustering method and determining the 'correct' number of clusters are reduced to model selection problems in the probability framework. Gaussian mixture models have been shown to be a powerful tool for clustering in many applications. RESULTS: We benchmarked the performance of model-based clustering on several synthetic and real gene expression data sets for which external evaluation criteria were available. The model-based approach has superior performance on our synthetic data sets, consistently selecting the correct model and the number of clusters. On real expression data, the model-based approach produced clusters of quality comparable to a leading heuristic clustering algorithm, but with the key advantage of suggesting the number of clusters and an appropriate model. We also explored the validity of the Gaussian mixture assumption on different transformations of real data. We also assessed the degree to which these real gene expression data sets fit multivariate Gaussian distributions both before and after subjecting them to commonly used data transformations. Suitably chosen transformations seem to result in reasonable fits. AVAILABILITY: MCLUST is available at http://www.stat.washington.edu/fraley/mclust. The software for the diagonal model is under development. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: http://www.cs.washington.edu/homes/kayee/model.

Abstract Motivation: Many clustering algorithms have been proposed for the analysis of gene expression data, but little guidance is available to help choose among them. We provide a systematic framework for assessing the results of clustering algorithms. Clustering algorithms attempt to partition the genes into groups exhibiting similar patterns of variation in expression level. Our methodology is to apply a clustering algorithm to the data from all but one experimental condition. The remaining condition is used to assess the predictive power of the resulting clusters—meaningful clusters should exhibit less variation in the remaining condition than clusters formed by chance. Results: We successfully applied our methodology to compare six clustering algorithms on four gene expression data sets. We found our quantitative measures of cluster quality to be positively correlated with external standards of cluster quality. Availability: The software is under development. Contact: [email protected] Supplementary information: http://www.cs.washington.edu/homes/kayee/cluster or http://www.cs.washington.edu/homes/ruzzo/cluster * To whom correspondence should be addressed.

MOTIVATION: There is a great need to develop analytical methodology to analyze and to exploit the information contained in gene expression data. Because of the large number of genes and the complexity of biological networks, clustering is a useful exploratory technique for analysis of gene expression data. Other classical techniques, such as principal component analysis (PCA), have also been applied to analyze gene expression data. Using different data analysis techniques and different clustering algorithms to analyze the same data set can lead to very different conclusions. Our goal is to study the effectiveness of principal components (PCs) in capturing cluster structure. Specifically, using both real and synthetic gene expression data sets, we compared the quality of clusters obtained from the original data to the quality of clusters obtained after projecting onto subsets of the principal component axes. RESULTS: Our empirical study showed that clustering with the PCs instead of the original variables does not necessarily improve, and often degrades, cluster quality. In particular, the first few PCs (which contain most of the variation in the data) do not necessarily capture most of the cluster structure. We also showed that clustering with PCs has different impact on different algorithms and different similarity metrics. Overall, we would not recommend PCA before clustering except in special circumstances.

We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, Owner Write, or CROW-PRAMS, these are machines in which each global memory location is assigned a unique “owner” processor, which is the only processor allowed to write into it. Considering the difficulties that would be involved in physically realizinga full CREW-PRAM model and demonstrate its stability under several definitional changes. Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time O (log n) (and implicity with a polynomial number of processors) is exactly the class LOGDCFL of languages log space reducible to deterministic context-free languages. Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log n space work tape, and pushdown store of small maximum height. For example, time O ( n 1 + ε ) is achievable with pushdown height O (log 2 n ). These result extend and unify work of von Braunmöhl, Cook, Mehlhorn, and Verbeek, Klein and Reif; and Rytter.

We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "jumping automata for graphs."

Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time algorithm for directed s-t connectivity. For n-vertex graphs, our algorithm can use as little as $n/2^{\Theta(\sqrt{\log n})}$ space while still running in polynomial time.

The s-t connectivity problem for undirected graphs

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A.Z. Broder et al. (1989). The models used are variants of S.A. Cook and C.W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated.>

We introduce a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines.We prove that under our model, the overhead experienced in scheduling an n x n grid graph is O(loglogn) for p processors, p > 2. We also prove a matching lower bound of Q(loglog n) for p processors, p 1 2. We give an extension of the model to cover the case where the processors can have varying speed or are subject to delay.

Article Free Access Share on The power of parallel pointer manipulation Authors: T. W. Lam Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong Kong Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong KongView Profile , W. L. Ruzzo Computer Science Department, University of Washington, Seattle, WA Computer Science Department, University of Washington, Seattle, WAView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 92–102https://doi.org/10.1145/72935.72946Published:01 March 1989Publication History 6citation235DownloadsMetricsTotal Citations6Total Downloads235Last 12 Months12Last 6 weeks4 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

Universal traversal sequences for d-regular n-vertex graphs require length Ω(d2n2 + dn2 log n/d), for 3 ≤ d ≤ n/3 - 2. This is nearly tight for d = Θ(n). We also introduce and study several variations on the problem, e.g. edge-universal traversal sequences, showing how improved lower bounds on these would improve the bounds given above.

View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] that nondeterministic space-bounded complexity classes are closed under complementation, two further applications of the inductive counting technique are developed. First, an errorless probabilistic algorithm for the undirected graph s-t connectivity problem that runs in $O(\log n)$ space and polynomial expected time is given. Then it is shown that the class LOGCFL is closed under complementation. The latter is a special case of a general result that shows closure under complementation of classes defined by semi-unbounded fan-in circuits (or, equivalently, nondeterministic auxiliary pushdown automata or tree-size bounded alternating Turing machines). As one consequence, it is shown that small numbers of “role switches” in two-person pebbling can be eliminated.

Previous article Full AccessErratum: Two Applications of Indctive Counting for Complementation ProblemsAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin TompaAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompahttps://doi.org/10.1137/0218084PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Two Applications of Indctive Counting for Complementation Problems." SIAM Journal on Computing, 18(6), p. 1283[1] Allan Borodin, , Stephen A. Cook, , Patrick W. Dymond, , Walter L. Ruzzo and , Martin Tompa, Two applications of inductive counting for complementation problems, SIAM J. Comput., 18 (1989), 559–578 10.1137/0218038 90k:68049a 0678.68031 LinkISIGoogle Scholar[2] John Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6 (1977), 675–695 10.1137/0206049 57:4616 0366.02024 LinkISIGoogle Scholar[3] Hermann Jung, On probabilistic time and spaceAutomata, languages and programming (Nafplion, 1985), Lecture Notes in Comput. Sci., Vol. 194, Springer, Berlin, 1985, 310–317 87b:68039 0599.68043 CrossrefGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Dual VP Classes23 September 2016 | computational complexity, Vol. 26, No. 3 Cross Ref Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages Cross Ref Computational Complexity Cross Ref Trading Space for Time in Undirected s-t ConnectivityAndrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal31 July 2006 | SIAM Journal on Computing, Vol. 23, No. 2AbstractPDF (1266 KB)My favorite ten complexity theorems of the past decade1 June 2005 Cross Ref Lower bounds on the length of universal traversal sequencesJournal of Computer and System Sciences, Vol. 45, No. 2 Cross Ref A very hard log space counting class Cross Ref Volume 18, Issue 6| 1989SIAM Journal on Computing History Submitted:03 August 1989Accepted:30 August 1989Published online:13 July 2006 InformationCopyright © 1989 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0218084Article page range:pp. 1283-1283ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

This paper studies two aspects of the power of space-bounded probabilistic Turing machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. Section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic Turing machine with small error; this is a generalization of Gill's result that any language in NSPACE(log n) can be recognized by such a machine

Information is not transferred instantaneously; there is always a propagation delay before an output is available as an input to the next computational step. Propagation delay is a function of wire length, so we study the length of edges in planar graphs. We prove matching (to within a constant factor) upper and lower bounds on minimax edge length for four planar embedding problems for complete binary trees. (The results are summarized in Table 1.) Because trees are often subcircuits of larger circuits, these results imply general performance limits due to propagation delay. The results give important information for the popular technique of pipelining.

A new algorithm for recognizing and parsing arbitrary context-free languages is presented, and several new results are given on the computational complexity of these problems. The new algorithm is of both practical and theoretical interest. It is conceptually simple and allows a variety of efficient implementations, which are worked out in detail. Two versions are given which run in faster than cubic time. Surprisingly close connections between the Cocke-Kasami-Younger and Earley algorithms are established which reveal that the two algorithms are “almost” identical.

We consider uniform circuit complexity, introduced by Borodin as a model of parallel complexity. Three main results are presented. First, we show that simultaneous size/depth of uniform circuits is the same as space/time of alternating Turing machines, with depth and time within a constant factor and likewise log(size) and space. Second, we apply this to characterize the class of polynomial size and polynomial-in-log depth circuits in terms of tree-size bounded alternating TM's, in particular showing that context-free recognition is in this class of circuits. Third, we investigate various definitions of uniform circuit complexity, showing that it is fairly insensitive to the choice of definition.

The size of an accepting computation tree of an alternating Turing machine (ATM) is introduced as a complexity measure. Tree-size on ATM's is shown to closely correspond to time on nondeterministic TM's and on nondeterministic auxiliary pushdown automata. The later gives a useful new characterization of the class of languages log-space-reducible to context-free languages. Relationships with parallel-time complexity are also explored. ATM computations using at most space S(n) and tree-size Z(n) (simultaneously) can be simulated in alternating time S(n).log Z(n). Several well-known simulations, e.g., Savitch's theorem, are special cases of this result. It also leads to improved parallel-time bounds for many problems, e.g., context-free language recognition in time 0(log2n) on several parallel models.

A new on-line context free language recognition algorithm is presented which is derived from Earley's algorithm and has several advantages over the original. First, the new algorithm not only is conceptually simpler than Earley's, but also allows significant speed improvements. Second, our algorithm serves to explain the connections between Earley's algorithm and the Cocke-Kasami-Younger algorithm. Third, our algorithm allows an implementation which uses only 0(n2/log n) operations on bit vectors of length n, or 0(n3/log n) operations on a RAM. This makes it the fastest known on-line context free language recognition algorithm.

A model of protection mechanisms in computing systems is presented and its appropriateness is demonstrated. The “safety” problem for protection systems under our model is to determine in a given situation whether a subject can acquire a particular right to an object. In restricted cases, one can show that this problem is decidable, i.e., there is an algorithm to determine whether a system in a particular configuration is safe. In general, and under surprisingly weak assumptions, one cannot decide if a situation is safe. Various implications of this fact are discussed.