Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (3 results)

  • Thesis
  • Peer Reviewed
UC Berkeley Electronic Theses and Dissertations (2015)

Since the 1920s, researchers in population genetics have developed mathematical models to explain how a species evolves. With the rise of DNA sequencing over the past decade, we now have the data to use these models to answer real questions in evolutionary biology. However, the sheer amount of data and the time complexity of the models makes inference extremely challenging. Computer science has therefore become an essential tool for bridging theoretical models and modern sequencing data.

In this thesis we present two novel algorithms that make use of DNA sequencing data in a principled yet practical way. The first method estimates the history of effective population sizes of a species using a coalescent hidden Markov model (HMM). Previous coalescent HMMs could only handle a few sequences, since the set of coalescent trees makes the state- space prohibitively large. Our algorithm uses a modified state-space to make inference computationally feasible while still retaining the essential genealogical features of a sample. We apply this algorithm, called diCal, to human data to learn more about major events in human history, such as the out-of-Africa migration. We also provide several extensions to diCal that make the computation faster, more automated, and applicable in a wider variety of scenarios.

The second method is an algorithm for jointly estimating effective population size changes and natural selection. These two factors can leave similar traces in genomic data, and the models that would describe both are computationally intractable. Our method uses a machine learning technique called deep learning to make the inference procedure robust and efficient. Deep learning automatically teases out important features of the data, but previously had not been used in population genetics. We apply this method to African Drosophila melanogaster data to jointly infer their population size changes and classify each region of their genome as neutral or under natural selection. We considered three types of selection: hard sweeps, soft sweeps, and balancing selection. To create a sophisticated framework for population genomic inference, in the future it would be promising to combine machine learning algorithms with biologically-inspired coalescent modeling.

    Cover page: Scalable Algorithms for Population Genomic Inference
    • Article
    • Peer Reviewed
    UC Berkeley Previously Published Works (2012)

    Motivation

    With advances in sequencing technology, it has become faster and cheaper to obtain short-read data from which to assemble genomes. Although there has been considerable progress in the field of genome assembly, producing high-quality de novo assemblies from short-reads remains challenging, primarily because of the complex repeat structures found in the genomes of most higher organisms. The telomeric regions of many genomes are particularly difficult to assemble, though much could be gained from the study of these regions, as their evolution has not been fully characterized and they have been linked to aging.

    Results

    In this article, we tackle the problem of assembling highly repetitive regions by developing a novel algorithm that iteratively extends long paths through a series of read-overlap graphs and evaluates them based on a statistical framework. Our algorithm, Telescoper, uses short- and long-insert libraries in an integrated way throughout the assembly process. Results on real and simulated data demonstrate that our approach can effectively resolve much of the complex repeat structures found in the telomeres of yeast genomes, especially when longer long-insert libraries are used.

    Availability

    Telescoper is publicly available for download at sourceforge.net/p/telescoper.

    Contact

    yss@eecs.berkeley.edu

    Supplementary information

    Supplementary data are available at Bioinformatics online.
      Cover page: Telescoper: de novo assembly of highly repetitive regions
      • Article
      • Peer Reviewed
      UC Berkeley Previously Published Works (2014)
      In many areas of computational biology, hidden Markov models (HMMs) have been used to model local genomic features. In particular, coalescent HMMs have been used to infer ancient population sizes, migration rates, divergence times, and other parameters such as mutation and recombination rates. As more loci, sequences, and hidden states are added to the model, however, the runtime of coalescent HMMs can quickly become prohibitive. Here we present a new algorithm for reducing the runtime of coalescent HMMs from quadratic in the number of hidden time states to linear, without making any additional approximations. Our algorithm can be incorporated into various coalescent HMMs, including the popular method PSMC for inferring variable effective population sizes. Here we implement this algorithm to speed up our demographic inference method diCal, which is equivalent to PSMC when applied to a sample of two haplotypes. We demonstrate that the linear-time method can reconstruct a population size change history more accurately than the quadratic-time method, given similar computation resources. We also apply the method to data from the 1000 Genomes project, inferring a high-resolution history of size changes in the European population.
        Cover page: Decoding Coalescent Hidden Markov Models in Linear Time
        Top