Source author record

Niko Beerenwinkel

Niko Beerenwinkel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Populations and Evolution Quantitative Methods Computational Complexity Data Structures and Algorithms Genomics Machine Learning math.ST Molecular Networks Statistics Theory

Catalog footprint

What is connected

12works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

High-Dimensional Inference in Bayesian Networks

Inference of the marginal probability distribution is defined as the calculation of the probability of a subset of the variables and is relevant for handling missing data and hidden variables. While inference of the marginal probability distribution is crucial for various problems in machine learning and statistics, its exact computation is generally not feasible for categorical variables in Bayesian networks due to the NP-hardness of this task. We develop a divide-and-conquer approach using the graphical properties of Bayesian networks to split the computation of the marginal probability distribution into sub-calculations of lower dimensionality, thus reducing the overall computational complexity. Exploiting this property, we present an efficient and scalable algorithm for calculating the marginal probability distribution for categorical variables. The novel method is compared against state-of-the-art approximate inference methods in a benchmarking study, where it displays superior performance. As an immediate application, we demonstrate how our method can be used to classify incomplete data against Bayesian networks and use this approach for identifying the cancer subtype of kidney cancer patient samples.

preprint2015arXiv

Probabilistic modeling of occurring substitutions in PAR-CLIP data

Photoactivatable ribonucleoside-enhanced cross-linking and immunoprecipitation (PAR-CLIP) is an experimental method based on next-generation sequencing for identifying the RNA interaction sites of a given protein. The method deliberately inserts T-to-C substitutions at the RNA-protein interaction sites, which provides a second layer of evidence compared to other CLIP methods. However, the experiment includes several sources of noise which cause both low-frequency errors and spurious high-frequency alterations. Therefore, rigorous statistical analysis is required in order to separate true T-to-C base changes, following cross-linking, from noise. So far, most of the existing PAR-CLIP data analysis methods focus on discarding the low-frequency errors and rely on high-frequency substitutions to report binding sites, not taking into account the possibility of high-frequency false positive substitutions. Here, we introduce BMix, a new probabilistic method which explicitly accounts for the sources of noise in PAR- CLIP data and distinguishes cross-link induced T-to-C substitutions from low and high-frequency erroneous alterations. We demonstrate the superior speed and accuracy of our method compared to existing approaches on both simulated and real, publicly available human datasets. The model is implemented in the Matlab toolbox BMix, freely available at www.cbg.bsse.ethz.ch/software/BMix.

preprint2015arXiv

TiMEx: A Waiting Time Model for Mutually Exclusive Groups of Cancer Alterations

Despite recent technological advances in genomic sciences, our understanding of cancer progression and its driving genetic alterations remains incomplete. Here, we introduce TiMEx, a generative probabilistic model for detecting patterns of various degrees of mutual exclusivity across genetic alterations, which can indicate pathways involved in cancer progression. TiMEx explicitly accounts for the temporal interplay between the waiting times to alterations and the observation time. In simulation studies, we show that our model outperforms previous methods for detecting mutual exclusivity. On large-scale biological datasets, TiMEx identifies gene groups with strong functional biological relevance, while also proposing many new candidates for biological validation. TiMEx possesses several advantages over previous methods, including a novel generative probabilistic model of tumorigenesis, direct estimation of the probability of mutual exclusivity interaction, computational efficiency, as well as high sensitivity in detecting gene groups involving low-frequency alterations. R code is available at www.cbg.bsse.ethz.ch/software/TiMEx.

preprint2013arXiv

Covering Pairs in Directed Acyclic Graphs

The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths "covering" all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.

preprint2011arXiv

Competition-colonization trade-off promotes coexistence of low-virulence viral strains

RNA viruses exist as genetically diverse populations displaying different phenotypes, including diverse degrees of virulence. The evolution of virulence in viral populations is, however, poorly understood. Based on the experimental observation of an RNA virus clone in cell culture diversifying into two subpopulations of different virulence, we study the dynamics of heterogeneous virus populations and the evolution of virulence. We introduce a competition-colonization trade-off into standard mathematical models of intra-host viral infection. Colonizers are fast spreading, virulent strains, whereas competitors are less virulent variants that are more successful within coinfected cells. We observe biphasic dynamics of the population: Early in the infection the population is dominated by colonizers, which later will be outcompeted by competitors. The simulations suggest the existence of a steady state where few low-virulence variants coexist. This equilibrium implies collective virulence attenuation in the population, in contrast to previous models predicting development of the population towards increased virulence. Nevertheless, the attenuation effect disappears if we include a highly simplified immune response in our models. Thus, the competition-colonization trade-off indicates a role for virulence in the modulation of the viral population diversity. The evolution of virulence is a dynamic feature of the population shaped by interactions between individuals and by the structure of the patchy habitat.

preprint2011arXiv

Evolutionary Games with Affine Fitness Functions: Applications to Cancer

We analyze the dynamics of evolutionary games in which fitness is defined as an affine function of the expected payoff and a constant contribution. The resulting inhomogeneous replicator equation has an homogeneous equivalent with modified payoffs. The affine terms also influence the stochastic dynamics of a two-strategy Moran model of a finite population. We then apply the affine fitness function in a model for tumor-normal cell interactions to determine which are the most successful tumor strategies. In order to analyze the dynamics of concurrent strategies within a tumor population, we extend the model to a three-strategy game involving distinct tumor cell types as well as normal cells. In this model, interaction with normal cells, in combination with an increased constant fitness, is the most effective way of establishing a population of tumor cells in normal tissue.

preprint2010arXiv

The evolution of virulence in RNA viruses under a competition-colonization trade-off

RNA viruses exist in large intra-host populations which display great genotypic and phenotypic diversity. We analyze a model of viral competition between two different viral strains infecting a constantly replenished cell pool, in which we assume a trade-off between the virus' colonization skills (cell killing ability or virulence) and its local competition skills (replication performance within coinfected cells). We characterize the conditions that allow for viral spread by means of the basic reproductive number and show that a local coexistence equilibrium exists, which is asymptotically stable. At this equilibrium, the less virulent competitor has a reproductive advantage over the more virulent colonizer. The equilibria at which one strain outcompetes the other one are unstable, i.e., a second viral strain is always able to permanently invade. One generalization of the model is to consider multiple viral strains, each one displaying a different virulence. However, to account for the large phenotypic diversity in viral populations, we consider a continuous spectrum of virulences and present a continuum limit of this multiple viral strains model that describes the time evolution of an initial continuous distribution of virulence. We provide a proof of the existence of solutions of the model's equations and present numerical approximations of solutions for different initial distributions. Our simulations suggest that initial continuous distributions of virulence evolve towards a stationary distribution that is extremely skewed in favor of competitors. Consequently, collective virulence attenuation takes place. This finding may contribute to understanding the phenomenon of virulence attenuation, which has been reported in previous experimental studies.

preprint2009arXiv

Multiple Sequence Alignment System for Pyrosequencing Reads

Pyrosequencing is among the emerging sequencing techniques, capable of generating upto 100,000 overlapping reads in a single run. This technique is much faster and cheaper than the existing state of the art sequencing technique such as Sanger. However, the reads generated by pyrosequencing are short in size and contain numerous errors. Furthermore, each read has a specific position in the reference genome. In order to use these reads for any subsequent analysis, the reads must be aligned . Existing multiple sequence alignment methods cannot be used as they do not take into account the specific positions of the sequences with respect to the genome, and are highly inefficient for large number of sequences. Therefore, the common practice has been to use either simple pairwise alignment despite its poor accuracy for error prone pyroreads, or use computationally expensive techniques based on sequential gap propagation. In this paper, we develop a computationally efficient method based on domain decomposition, referred to as pyro-align, to align such large number of reads. The proposed alignment algorithm accurately aligns the erroneous reads in a short period of time, which is orders of magnitude faster than any existing method. The accuracy of the alignment is confirmed from the consensus obtained from the multiple alignments.

preprint2009arXiv

Waiting time models of cancer progression

Cancer progression is an evolutionary process that is driven by mutation and selection in a population of tumor cells. We discuss mathematical models of cancer progression, starting from traditional multistage theory. Each stage is associated with the occurrence of genetic alterations and their fixation in the population. We describe the accumulation of mutations using conjunctive Bayesian networks, an exponential family of waiting time models in which the occurrence of mutations is constrained to a partial temporal order. Two opposing limit cases arise if mutations either follow a linear order or occur independently. We derive exact analytical expressions for the waiting time until a specific number of mutations have accumulated in these limit cases as well as for the general conjunctive Bayesian network. Finally, we analyze a stochastic population genetics model that explicitly accounts for mutation and selection. In this model, waves of clonal expansions sweep through the population at equidistant intervals. We present an approximate analytical expression for the waiting time in this model and compare it to the results obtained for the conjunctive Bayesian networks.

preprint2008arXiv

Viral population estimation using pyrosequencing

The diversity of virus populations within single infected hosts presents a major difficulty for the natural immune response as well as for vaccine design and antiviral drug therapy. Recently developed pyrophosphate based sequencing technologies (pyrosequencing) can be used for quantifying this diversity by ultra-deep sequencing of virus samples. We present computational methods for the analysis of such sequence data and apply these techniques to pyrosequencing data obtained from HIV populations within patients harboring drug resistant virus strains. Our main result is the estimation of the population structure of the sample from the pyrosequencing reads. This inference is based on a statistical approach to error correction, followed by a combinatorial algorithm for constructing a minimal set of haplotypes that explain the data. Using this set of explaining haplotypes, we apply a statistical model to infer the frequencies of the haplotypes in the population via an EM algorithm. We demonstrate that pyrosequencing reads allow for effective population reconstruction by extensive simulations and by comparison to 165 sequences obtained directly from clonal sequencing of four independent, diverse HIV populations. Thus, pyrosequencing can be used for cost-effective estimation of the structure of virus populations, promising new insights into viral evolutionary dynamics and disease control strategies.

preprint2007arXiv

Genetic progression and the waiting time to cancer

Cancer results from genetic alterations that disturb the normal cooperative behavior of cells. Recent high-throughput genomic studies of cancer cells have shown that the mutational landscape of cancer is complex and that individual cancers may evolve through mutations in as many as 20 different cancer-associated genes. We use data published by Sjoblom et al. (2006) to develop a new mathematical model for the somatic evolution of colorectal cancers. We employ the Wright-Fisher process for exploring the basic parameters of this evolutionary process and derive an analytical approximation for the expected waiting time to the cancer phenotype. Our results highlight the relative importance of selection over both the size of the cell population at risk and the mutation rate. The model predicts that the observed genetic diversity of cancer genomes can arise under a normal mutation rate if the average selective advantage per mutation is on the order of 1%. Increased mutation rates due to genetic instability would allow even smaller selective advantages during tumorigenesis. The complexity of cancer progression thus can be understood as the result of multiple sequential mutations, each of which has a relatively small but positive effect on net cell growth.

preprint2006arXiv

A Mutagenetic Tree Hidden Markov Model for Longitudinal Clonal HIV Sequence Data

RNA viruses provide prominent examples of measurably evolving populations. In HIV infection, the development of drug resistance is of particular interest, because precise predictions of the outcome of this evolutionary process are a prerequisite for the rational design of antiretroviral treatment protocols. We present a mutagenetic tree hidden Markov model for the analysis of longitudinal clonal sequence data. Using HIV mutation data from clinical trials, we estimate the order and rate of occurrence of seven amino acid changes that are associated with resistance to the reverse transcriptase inhibitor efavirenz.