Dataset Information

Viral quasispecies assembly via maximal clique enumeration.

ABSTRACT: Virus populations can display high genetic diversity within individual hosts. The intra-host collection of viral haplotypes, called viral quasispecies, is an important determinant of virulence, pathogenesis, and treatment outcome. We present HaploClique, a computational approach to reconstruct the structure of a viral quasispecies from next-generation sequencing data as obtained from bulk sequencing of mixed virus samples. We develop a statistical model for paired-end reads accounting for mutations, insertions, and deletions. Using an iterative maximal clique enumeration approach, read pairs are assembled into haplotypes of increasing length, eventually enabling global haplotype assembly. The performance of our quasispecies assembly method is assessed on simulated data for varying population characteristics and sequencing technology parameters. Owing to its paired-end handling, HaploClique compares favorably to state-of-the-art haplotype inference methods. It can reconstruct error-free full-length haplotypes from low coverage samples and detect large insertions and deletions at low frequencies. We applied HaploClique to sequencing data derived from a clinical hepatitis C virus population of an infected patient and discovered a novel deletion of length 357±167 bp that was validated by two independent long-read sequencing experiments. HaploClique is available at https://github.com/armintoepfer/haploclique. A summary of this paper appears in the proceedings of the RECOMB 2014 conference, April 2-5.

SUBMITTER: Topfer A

PROVIDER: S-EPMC3967922 | biostudies-literature | 2014 Mar

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Viral quasispecies assembly via maximal clique enumeration.

Töpfer Armin A Marschall Tobias T Bull Rowena A RA Luciani Fabio F Schönhuth Alexander A Beerenwinkel Niko N

PLoS computational biology 20140327 3

Virus populations can display high genetic diversity within individual hosts. The intra-host collection of viral haplotypes, called viral quasispecies, is an important determinant of virulence, pathogenesis, and treatment outcome. We present HaploClique, a computational approach to reconstruct the structure of a viral quasispecies from next-generation sequencing data as obtained from bulk sequencing of mixed virus samples. We develop a statistical model for paired-end reads accounting for mutati ...[more]

PMID: 24675810

Similar Datasets

Project description:BackgroundThe maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are NP-hard, given that they subsume the classic version of the NP-complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow.ResultsAn extensive testbed of benchmark graphs are created using publicly available transcriptomic datasets from the Gene Expression Omnibus (GEO). Empirical testing reveals crucial but latent features of such high-throughput biological data. In turn, it is shown that these features distinguish real data from random data intended to reproduce salient topological features. In particular, with real data there tends to be an unusually high degree of maximum clique overlap. Armed with this knowledge, novel decomposition strategies are tuned to the data and coupled with the best FPT MCE implementations.ConclusionsSeveral algorithmic improvements to MCE are made which progressively decrease the run time on graphs in the testbed. Frequently the final runtime improvement is several orders of magnitude. As a result, instances which were once prohibitively time-consuming to solve are brought into the domain of realistic feasibility.

Project description:Opportunistic infection of oligodendrocytes by human JC polyomavirus may result in the development of progressive multifocal encephalopathy in immunocompromised individuals. Neurotropic JC virus generally harbors reorganized noncoding control region (NCCR) DNA interspersed on the viral genome between early and late coding genes. By applying 454 sequencing on NCCR DNA amplified from body fluid samples (urine, plasma, and cerebrospinal fluid [CSF]) from 19 progressive multifocal leukoencephalopathy (PML) patients, we attempted to reveal the composition of the JC polyomavirus population (the quasispecies, i.e., the whole of the consensus population and minor viral variants) contained in different body compartments and to better understand intrapatient viral dissemination. Our data demonstrate that in the CSF of PML patients, the JC viral population is often a complex mixture composed of multiple viral variants that contribute to the quasispecies. In contrast, urinary JC virus highly resembled the archetype virus, and urine most often did not contain minor viral variants. It also appeared that archetype JC virus could sporadically be identified in PML patient brain, although selection of rearranged JC virus DNA was favored. Comparison of the quasispecies from different body compartments within a given patient suggested a strong correlation between the viral population in plasma and CSF, whereas the viral population shed in urine appeared to be unrelated. In conclusion, it is shown that the representation of viral DNA in the CSF following the high-level DNA replication in the brain underlying PML has hitherto been much underestimated. Our data also underscore that the hematogenous route might play a pivotal role in viral dissemination from or toward the brain.For the first time, the JC polyomavirus population contained in different body compartments of patients diagnosed with progressive multifocal encephalopathy has been studied by deep sequencing. Two main findings came out of this work. First, it became apparent that the complexity of the viral population associated with PML has been highly underestimated so far, suggestive of a highly dynamic process of reorganization of the noncoding control region of JC polyomavirus in vivo, mainly in CSF and blood. Second, evidence showing viral dissemination from and/or toward the brain via the hematogenous route was provided, confirming a hypothesis that was recently put forward in the field.

Dataset Information

Viral quasispecies assembly via maximal clique enumeration.

Publications

Viral quasispecies assembly via maximal clique enumeration.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets