Combinatorial analysis and algorithms for quasispecies reconstruction using next-generation sequencing.

BACKGROUND: Next-generation sequencing (NGS) offers a unique opportunity for high-throughput genomics and has potential to replace Sanger sequencing in many fields, including de-novo sequencing, re-sequencing, meta-genomics, and characterisation of infectious pathogens, such as viral quasispecies. Although methodologies and software for whole genome assembly and genome variation analysis have been developed and refined for NGS data, reconstructing a viral quasispecies using NGS data remains a challenge. This application would be useful for analysing intra-host evolutionary pathways in relation to immune responses and antiretroviral therapy exposures. Here we introduce a set of formulae for the combinatorial analysis of a quasispecies, given a NGS re-sequencing experiment and an algorithm for quasispecies reconstruction. We require that sequenced fragments are aligned against a reference genome, and that the reference genome is partitioned into a set of sliding windows (amplicons). The reconstruction algorithm is based on combinations of multinomial distributions and is designed to minimise the reconstruction of false variants, called in-silico recombinants. RESULTS: The reconstruction algorithm was applied to error-free simulated data and reconstructed a high percentage of true variants, even at a low genetic diversity, where the chance to obtain in-silico recombinants is high. Results on empirical NGS data from patients infected with hepatitis B virus, confirmed its ability to characterise different viral variants from distinct patients. CONCLUSIONS: The combinatorial analysis provided a description of the difficulty to reconstruct a quasispecies, given a determined amplicon partition and a measure of population diversity. The reconstruction algorithm showed good performance both considering simulated data and real data, even in presence of sequencing errors.

Stochastic modelling of genotypic drug-resistance for human immunodeficiency virus towards long-term combination therapy optimization.

MOTIVATION: Several mathematical models have been investigated for the description of viral dynamics in the human body: HIV-1 infection is a particular and interesting scenario, because the virus attacks cells of the immune system that have a role in the antibody production and its high mutation rate permits to escape both the immune response and, in some cases, the drug pressure. The viral genetic evolution is intrinsically a stochastic process, eventually driven by the drug pressure, dependent on the drug combinations and concentration: in this article the viral genotypic drug resistance onset is the main focus addressed. The theoretical basis is the modelling of HIV-1 population dynamics as a predator-prey system of differential equations with a time-dependent therapy efficacy term, while the viral genome mutation evolution follows a Poisson distribution. The instant probabilities of drug resistance are estimated by means of functions trained from in vitro phenotypes, with a roulette-wheel-based mechanisms of resistant selection. Simulations have been designed for treatments made of one and two drugs as well as for combination antiretroviral therapies. The effect of limited adherence to therapy was also analyzed. Sequential treatment change episodes were also exploited with the aim to evaluate optimal synoptic treatment scenarios. RESULTS: The stochastic predator-prey modelling usefully predicted long-term virologic outcomes of evolved HIV-1 strains for selected antiretroviral therapy combinations. For a set of widely used combination therapies, results were consistent with findings reported in literature and with estimates coming from analysis on a large retrospective data base (EuResist).

Investigation of expert rule bases, logistic regression, and non-linear machine learning techniques for predicting response to antiretroviral treatment.

BACKGROUND: The extreme flexibility of the HIV type-1 (HIV-1) genome makes it challenging to build the ideal antiretroviral treatment regimen. Interpretation of HIV-1 genotypic drug resistance is evolving from rule-based systems guided by expert opinion to data-driven engines developed through machine learning methods. METHODS: The aim of the study was to investigate linear and non-linear statistical learning models for classifying short-term virological outcome of antiretroviral treatment. To optimize the model, different feature selection methods were considered. Robust extra-sample error estimation and different loss functions were used to assess model performance. The results were compared with widely used rule-based genotypic interpretation systems (Stanford HIVdb, Rega and ANRS). RESULTS: A set of 3,143 treatment change episodes were extracted from the EuResist database. The dataset included patient demographics, treatment history and viral genotypes. A logistic regression model using high order interaction variables performed better than rule-based genotypic interpretation systems (accuracy 75.63% versus 71.74-73.89%, area under the receiver operating characteristic curve [AUC] 0.76 versus 0.68-0.70) and was equivalent to a random forest model (accuracy 76.16%, AUC 0.77). However, when rule-based genotypic interpretation systems were coupled with additional patient attributes, and the combination was provided as input to the logistic regression model, the performance increased significantly, becoming comparable to the fully data-driven methods. CONCLUSIONS: Patient-derived supplementary features significantly improved the accuracy of the prediction of response to treatment, both with rule-based and data-driven interpretation systems. Fully data-driven models derived from large-scale data sources show promise as antiretroviral treatment decision support tools.

