The rapid replication and high mutation rates of viruses like HIV lead to the formation of a community of highly similar genomes, referred to as a viral quasispecies, in an infected individual. Next-generation sequencing technologies enable researchers to sequence a complete quasispecies community with reduced expense and effort compared to traditional sequencing methods. However, typical sequence assembly software is designed to reconstruct a single genome from sequencing reads rather than a community of highly similar genomes. We describe and implement a de novo assembly method for reconstructing variants from a quasispecies community using de Bruijn graphs and a novel, heuristic path-construction method designed to identify corresponding variations at long distances across the genome. We predict the relative abundance of reconstructed variants using an approach inspired from Markov chains.

The rapid replication and high mutation rates of viruses like HIV lead to the formation of a community of highly similar genomes, referred to as a viral quasispecies, in an infected individual. Next-generation sequencing technologies enable researchers to sequence a complete quasispecies community with reduced expense and effort compared to traditional sequencing methods. However, typical sequence assembly software is designed to reconstruct a single genome from sequencing reads rather than a community of highly similar genomes. We describe and implement a de novo assembly method for reconstructing variants from a quasispecies community using de Bruijn graphs and a novel, heuristic path-construction method designed to identify corresponding variations at long distances across the genome. We predict the relative abundance of reconstructed variants using an approach inspired from Markov chains.

No description available.

No description available.

Nesta tese propomos e estudamos um modelo alternativo para investigar a evolução de quase-espécies moleculares, no qual supomos que a população seja uma combinação aleatória das moléculas constituintes em cada geração. Essa aleatoriedade deve-se a inclusão de um procedimento adicional de amostragem da população além dos procedimentos usuais de mutação e reprodução diferenciada. O modelo, denominado modelo de amostragens, é baseado em um algoritmo que mimetiza procedimentos experimentais que usam técnicas de transferências em série para reproduzir o processo de evolução de microorganismos in vitro. Além do modelo reproduzir a solução exata do estado estacionário do modelo de quase-espécies no regime determinístico, ele permite o estudo da evolução da quase-espécie molecular em todo espaço de parâmetros de controle, incluindo o caso em que a população é finita. A generalização dessa formulação alternativa para uma classe geral de relevos de replicação permite-nos realizar um estudo bastante completo do fenômeno do limiar de erro, levando-nos a uma análise crítica sobre a generalidade desse fenômeno / In this thesis we propose and study an alternative model to investigate the evolution of a molecular quasispecies, in which we assume that the population is a random combination of the constituent molecules in each generation. This randomness is due to the inclusion of an additional sampling procedure of the population, besides the usual procedures of mutation and differential reprodution. This model, termed sampling model, is based on an algorithm that mimics experimental procedures using serial transfer techniques to study the microbial evolutionary process in vitro. Besides yielding the exact steady-state solution of the quasispecies model in the deterministic limit, the sampling model allows the study of the molecular evolution in the full space of the control parameter, including the case where of population is finite. The generalization of this alternative formulation to a general class of fitness landscapes, allows us to investigate thoroughly the error threshold phenomenon, leading us to discuss critically the generality of this phenomenon in molecular evolution

The genomic diversity of viral quasispecies is a subject of great interest, especially for chronic infections. Characterization of viral diversity can be addressed by high-throughput sequencing technology (454 Life Sciences, Illumina, SOLiD, Ion Torrent, etc.). Standard assembly software was originally designed for single genome assembly and cannot be used to assemble and estimate the frequency of closely related quasispecies sequences. This work focuses on parsimonious and maximum likelihood models for assembling viral quasispecies and estimating their frequencies from 454 sequencing data. Our methods have been applied to several RNA viruses (HCV, IBV) as well as DNA viruses (HBV), genotyped using 454 Life Sciences amplicon and shotgun methods.

The genomic diversity of viral quasispecies is a subject of great interest, especially for chronic infections. Characterization of viral diversity can be addressed by high-throughput sequencing technology (454 Life Sciences, Illumina, SOLiD, Ion Torrent, etc.). Standard assembly software was originally designed for single genome assembly and cannot be used to assemble and estimate the frequency of closely related quasispecies sequences. This work focuses on parsimonious and maximum likelihood models for assembling viral quasispecies and estimating their frequencies from 454 sequencing data. Our methods have been applied to several RNA viruses (HCV, IBV) as well as DNA viruses (HBV), genotyped using 454 Life Sciences amplicon and shotgun methods.

Many bioinformatics problems are inference problems: Given partial or incomplete information about something, use that information to infer the missing or unknown data. This work addresses two inference problems in bioinformatics. The rst problem is inferring viral quasispecies sequences and their frequencies from 454 pyrosequencing reads. The second problem is inferring the structure of signal transduction networks from observations of interactions between cellular components. At first glance, these problems appear to be unrelated to each other. However, this work successfully penetrates both problems using the machinery of ow networks and transitive reduction, tools from classical computer science that prove useful in a wide array of application domains.

Nesta tese propomos e estudamos um modelo alternativo para investigar a evolução de quase-espécies moleculares, no qual supomos que a população seja uma combinação aleatória das moléculas constituintes em cada geração. Essa aleatoriedade deve-se a inclusão de um procedimento adicional de amostragem da população além dos procedimentos usuais de mutação e reprodução diferenciada. O modelo, denominado modelo de amostragens, é baseado em um algoritmo que mimetiza procedimentos experimentais que usam técnicas de transferências em série para reproduzir o processo de evolução de microorganismos in vitro. Além do modelo reproduzir a solução exata do estado estacionário do modelo de quase-espécies no regime determinístico, ele permite o estudo da evolução da quase-espécie molecular em todo espaço de parâmetros de controle, incluindo o caso em que a população é finita. A generalização dessa formulação alternativa para uma classe geral de relevos de replicação permite-nos realizar um estudo bastante completo do fenômeno do limiar de erro, levando-nos a uma análise crítica sobre a generalidade desse fenômeno / In this thesis we propose and study an alternative model to investigate the evolution of a molecular quasispecies, in which we assume that the population is a random combination of the constituent molecules in each generation. This randomness is due to the inclusion of an additional sampling procedure of the population, besides the usual procedures of mutation and differential reprodution. This model, termed sampling model, is based on an algorithm that mimics experimental procedures using serial transfer techniques to study the microbial evolutionary process in vitro. Besides yielding the exact steady-state solution of the quasispecies model in the deterministic limit, the sampling model allows the study of the molecular evolution in the full space of the control parameter, including the case where of population is finite. The generalization of this alternative formulation to a general class of fitness landscapes, allows us to investigate thoroughly the error threshold phenomenon, leading us to discuss critically the generality of this phenomenon in molecular evolution

We extend earlier cellular automata models of spatially extended hypercycles by including an explicit genetic component into the model. This allows us to study the sequence evolution of hypercyclically coupled molecular replicators in addition to considering their population dynamics and spatial organization. In line with previous models, that considered either spatial organization or sequence evolution alone, we find both temporal oscillations of the relative concentration of the species forming the hypercycles as well as the formation of spatial organisations including spiral waves. We also confirm the greatly increased robustness of the spatially extended hypercycle against various classes of parasites. We find the sequence evolution of each of the hypercyclically coupled populations proceeds (after an inital selection-dominated phase) in a drift-like manner that can be described by a diffusion process in sequence space. Kimura's theory of neutral evolution is therefore applicable on long time-scales despite the fact that the hypercycle exhibits extreme periodic changes in population sizes and that are governed solely by frequency-dependent selection.