DNA methylation is a dynamic chemical modification that is abundant on DNA sequences and plays a central role in the regulatory mechanisms of cells. This modification can be inherited across cell divisions and generations, providing a ``memory mechanism" for regulatory programs that is more flexible than that coded in the DNA sequence. In recent years, high-throughput sequencing technologies have enabled genome-wide annotation of DNA methylation. Coupled with novel computational machinery, these developments have enabled unperceivable insight to the characteristics, biological function and disease association of this phenomenon. The collaborations between experimental and computational researches who take part in these efforts has been closer than ever before due to the need to involve computational methodologies throughout the entire research pipeline, from experimental design through bias correction to the analysis of large datasets.

In the first part of this thesis we present contributions to the field of high-throughput DNA methylation. We introduce statistically sound criteria for the detection of methylation signatures in DNA sequence, and present an algorithm for the annotation of an informative non-overlapping subset of such regions that is optimal under biologically motivated assumptions. Our method outputs a sequence-generated list of regions that are of interest with respect to their methylation states. We then present a Bayesian network to infer corrected site-specific methylation states from a favorable but biased experimental method, and describe its incorporation in a software package. Along with site-specific methylation calls our package annotates experiment-specific regions of interest by considering both the methylation state inferences and the genomic sequence. These regions can serve as a basis for comparative methylation studies. In the last chapter of this section we bring results from a genome-scale comparative study conducted on humans, chimpanzees and an orangutan, providing evidence of DNA methylation differences that propagate through generations and distinguish these closely related species.

The second part of this thesis concerns error correction in high-throughput sequencing datasets. In the course of studying DNA methylation with high-throughput sequencing we discovered a systematic error that results in false-positive variant detection and can significantly affect biological inferences in a variety of genomic studies. We present a classifier to correct for such errors and show that it performs very well with respect to both sensitivity and specificity.

The first step in many metagenomic and metatranscriptomic analysis workflows is assigning high-throughput sequencing reads to specific strains or transcripts, providing the basis for identification and later quantification. However, the high degree of similarity between the sequences of many strains and genes makes it difficult to assign reads at the lowest level of taxonomy, and reads are typically assigned to more general taxonomic levels where they are unambiguous. Recent developments in RNA-Seq analysis have found direct-match k-mer based methods to be extremely accurate and fast when comparing sequenced RNA-Seq reads to transcriptomes. While similar methods have been used in metagenomics before now, none are highly accurate at distinguishing similar strains, and none have been applied to metatranscriptomic data. We explore connections between metagenomic and metatranscriptomic read assignment and the quantification of transcripts from RNA-Seq data to develop novel methods for rapid and accurate quantification of microbiome strains and transcripts.

We find that the recent idea of pseudoalignment introduced in the RNA-Seq context is highly applicable in the metagenomics and metatranscriptomics settings as well. When coupled with the Expectation-Maximization (EM) algorithm, reads can be assigned far more accurately and quickly than is currently possible with state of the art software, making it possible and practical for the first time to analyze abundances of individual genomes in metagenomics and metatranscriptomics projects.

Genes are functional units in organisms' genomes that are believed to play an important role in how organisms develop their inheritable characteristics such as eye and hair colors. One of the fundamental problems in computational biology is to predict gene functions from DNA sequence data. Researchers have developed several methods, both experimental and computational, to tackle the problem and some of those methods rely on an assumption that genes that have similar functions would likely evolve in a correlated fashion and vice versa. I aim to investigate this assumption under a statistical framework.

I define a measure that quantifies the dissimilarity level of the evolutions of any pair of genes. In order to properly define the measure, I use an evolutionary model to represent the evolution of each gene. The model essentially serves as an encoding of the distribution of all possible character sequences that could be observed at the leaf nodes of the model. Then the measure between any two evolutionary models is precisely defined as the Kullback-Leibler divergence between the two distributions, encoded by the models. Since computing the exact measures are not computationally tractable, I instead propose an efficient algorithm for estimating them. Genes' functions are determined based on the Gene Ontology consortium database. In the end, I apply statistical tests for clustering to verify if genes with correlated evolutions tend to have similar functions. I find that the hypothesis is not always true. There are some groups of genes whose functions are not correlated with their evolutions and there are some other groups of genes whose functions and evolutions are correlated well.

In addition, the methods presented in this research lay out a framework for any studies that involve quantitative analysis on genes' or proteins' evolutions. This thesis exhibits one application in this framework, which focuses solely on genes' functions. But the methods can be applied to other type of attributes such as proteins' structures.

For the last 15 years, the world's sequencing capacity has increased at a staggering rate. While the focus of much of this has been on the sequencing of genomic DNA, the sequencing of transcribed RNAs as a proxy for the expression of genes has also taken a starring role. In this thesis, we consider three themes related to these RNA-seq experiments, operating at three different levels.

We begin by considering the quantification of a single RNA-seq experiment. Here the blessing of cheap sequencing has become something of a curse as data is being generated at such a rate that analyzing that it can end up being an onerous task. To address this, we attempt to do as much as we can with very little: without aligning our sequencing data to a genome and foregoing much of the information usually utilized in RNA-seq analyses, we manage to produce quantifications of expression that are close in accuracy to those produced by state of the art, sophisticated models while using a very small fraction of their computational resources.