Rigidity-Preserving Team Partitions in Multiagent Networks.

Motivated by the strong influence network rigidity has on collaborative systems, in this paper, we consider the problem of partitioning a multiagent network into two sub-teams, a bipartition, such that the resulting sub-teams are topologically rigid. In this direction, we determine the existence conditions for rigidity-preserving bipartitions, and provide an iterative algorithm that identifies such partitions in polynomial time. In particular, the relationship between rigid graph partitions and the previously identified Z-link edge structure is given, yielding a feasible direction for graph search. Adapting a supergraph search mechanism, we then detail a methodology for discerning graphs cuts that represent valid rigid bipartitions. Next, we extend our methods to a decentralized context by exploiting leader election and an improved graph search to evaluate feasible cuts using only local agent-to-agent communication. Finally, full algorithm details and pseudocode are provided, together with simulation results that verify correctness and demonstrate complexity.

Construction, training and clinical validation of an interpretation system for genotypic HIV-1 drug resistance based on fuzzy rules revised by virological outcomes.

OBJECTIVES: To evaluate whether fuzzy operators can be usefully applied to the interpretation of genotypic HIV-1 drug resistance by experts, and to improve the prediction of salvage therapy outcome by adapting interpretation rules of genotypic resistance on the basis of their association with virological response data. METHODS: We used a clinical dataset of 231 patients failing highly active antiretroviral therapy (HAART) and starting salvage therapy with baseline resistance genotyping and virological outcomes after 3 and 6 months. A set of rules predicting genotypic resistance was initially derived from an expert (ADL). Rules were implemented using a fuzzy logic approach and the virological outcomes dataset used for the training phase. The resulting algorithm was validated using a separate set of 184 selected patients by correlating the resulting predicted activity with observed virological response at 3 months. For comparison, the expert systems from the drug resistance group of the Agence Nationale de Recherches sur le SIDA (ANRS-AC11) and the algorithm from the Stanford's HIV drug resistance database (Stanford HIVdb) were evaluated on the same set. RESULTS: The starting algorithm had a correlation with virological outcomes of R2=0.06 (P=0.0001). After the training phase the correlation with virological outcomes increased to R2=0.19 (P<0.000001). In the validation set of patients, the activity of the salvage regimen predicted by the fuzzy algorithm was the only variable independently predictive of the 3-month viral load change even after adjusting by the activity predicted by the two expert systems and baseline viral load (for each 10% salvage regimen's activity increase, mean HIV RNA change from baseline: -0.27 log10 copies/ml; 95% CI -0.39, -0.15). CONCLUSION: Using fuzzy operators in a virological outcomes training database to implement a rules-based algorithm for genotypic resistance interpretation, significant improvements of outcomes prediction were obtained. The resulting algorithm showed an independent predictive capability of virological outcomes over that of two rules-based interpretation algorithms made by experts. Although the system was trained and validated on a limited number of cases, the approach deserves further evaluation.

Robust supervised and unsupervised statistical learning for HIV type 1 coreceptor usage analysis.

Human immunodeficiency virus type 1 (HIV-1) isolates differ in their use of coreceptors to enter target cells. This has important implications for both viral pathogenicity and susceptibility to entry inhibitors, recently approved or under development. Predicting HIV-1 coreceptor usage on the basis of sequence information is a challenging task, due to the high variability of the envelope. The associations of the whole HIV-1 envelope genetic features (subtype, mutations, insertions-deletions, physicochemical properties) and clinical markers (viral RNA load, CD8(+), CD4(+) T cell counts) with viral tropism were investigated, using a set of 2896 (659 after filter, 593 patients) sequence-tropism pairs available at the Los Alamos HIV database. Bootstrapped hierarchical clustering was used to assess mutational covariation. Univariate and multivariate analysis was performed to assess the relative importance of different features. Different machine learning (logistic regression, support vector machines, decision trees, rule bases, instance based reasoning) and feature selection (filter and embedded) methods, along with loss functions (accuracy, AUC of ROC curves, sensitivity, specificity, f-measure), were applied and compared for the classification of X4 variants. Extra-sample error estimation was assessed via multiple cross-validation and adjustments for multiple testing. A high-performing, compact, and interpretable logistic regression model was derived to infer HIV-1 coreceptor tropism for a given patient [accuracy = 92.76 (SD 3.07); AUC = 0.93 (SD 0.04)].