117 research outputs found
<i>De Novo</i> Discovery of Structured ncRNA Motifs in Genomic Sequences
No full textDe novo discovery of "motifs" capturing the commonalities among related noncoding ncRNA structured RNAs is among the most difficult problems in computational biology. This chapter outlines the challenges presented by this problem, together with some approaches towards solving them, with an emphasis on an approach based on the CMfinder CMfinder program as a case study. Applications to genomic screens for novel de novo structured ncRNA ncRNA s, including structured RNA elements in untranslated portions of protein-coding genes, are presented.</p
Faster Genome Annotation of Non-coding RNA Families without Loss of Accuracy
No full textRNA 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 rigorous 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 # Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle, WA, USA, 98195, [email protected] + Depts. of Computer Science & Engineering and Genome Sciences, University of Washington, Box 352350, Seattle, WA, USA, 98195, [email protected] c ACM, 2004. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proc. Eighth Annual Inter. Conf. on Computational Molecular Biology (RECOMB) , 2004. See http://recomb04.sdsc.edu/
Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition
No full textWe 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 realizing a full CREW-PRAM model, it is interesting to observe that in fact, most known CREW-PRAM algorithms satisfy the CROW restriction or can be easily modified to do so. This paper makes three main contributions. First, we formally define the CROW-PRAM model and demonstrate its stability Department of Computer Science, York University, Toronto, Canada M3J 1P3; [email protected]. y Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195-2350; [email protected]. z Parts of this work were done at the Department of ..
Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition
No full textWe 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 realizing a full CREW-PRAM model, it is interesting to observe that in fact, most known CREW-PRAM algorithms satisfy the CROW restriction or can be easily modified to do so. This paper makes three main contributions. First, we formally define the CROW-PRAM model and demonstrate its stability Department of Computer Science, CCB126, York University, Toronto, Canada M3J 1P3; [email protected]. y Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195-2350; [email protected]. z Parts of this work were done at the Depart..
The analysis of RNA-Seq experiments using approximate likelihood
No full textThesis (Ph.D.)--University of Washington, 2020The analysis of mRNA transcript abundance with RNA-Seq is a central tool in molecular biology research, but often analyses fail to account for the uncertainty in these estimates, which can be significant, especially when trying to disentangle isoforms or duplicated genes. Preserving uncertainty necessitates a full probabilistic model of the all the sequencing reads which quickly becomes intractable, as experiments can consist of billions of reads. To overcome these limitations, we propose a new method of approximating the likelihood function of a sparse mixture model, using a technique we call the Polya tree transformation. We demonstrate that substituting this approximation for the real thing achieves most of the benefits with a fraction of the computational costs, leading to more accurate detection of differential transcript expression
Discovery and Applications of Bacterial Noncoding RNAs
No full textThesis (Ph.D.)--University of Washington, 2012Noncoding RNAs (ncRNAs) are functional transcripts that do not code for proteins. Many of them play indispensible roles in the cell. For example, the ribosomal RNAs make up the ribosome that is the factory for making proteins and riboswitches bind to small metabolites in the cell and regulate gene expression. Computational discovery of ncRNAs is challenging, however, because ncRNAs evolve rapidly on the nucleotide level while preserving secondary structure. In the first part of this thesis, we develop two clustering algorithms that are robust to weak sequence homology signals and are applicable on the genomic scale. We show that both algorithms can recover most known ncRNA families and as few as 5 homologous sequences are needed to predict a strong motif. In the second part of the thesis, we investigate whether secondary structure in- formation improves maximum likelihood tree inference for ncRNAs. An accurate phylogenetic tree has important biological and clinical applications: it can be used to infer the function of novel organisms and understand the evolutionary history of species. We show that using structure information, a more realistic gap model, and a maximum likelihood approach improves phylogenetic tree inference. In the third part of the thesis, we develop a method for profiling human gut microbial communities using high-throughput sequencing. Our method works on Illumina short reads and does not require assembly or taxonomic identification. We show that it can differentiate between the gut microbiota of healthy individuals at low sequencing depth, making it a cost-effective screening tool for large population studies. In the final part of the thesis, we use a standard additions experiment to examine sequencing bias and errors in Illumina HiSeq. We identify features associated with systematic errors and develop an error correction pipeline. We show that our method reduces base errors and produces better species diversity estimates
RNA Structural Alignments, Part I:Sankoff-Based Approaches for Structural Alignments
No full textSimultaneous alignment and secondary structure prediction of RNA sequences is often referred to as "RNA structural alignment." A class of the methods for structural alignment is based on the principles proposed by Sankoff more than 25 years ago. The Sankoff algorithm simultaneously folds and aligns two or more sequences. The advantage of this algorithm over those that separate the folding and alignment steps is that it makes better predictions. The disadvantage is that it is slower and requires more computer memory to run. The amount of computational resources needed to run the Sankoff algorithm is so high that it took more than a decade before the first implementation of a Sankoff style algorithm was published. However, with the faster computers available today and the improved heuristics used in the implementations the Sankoff-based methods have become practical. This chapter describes the methods based on the Sankoff algorithm. All the practical implementations of the algorithm use heuristics to make them run in reasonable time and memory. These heuristics are also described in this chapter.</p
Quantifying wellness and disease with personal, dense, dynamic data clouds
No full textThesis (Ph.D.)--University of Washington, 2020Precision Medicine, where medical treatment is guided by deep molecular knowledge of the individual, has gained momentum in recent years. Rapid advancement in biological measurement technologies such as genome sequencing, mass spectrometry, protein capture assays, microfluidics and quantified-self devices provide an unprecedented opportunity to quantify, explain, and affect each person's health. The key challenge now is how to utilize these new capabilities to maximize wellness and prevent disease. These developments are concurrent with and aided by the increased availability of robust data analytic tools and cheap, scalable computation. In this dissertation, I present three steps taken to advance Precision Medicine. I present the first large multi-omic wellness study, where information from these -omics were integrated and used to provide personalized wellness guidance through a trained wellness coach. I present a holistic and modifiable wellness marker based on aging, generated from longitudinal multi-omic data. Finally, I apply systems approaches with dense phenotypic longitudinal data to profiling cancer, highlighting one approach to personalized 'N of 1' medicine. The research I present in this dissertation has led to the formation of two companies, so far
A Regression-based K nearest neighbor algorithm for gene function prediction from heterogeneous data
No full textAbstract 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.</p
- …