Next, we consider the quantification of RNA-seq datasets with many samples. While generating such datasets was previously a difficult and expensive undertaking, it is becoming increasingly routine and so the question of whether they should have their own specialized form of analysis should be addressed. In such datasets, the different samples are almost always related in some sense which creates the possibility that, rather than analyzing each sample independently, information could be shared between the analyses thereby improving the accuracy of all. To that end, we propose a method of regularizing the analysis of many sample RNA-seq inspired by techniques in machine learning and provide evidence that it may improve the accuracy many sample RNA-seq experiments which are shallowly sequenced and therefore would most likely benefit from such information sharing.

Finally, we consider some aspects of the analyzing the results of many sample RNA-seq experiments. Specifically, we consider experiments in which expression has been measured in many individuals and ask: do we see the signature of population structure in expression data, as we do in genotype data? While the question has been answered in the negative in the past, we show that more sensitive analysis reveals that population signals do indeed leave their mark on expression.

As the cost of short-read, high-throughput DNA sequencing continues to fall rapidly, new uses for the technology have been developed aside from its original purpose in determining the genome of various species. Many of these new experiments use the sequencer as a digital counter for measuring biological activities such as gene expression (RNA-Seq) or protein binding (ChIP-Seq).

A common problem faced in the analysis of these data is that of sequenced fragments that are "ambiguous", meaning they resemble multiple loci in a reference genome or other sequence. In early analyses, such ambiguous fragments were ignored or were assigned to loci using simple heuristics. However, statistical approaches using maximum likelihood estimation have been shown to greatly improve the accuracy of downstream analyses and have become widely adopted Optimization based on the expectation-maximization (EM) algorithm are often employed by these methods to find the optimal sets of alignments, with frequent enhancements to the model. Nevertheless, these improvements increase complexity, which, along with an exponential growth in the size of sequencing datasets, has led to new computational challenges.

Herein, we present our model for ambiguous fragment assignment for RNA-Seq, which includes the most comprehensive set of parameters of any model introduced to date, as well as various methods we have explored for scaling our optimization procedure. These methods include the use of an online EM algorithm and a distributed EM solution implemented on the Spark cluster computing system. Our advances have resulted in the first efficient solution to the problem of fragment assignment in sequencing.

Furthermore, we are the first to create a fully generalized model for ambiguous fragment assignment and present details on how our method can provide solutions for additional high-throughput sequencing assays including ChIP-Seq, Allele-Specific Expression (ASE), and the detection of RNA-DNA Differences (RDDs) in RNA-Seq.

Recent advances in collecting sequencing data from tumors is promising for both immediate individual patient treatment and investigation of cancer mechanisms. A resultant central goal is identifying changes in tumors that are impactful towards these ends. Here, we develop two tools to identify impactful changes at different levels. We develop both methods in the context of gliomas, a common form of brain cancer. Firstly, we develop and assess a tool for assessing the impact of fusion genes, a type of common mutation using RNA-sequencing data. We validate the tool by working with collaborators in The Cancer Genome Atlas. Secondly, we develop a tool for an overall assessment of patient outcome by integrating data from diverse sequencing platforms. We validate this tool using simulation, data from consortiums, and collaborators at UCSF.

As access to DNA sequencing has become ubiquitous to scientists, the use of sequencers has expanded from determining the genomes of individuals to performing molecular probing assays. These assays have turned DNA sequencers into molecule counting machines and can be used to measure biological activities such as gene expression (RNA-Seq), DNA accessibility (ATAC-Seq) and many others.

Each new assay poses new analytical challenges, and the main focus presented here is in analyzing RNA-Seq data.

One of the main challenges in RNA-Seq is that sequenced fragments are often ambiguous, meaning they are compatible with multiple splice forms or genomic locations.

In order to estimate gene abundances effectively, these ambiguous fragments should be used in a comprehensive model in order to not bias results.

Analysis has come a long way from ignoring ambiguous mappings, to maximum likelihood models, and even streaming models.

Advancements in these models have greatly improved the accuracy of estimating gene and transcript abundances.

In parallel, methods for determining true expression differences between experimental conditions, termed differential expression, have been developed.

Historically, these methods have mostly ignored advancements in gene expression estimation but have made much progress in between-sample variance estimation when sample sizes are small -- a common practice in this field.

Herein, we present advancements to both abundance estimation and differential expression analysis.

We show dramatic improvements to the speed of abundance estimation while maintaining accuracy.

Furthermore, we bridge these two fields by developing a differential expression model incorporating the uncertainty introduced by abundance estimation.

We show that this model outperforms existing techniques at both the transcript and gene level.

Additionally, we show that these methods can be used to address other biological questions such as the discovery of novel retained introns and estimation of their abundances.

An extension to the differential expression model is proposed to identify differences in retained intron levels while incorporating abundance estimation uncertainty.

Multicellular organisms rely on diverse cell types to carry out the multitude of tasks necessary

for complex life. Understanding the interplay between cell populations within a tissue

or organism is a major goal of biological and medical research. In pursuit of this aim, recent

advances in micro

uidics and molecular biology have propelled single-cell RNA-sequencing

(scRNA-seq) to the forefront of cell population analysis. Routine scRNA-seq experiments

can prole tens of thousands of genes from tens of thousands of cells in parallel, oering a

platform ripe for technological development, a sandbox in which a clever molecular biologist

may develop more varied experiments at unprecedented scale and depth. Accordingly, we

have made signicant inroads toward the goals of simultaneous RNA/epitope quantication

and ultra-low-cost library preparation, and we have expanded the capacity of scRNA-seq

with a novel sample multiplexing method. We demonstrate the power of parallel cell population

analysis with a high-resolution screen of experimental perturbations, introducing a

new paradigm in which scRNA-seq is used to understand a cell population at multiple scales

with unprecedented depth of information.