BACKGROUND
hiv/aids is a pandemic disease and more than  <dig> million people are infected worldwide  <cit> .
there is no effective vaccine or medicine to completely cure aids; however, the long-term survival of many patients has been enabled by drug therapy.
highly active antiretroviral therapy  using three or four different drugs with different viral targets is very effective in stabilizing the infection  <cit> .
these antiviral drugs target different stages in the viral life-cycle.
two important drug targets are the hiv protease  and reverse transcriptase , which have essential roles in viral replication.
hiv rt converts the viral rna genome into dna, which is translated by the host cell machinery into the viral precursor proteins.
hiv pr functions to cleave the large viral precursor proteins into individual enzymes and structural proteins, which produces infectious viral particles.
among the  <dig> approved drugs in current clinical use, there are seven nucleoside rt inhibitors , four non-nucleoside rt inhibitors , and eight pr inhibitors   <cit> .
the approved pis were designed to bind in the active site of hiv pr, and prevent the processing of viral precursor proteins .
nrtis are chemical analogs of the natural nucleoside substrates of the hiv rt that bind to the protein active site and block its activity in synthesizing dna from viral rna.
the inhibitors in the nnrti class also decrease the enzymatic activities of rt, however, they bind in an allosteric site in the palm domain of the p <dig> subunit instead of the active site of rt .
despite the success of haart, current therapy is limited by the rapid emergence of drug resistance  <cit> .
the virus can mutate to acquire resistance during therapy due to the lack of proofreading by rt  <cit>  and high replication rate  <cit> .
these resistance mutations alter the drug targets such as pr and rt  <cit> .
some of the  <dig> mutations associated with resistance to pris alter amino acids located in the active site of pr while the majority alter residues in distal regions of the enzyme structure  <cit> .
similarly for rt, several of the mutations associated with resistance to nrtis alter amino acids in the active site of the enzyme while others are located in more distal regions.
the amino acid mutations occurring in association with resistance to the nnrtis tend to cluster around the inhibitor binding site  <cit> .
the molecular mechanisms for these antiviral drugs are described in the review  <cit> .
these resistance mutations lower the effectiveness of specific drugs and may cause failure of the treatment.
infections with resistant hiv are prevalent; surveys in north america and europe show that 8-20% of hiv infections in untreated people contain primary drug resistance mutations  <cit> .
over time, multiple mutations can accumulate giving a huge number of possible combinations of mutations in each protein.
this persistent problem led to the recommendation for resistance testing to guide the choice of drugs in aids therapy  <cit> .
fast sequencing of the genome of the infecting virus can be combined with computational predictions of resistance to guide the choice of effective antiviral drugs  <cit> .
accurate and fast computational predictions are desirable to avoid the expense, limited availability and time involved for performing an experimental cell-based assay for resistance where results can take four weeks.
accurate predictions can be valuable for prescribing the most effective drugs for infections with resistant hiv.
most genotype interpretation algorithms in clinical use are knowledge based  <cit> .
these interpretation algorithms apply a set of rules or scores for each mutation and drug.
the performance of several commonly used interpretation algorithms: stanford hivdb  <cit> , hiv-grade  <cit> , rega and anrs  has been compared  <cit> .
in addition, many computational classification techniques have been evaluated for predicting drug resistance from the genotype data.
the standard classification techniques of artificial neural networks   <cit> , decision tree  <cit> , random forests  <cit> , support vector machine   <cit>  and regression analysis  <cit>  have been applied in hiv drug resistance predictions.
statistical methods can also be applied to analyze the relationship between genotype and phenotype.
the association of mutations with resistance to the pis saquinavir  and indinavir  was determined using cluster analysis, recursive partitioning, and linear discriminant analysis  <cit> .
these methods are limited by the high dimensionality of the genotype data, hence non-parametric methods have been proposed and tested on resistance data for the pi amprenavir  <cit> .
protein structural information has been used to generate statistical potentials of mutants for training with svm or random forest learning algorithms and tested in predicting resistance to the rt inhibitor nevirapine   <cit> .
we have evaluated an efficient encoding of information from the three-dimensional protein structure for the prediction of resistance from genotype.
the structural encoding via delaunay triangulation improves the quality of the predictions by representing interactions between amino acid neighbours in the three-dimensional structure unlike the linear sequence representation of other methods.
this unified sequence-structure representation was used in supervised training with svm, ann, and a new sparse dictionary classification method.
the compressive sensing/sparse dictionary representation  <cit>  has been applied successfully in image analysis to enhance learning capacity and efficiency.
sparse representation has been employed for image restoration  <cit> , denoising  <cit> , deblurring  <cit> , signal processing  <cit> , and face detection  <cit> .
initial tests of this procedure for classifying resistance to four pis was presented in  <cit> .
here, the structural encoding has been expanded to regression analysis and classification of genotype-phenotype data for seven pis, six nrtis and three nnrtis.
RESULTS
we combined structural information with genotype for regression analysis and supervised learning on resistance data.
the new graph based sequence-structure encoding was tested with the genotype-phenotype data from the stanford hiv drug resistance database  <cit>  .
data were available for two different protein targets: hiv- <dig> pr and hiv- <dig> rt.
for hiv- <dig> pr, eight pr inhibitors atazanavir , idv, nelfinavir , ritonavir , lopinavir , tipranavir  and sqv were tested.
while for the study of hiv rt inhibitor resistance, nnrtis nevirapine , delaviridine , efavirenz , and nrtis lamivudine , abacavir , zidovudine , stavudine , didanosine  and tenofovir  were tested.
the data include the protein sequence  and resistance value  from the phenosense  assay for each virus isolate.
genotype-phenotype data were available for  <dig> to  <dig> isolates for different inhibitors of hiv pr, while rt was represented by  <dig> to  <dig> records for the  <dig> different nrtis and nnrtis.
the preprocessing of the sequence and resistance data is detailed in methods.
genotypes were expanded to unique protein sequences due to the presence of more than one amino acid at some positions.
this expansion resulted in a total of  <dig>  to  <dig>  unique sequences of hiv pr mutants and  <dig>  to  <dig>  rt mutants for the various inhibitor resistance values.
graph based protein sequence/structure representation using delaunay triangulation
the sequences were combined with information from the three-dimensional protein structures by employing a graph generated by delaunay triangulation as described in  <cit> .
two structure templates were used: 3oxc  <cit>  for hiv- <dig> pr, and 2wom  <cit>  .
only one structure vector is needed for each protein.
in other words, all pr mutant sequences are combined with a single 210-dimensional vector derived from one pr structure, and similarly, a single structure vector is used for the rt mutants in subsequent regression and classification of resistance data.
as a result, all mutants are represented as vectors of constant dimensionality, which is a desirable property for most of the pattern recognition algorithms.
this structure vector was combined with sequences in regression analysis and classification for resistance.
multiple regression on hiv protease inhibitor resistance
after each of the mutated sequences was represented by a 210-dimensional vector, we performed the regression analysis for the drug resistance data.
we performed k-fold  regression analysis on the sequence and resistance data.
the predicted values for relative resistance are plotted against the experimental values as shown in  for the pr inhibitors atv, nfv, rtv, idv, lpv, tpv and sqv.
the multiple regression gave high r <dig> values of  <dig> - <dig>  and very low standard deviations as listed in table  <dig>  the values are the average of all the r <dig> values from k-fold regression.
the high variance seen for high values of resistance is likely due to limitations of the experimental assay such that the measured resistance value has a cutoff at the upper limit, while the viral strains may have an effective resistance above this cutoff.
the excellent correlations demonstrate that relative resistance to pis can be predicted successfully from genotype by the new sequence/structure encoding method.
in order to avoid training to an "optimal" n-fold set for cross validation, cross validation sets are chosen independently for each training run.
therefore, there is always a small variation in the results.
multiple regression on hiv reverse transcriptase inhibitor resistance
multiple regression analysis was performed similarly on genotype-phenotype data for drugs inhibiting hiv- <dig> rt.
the predicted and observed values are compared for resistance to nrtis: 3tc, abc, d4t, ddi, tdf and azt in figure 3; and nnrtis: npv, dlv and efv in figure  <dig>
the regression results gave high r <dig> values of  <dig> - <dig>  for the different rt inhibitors, as shown in tables  <dig> and  <dig>  the resistance to nrtis was predicted with excellent r <dig> values of  <dig> - <dig>  and very low standard deviations, while resistance predictions for nrtis gave r <dig> values in the larger range of  <dig> - <dig> .
larger standard deviations were obtained for analysis of abc and ddi possibly because the range of values in the dataset was smaller than for the others.
therefore, graph based encoding had excellent success in predicting resistance to rt inhibitors.
classification of resistance with support vector machine
the support vector machine  was proposed by vapnik  <cit> , and is widely used as a supervised learning classifier in the machine learning classification area.
in this experiment, 5-fold cross validation tests were performed by implementing in matlab svm toolbox  <cit>  and the linear kernel was used.
the results are shown in tables  <dig>   <dig>   <dig> for hiv- <dig> pr inhibitors , hiv- <dig> rt nrtis and hiv- <dig> rt nnrtis.
this classification shows high accuracy, sensitivity and specificity for all inhibitors.
for pis the accuracy values range from a low of  <dig>  to a high of  <dig> , while sensitivity and specificity range from  <dig> - <dig>  and  <dig> - <dig> , respectively.
resistance to nrtis is classified with even higher accuracies of  <dig> - <dig> , sensitivities of greater than  <dig>  and specificities of  <dig> - <dig> , while for nnrtis the classification performance was superior with all values of over  <dig>  for accuracy, sensitivity and specificity.
the excellent performance with the linear svm kernel demonstrates conclusively that the novel encoding using delaunay triangulation separates the resistant and non-resistant data into two distinct categories.
classification with artificial neural networks
as in the svm experiment, the 5-cross validation test was applied to the artificial neural networks  to classify genotype-phenotype data for resistance.
specifically, the three-layer feedforward network was used in matlab  <cit> .
the network had one hidden layer of  <dig> nodes and was trained with backpropagation with a maximum of  <dig> training epochs.
the results are shown in tables  <dig>   <dig>   <dig> for hiv- <dig> pr inhibitors, and rt inhibitors nrtis and nnrtis.
the values calculated for accuracy, sensitivity and specificity for resistance to pis have a low of  <dig>  and reach  <dig> .
improved performance was achieved for classifying resistance to rt inhibitors compared with pis.
results for nrtis gave values of accuracy, sensitivity and specificity of  <dig> - <dig> , while for nnrtis all values were greater than  <dig> .
classification using sparse dictionary
the sparse dictionary classifier was also implemented using the 5-fold cross validation tests using the approach described in  <cit> .
the results are shown in tables  <dig>   <dig>   <dig> for hiv- <dig> pr inhibitors, hiv- <dig> rt nrtis and nnrtis.
high values were obtained for accuracy, sensitivity, and specificity.
accuracies ranged from  <dig> - <dig>  for resistance to pis,  <dig> - <dig>  for nrtis and  <dig> - <dig>  for nnrtis.
the sensitivities were all greater than  <dig>  for the calculations on resistance to pis, and specificities were greater than  <dig> .
lower values were obtained for calculations on some of the rt inhibitors where values for sensitivity ranged from  <dig>  to  <dig> , while high specificity values from  <dig>  to  <dig>  was calculated.
these performance measures are somewhat poorer than for the standard svm and ann classifiers.
it is not surprising; however, that more development may be necessary for applying the new sparse dictionary as a classifier since previously it has been employed primarily for image processing.
comparison with standard genotype interpretation methods
finally, we compared our methods with the standard drug resistance prediction methods hiv-grade, anrs-rules, stanford hivdb, and rega, which are available at http://www.hiv-grade.de/cms/grade/, using the same genotype-phenotype datasets described in methods.
the procedure discussed in  <cit>  was used to convert the protein sequences into nucleotide sequences.
other methods usually give resistance interpretations in three categories of "resistance, "intermediate" and "susceptible".
since multiple classification is difficult with svm and ann, only two classes were considered for calculating the accuracy.
both "resistant" and "intermediate" are considered as "resistant"; while "susceptible" is considered as "non-resistant".
the results are shown in tables  <dig>   <dig>   <dig> for hiv- <dig> pr inhibitors, hiv- <dig> rt nrtis and nnrtis.
n/a means that no output was obtained from the server for this dataset.
the accuracies demonstrate that classification with our structural encoding significantly outperforms other state of the art methods for predicting resistance to pis for the three tested classifiers svm, ann and the sparse dictionary.
accuracies of  <dig> - <dig> % were obtained with structural encoding compared to  <dig> - <dig> % for the standard methods.
the highest accuracies of greater than 95% were achieved with the sparse dictionary method.
the prediction accuracy for resistance to the nrti class of rt inhibitors also showed the advantages of our structural encoding with values of  <dig> - <dig> % compared with  <dig> - <dig> % for standard methods.
in this case, the svm and ann classifiers performed better than the new sparse dictionary giving accuracies of at least 97%.
for the nnrtis, the structural encoding with svm or ann gave higher accuracies of  <dig> - <dig> % compared with  <dig> - <dig> % for standard methods.
the sparse dictionary, however, showed lower performance with accuracies of  <dig> - <dig> % for nnrti resistance, indicating some improvements may be needed for the new classifier.
discussion
the serious problem of drug resistance arising during therapy of hiv-infected individuals can be tackled by sequencing the hiv drug targets to identify mutations followed by computational prediction of resistance to guide the choice of effective therapy.
computational predictions of the most effective drugs for the mutated hiv provide a major advantage of low cost and speed relative to experimental assays for resistance.
most standard prediction methods are knowledge based methods, such as the genotype interpretation algorithms.
these algorithms either use a set of rules, for example, the visible genetics/bayer diagnostics genotype interpretation rules  <cit> , to generate the susceptibility of the infecting virus for each drug; or apply a score or 'penalty' for each drug such as the stanford hiv database  <cit>  and mutation rate based score  <cit> .
also, a combined rule-based and penalty-based method has been proposed and applied to both hiv- <dig> pr and rt inhibitors  <cit> .
although these methods are fast, they suffer from the major disadvantage of relying on specific known mutations strongly associated with resistance and cannot identify newly appearing resistance mutations, or assess the effects of many mutations more weakly associated with resistance.
various machine learning and statistical methods have been applied to this problem, including the widely used classifiers, ann  <cit> , decision tree  <cit> , and svm  <cit> .
statistical methods such as cluster analysis, recursive partitioning, and linear discriminant analysis have been evaluated  <cit> , and non-parametric methods proposed for high dimensionality data  <cit> .
most of these methods are based on the linear protein sequence and omit potentially valuable information from the three-dimensional protein structure.
additional information has been introduced in the form of  <dig> physicochemical descriptors for the amino acid mutations leading to correlation coefficients of  <dig> - <dig>   <cit> .
other groups have included structural features such as pr-drug contacts in the binding site with majority voting  <cit> .
in another example, delaunay triangulation of the rt structure was combined with a four-body statistical potential derived from  <dig> protein structures in predictions for resistance to nvp and gave cross-validated accuracies of 85% with svm and 92% with random forest classifiers  <cit> .
molecular mechanics calculations on the pr-drug structure have been used to predict resistance of mutants, and gave high correlation  between caclulation and ic <dig> from the experimental assay  <cit> .
however, these calculations must be performed for each mutant-drug combination and will be slow for assessing large numbers of mutants for resistance.
we have developed a simple graph representation of protein structure for fast classification.
the protein structure is a three-dimensional object that has many physical and chemical factors potentially effecting stability and activity.
previously, we showed that delaunay triangulation was the best of several tested graph-based encodings of protein structure and sequence  <cit> .
the graph-based encoding algorithm condenses a complicated three-dimensional object, a protein structure, into a relatively small hash function with  <dig> unique values per sequence and structure.
one critical outcome is that the graph-based encoding results in a linearly separable data set that can be used readily by several different machine learning algorithms.
similarly, the encoding is sufficiently linear that straightforward multiple linear regression can be performed on the training data.
the hash value maintains enough information about the complicated object to provide useful information for machine learning and regression.
this unified sequence-structure encoding gave high accuracy in initial tests on four pis  <cit> .
here, we demonstrate successful application of the structure vector in multiple regression analysis and classification on resistance data for seven inhibitors of hiv pr and nine inhibitors of rt.
the 5-fold validated regression analysis gave excellent correlation between predicted and observed resistance with excellent r <dig> values of  <dig> - <dig>  for pis,  <dig> - <dig>  for nrtis and  <dig> - <dig>  for nnrtis.
classification with svm, ann or a new sparse dictionary method gave high accuracies for predicting the resistance for pr and rt inhibitors.
the structure vector encoding had superior accuracy to predictions on the same sequences using standard interpretation algorithms.
the sparse dictionary classifier was the best of tested classifiers for prediction of resistance to pis, whereas svm classification gave the best performance on resistance prediction for rt inhibitors.
this structure vector encoding of genotype data has the advantage of using a single 210-dimensional vector for each protein target.
the algorithm has one slow step for preparing the encoding from a single protein structure that can be applied to all genotypes in a fast calculation, in contrast to molecular mechanics calculations that must be set up in a non-trivial manner for each individual protein sequence.
the entire protein sequence is combined with the structure vector, so there is the potential for accommodating new mutations or combinations of mutations with weak but concerted effects on resistance.
the procedure can be extended easily in future calculations for resistant mutants with insertions in the protein sequence, which occur commonly in rt  <cit> .
the new sparse dictionary classification approach can be extended to multiple classifiers by using more than two dictionaries, which is a significant advantage over the tested standard svm or ann classifiers, and may permit accurate predictions for different levels of resistance.
CONCLUSIONS
the simple unified encoding of structural information with genotype gives high accuracy for prediction of resistance to hiv pr and rt inhibitors as well as excellent correlation coefficients in regression analysis.
the improvement over algorithms using only linear sequence information suggests the importance of local interactions between mutated residues in the protein structure, which is consistent with the correlated local changes observed in the crystal structures of a highly resistant pr mutant with  <dig> substitutions  <cit> .
graph-based encoding of sequence and structure holds promise for fast and accurate predictions of resistance from sequence in order to guide the choice of effective drugs for treatment of hiv infections.
in future, this approach can be expanded to predict resistance for other drugs and more diverse types of data.
materials and methods
data sets and data preparation
all the datasets were retrieved from genotype-phenotype data on the stanford hiv drug resistance database  <cit>  .
in this experiment, the proposed algorithm was tested on two different systems: hiv- <dig> pr and hiv- <dig> rt resistance data.
for hiv- <dig> pr, eight pr inhibitors atazanavir , indinavir , nelfinavir , ritonavir , idv, lpv, tpv and sqv were tested.
while for the study of hiv rt inhibitor resistance, nnrtis nevirapine , delaviridine , efavirenz , and nrtis lamivudine , abacavir , zidovudine , stavudine , didanosine  and tenofovir  were tested.
for the drug resistance study on the hiv pr and hiv rt inhibitors, all the genotypes were expanded to individual unique amino acid sequences using the method discussed in  <cit> .
this expansion was needed since the genotyping experiment resulted in more than one possible amino acid at several positions in each genotype, due to potential experimental error or existence of multiple viral sequences infecting one patient.
for each of the hiv- <dig> pr inhibitors the results were: for the inhibitor idv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor lpv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor tpv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor sqv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor atv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor idv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor nfv, a total of  <dig> sequences were obtained from  <dig> isolates; and for the inhibitor rtv, a total of  <dig> sequences were obtained from  <dig> isolates.
for each of the hiv- <dig> rt inhibitors the results were: for the inhibitor npv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor dlv, a total of  <dig> sequences were obtained from  <dig> isolates; and for the inhibitor efv, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor 3tc, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor abc, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor azt, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor d4t, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor ddi, a total of  <dig> sequences were obtained from  <dig> isolates; for the inhibitor tdf, a total of  <dig> sequences were obtained from  <dig> isolates.
all positive and negative instances of a given mutant were removed from either training or testing dataset before the cross-validation.
this may avoid the potential problem of having negative instances associated with a positive test item or positive instances associated with a negative test item, and thus assure the training accuracy.
pre-processing of the datasets
in order to unify the data in the original datasets, those sequences with an insertion, deletion, or containing a stop codon relative to the consensus have been removed so that the data represent proteases of  <dig> amino acids.
many of the sequence records in the dataset have multiple mutations at the same sites yet share the same drug-resistance value, which may be due to sequencing limitations or to the existence of multiple viral strains in the same isolate.
in order to represent a single amino acids sequence for each mutant protein, we need to expand the data to multiple sequences with single amino acids at each location.
for instance, in one 99-amino acid mutant of hiv pr, at one site there are two different types of amino-acids, and another site has three.
in this case, this record must be expanded to a total of  <dig> =  different sequences, each of which has only one amino-acid for each of its  <dig> residues, sharing the same drug resistance.
we designed a fast way to perform this expansion as detailed in  <cit> , which significantly enriches the test data.)
cutoffs for resistance/susceptibility for each drug
for the hiv- <dig> pr inhibitors: atv, idv, nfv, and rtv, among all these genotype sequences, those mutants with the relative resistant fold <  <dig>  were classified as non- resistant , denoted as 0; while those with the relative resistant fold ≥  <dig>  were classified as resistant, denoted as  <dig>  <cit> .
with the hiv- <dig> rt inhibitors: for abc and tpv, those mutants with the relative resistant fold <  <dig>  were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥  <dig>  were classified as resistant, denoted as 1; for 3tc, azt, npv, dlv, efv, sqv, idv and lpv those mutants with the relative resistant fold <  <dig>  were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥  <dig>  were classified as resistant, denoted as 1; for d4t, ddi and tdf, those mutants with the relative resistant fold <  <dig>  were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥  <dig>  were classified as resistant, denoted as  <dig>  <cit> .
encoding structure and sequence with delaunay triangulation
the sequence and structure of the protein were represented using a graph-based encoding as described in  <cit> .
delaunay triangulation was used to define a graph which spanned the protein structure and defined adjacent pairs of amino acid residues.
adjacent pairs of amino acids were summarized into a vector of the  <dig> unique kinds of amino acid pairs by calculating the distance for each adjacent pair in the structure and tabulating by the types of amino acids in that adjacent pair.
only the sequences of the mutated proteins are needed and only one protein structure is necessary.
as a result, all mutants are represented as vectors of the same dimensionality, which is a desired property for most of the pattern recognition algorithms.
the structures 3oxc  <cit>  for hiv- <dig> pr, and 2wom  <cit>  for hiv- <dig> rt  were used as templates for delaunay triangulation.
k-fold validation
in order to fully use all the data, a k-fold cross-validation was performed in all the experiments for all the drugs.
specifically, we randomly choose /k of all the sequences  for training the classifier and the remaining 1/k data are used for testing.
these tests used k =  <dig>  independent randomly selected k-folds were chosen throughout the study to avoid bias in the results.
regression analysis for drug resistance prediction
the genotype-phenotype datasets provide a drug resistance value, with respect to a certain type of drug, with each genotype.
the mutations relative to a standard sequence are denoted as x <dig> x <dig> …,xn;xi∈ℜ <dig> where n is the total number of mutations and ℜ <dig> is the structure vector.
also the corresponding drug resistance values are denoted as the real numbers y <dig> y <dig> …,yn;y∈ℜ including  <dig> for the resistance value of the wild type virus.
we then seek a linear model between the xi's and yi's by minimizing the cost function e :
e:=∑i=1n <dig>
with respect to the  <dig> dimensional vector a and scalar b.
furthermore, in order to better utilize the available data set, we performed a k-fold cross-validation .
specifically, the training set of size n is randomly divided into k groups.
among them, k -  <dig> groups are utilized for constructing the linear model as in equation .
then, the linear model is used to predict the drug resistance for the remaining group with n/k mutations.
the predicted resistances are compared with the measured ones and the r <dig> values are recorded.
finally, the average and standard deviation of the k r <dig> values are computed.
sparse dictionary classification
in this experiment, we applied our newly proposed method described in  <cit>  on both hiv- <dig> pr and hiv- <dig> rt data sets.
in this case, the sequences of the mutants are considered as the group of signals, and given these signals, we would like to construct a dictionary to represent them sparsely.
the construction of a dictionary can be considered as finding a suitable over-complete basis , in which the signals of interest would be represented with far fewer non-zero coefficients, than in an arbitrary fixed basis such as a fourier basis.
the newly constructed basis is also called a dictionary.
this dictionary can be used to assess how well the new signal fits the model represented by the dictionary, and therefore, it can be used as a new classification method.
in our experiment, we assume there are  <dig> groups of signals: one for drug resistant mutants, while the other group is non-drug resistant mutants.
we construct two dictionaries for each group, respectively.
after that, given a new signal , we use both dictionaries to represent this signal.
by calculating and comparing the reconstruction error, the dictionary with the smaller error indicates that the signal belongs to this category.
based on the theory of the dictionary, it can be observed that the group number is not limited to  <dig>  and such procedure could be used as a multi-group classification method.
the  <dig> dictionaries for each set of drug resistance data were constructed and the classification performed as described in  <cit> .
list of abbreviations
haart, highly active antiretroviral therapy; pr, hiv protease; pi, protease inhibitor; rt, hiv reverse transcriptase; nrti, nucleoside rt inhibitor; nnrti, non-nucleoside rt inhibitor; ann, artificial neural networks; svm, support vector machine; apv, amprenavir; atv, atazanavir; idv, indinavir; lpv, lopinavir; nfv, nelfinavir; rtv, ritonavir; sqv, saquinavir; tpv, tipranvir; 3tc, lamivudine; abc, abacavir; azt, zidovudine; d4t, stavudine; ddi, didanosine; dlv, delaviridine; efv, efavirenz; nvp, nevirapine; tdf, tenofovir.
competing interests
the authors declare that they have no competing interests.
authors' contributions
all authors designed the experiments.
xy and rwh designed the algorithms.
xy implemented the algorithms and ran the predictions.
all authors interpreted the results and wrote the manuscript.
all authors read and approved the final manuscript.

 hiv/aids is a pandemic disease and more than million people are infected worldwide. there is no effective vaccine or medicine to completely cure aids; however, the long-term survival of many patients has been enabled by drug therapy. highly active antiretroviral therapy using three or four different drugs with different viral targets is very effective in stabilizing the infection. these antiviral drugs target different stages in the viral life-cycle. two important drug targets are the hiv protease and reverse transcriptase, which have essential roles in viral replication. hiv rt converts the viral rna genome into dna, which is translated by the host cell machinery into the viral precursor proteins. hiv pr functions to cleave the large viral precursor proteins into individual enzymes and structural proteins, which produces infectious viral particles. among the approved drugs in current clinical use, there are seven nucleoside rt inhibitors, four non-nucleoside rt inhibitors, and eight pr inhibitors. the approved pis were designed to bind in the active site of hiv pr, and prevent the processing of viral precursor proteins. nrtis are chemical analogs of the natural nucleoside substrates of the hiv rt that bind to the protein active site and block its activity in synthesizing dna from viral rna. the inhibitors in the nnrti class also decrease the enzymatic activities of rt, however, they bind in an allosteric site in the palm domain of the p subunit instead of the active site of rt. despite the success of haart, current therapy is limited by the rapid emergence of drug resistance. the virus can mutate to acquire resistance during therapy due to the lack of proofreading by rt and high replication rate. these resistance mutations alter the drug targets such as pr and rt. some of the mutations associated with resistance to pris alter amino acids located in the active site of pr while the majority alter residues in distal regions of the enzyme structure. similarly for rt, several of the mutations associated with resistance to nrtis alter amino acids in the active site of the enzyme while others are located in more distal regions. the amino acid mutations occurring in association with resistance to the nnrtis tend to cluster around the inhibitor binding site. the molecular mechanisms for these antiviral drugs are described in the review. these resistance mutations lower the effectiveness of specific drugs and may cause failure of the treatment. infections with resistant hiv are prevalent; surveys in north america and europe show that 8-20% of hiv infections in untreated people contain primary drug resistance mutations. over time, multiple mutations can accumulate giving a huge number of possible combinations of mutations in each protein. this persistent problem led to the recommendation for resistance testing to guide the choice of drugs in aids therapy. fast sequencing of the genome of the infecting virus can be combined with computational predictions of resistance to guide the choice of effective antiviral drugs. accurate and fast computational predictions are desirable to avoid the expense, limited availability and time involved for performing an experimental cell-based assay for resistance where results can take four weeks. accurate predictions can be valuable for prescribing the most effective drugs for infections with resistant hiv. most genotype interpretation algorithms in clinical use are knowledge based. these interpretation algorithms apply a set of rules or scores for each mutation and drug. the performance of several commonly used interpretation algorithms: stanford hivdb, hiv-grade, rega and anrs has been compared. in addition, many computational classification techniques have been evaluated for predicting drug resistance from the genotype data. the standard classification techniques of artificial neural networks, decision tree, random forests, support vector machine and regression analysis have been applied in hiv drug resistance predictions. statistical methods can also be applied to analyze the relationship between genotype and phenotype. the association of mutations with resistance to the pis saquinavir and indinavir was determined using cluster analysis, recursive partitioning, and linear discriminant analysis. these methods are limited by the high dimensionality of the genotype data, hence non-parametric methods have been proposed and tested on resistance data for the pi amprenavir. protein structural information has been used to generate statistical potentials of mutants for training with svm or random forest learning algorithms and tested in predicting resistance to the rt inhibitor nevirapine. we have evaluated an efficient encoding of information from the three-dimensional protein structure for the prediction of resistance from genotype. the structural encoding via delaunay triangulation improves the quality of the predictions by representing interactions between amino acid neighbours in the three-dimensional structure unlike the linear sequence representation of other methods. this unified sequence-structure representation was used in supervised training with svm, ann, and a new sparse dictionary classification method. the compressive sensing/sparse dictionary representation has been applied successfully in image analysis to enhance learning capacity and efficiency. sparse representation has been employed for image restoration, denoising, deblurring, signal processing, and face detection. initial tests of this procedure for classifying resistance to four pis was presented in. here, the structural encoding has been expanded to regression analysis and classification of genotype-phenotype data for seven pis, six nrtis and three nnrtis.  we combined structural information with genotype for regression analysis and supervised learning on resistance data. the new graph based sequence-structure encoding was tested with the genotype-phenotype data from the stanford hiv drug resistance database. data were available for two different protein targets: hiv- pr and hiv- rt. for hiv- pr, eight pr inhibitors atazanavir, idv, nelfinavir, ritonavir, lopinavir, tipranavir and sqv were tested. while for the study of hiv rt inhibitor resistance, nnrtis nevirapine, delaviridine, efavirenz, and nrtis lamivudine, abacavir, zidovudine, stavudine, didanosine and tenofovir were tested. the data include the protein sequence and resistance value from the phenosense assay for each virus isolate. genotype-phenotype data were available for to isolates for different inhibitors of hiv pr, while rt was represented by to records for the different nrtis and nnrtis. the preprocessing of the sequence and resistance data is detailed in methods. genotypes were expanded to unique protein sequences due to the presence of more than one amino acid at some positions. this expansion resulted in a total of to unique sequences of hiv pr mutants and to rt mutants for the various inhibitor resistance values. graph based protein sequence/structure representation using delaunay triangulation the sequences were combined with information from the three-dimensional protein structures by employing a graph generated by delaunay triangulation as described in. two structure templates were used: 3oxc for hiv- pr, and 2wom. only one structure vector is needed for each protein. in other words, all pr mutant sequences are combined with a single 210-dimensional vector derived from one pr structure, and similarly, a single structure vector is used for the rt mutants in subsequent regression and classification of resistance data. as a result, all mutants are represented as vectors of constant dimensionality, which is a desirable property for most of the pattern recognition algorithms. this structure vector was combined with sequences in regression analysis and classification for resistance. multiple regression on hiv protease inhibitor resistance after each of the mutated sequences was represented by a 210-dimensional vector, we performed the regression analysis for the drug resistance data. we performed k-fold regression analysis on the sequence and resistance data. the predicted values for relative resistance are plotted against the experimental values as shown in for the pr inhibitors atv, nfv, rtv, idv, lpv, tpv and sqv. the multiple regression gave high r values of - and very low standard deviations as listed in table the values are the average of all the r values from k-fold regression. the high variance seen for high values of resistance is likely due to limitations of the experimental assay such that the measured resistance value has a cutoff at the upper limit, while the viral strains may have an effective resistance above this cutoff. the excellent correlations demonstrate that relative resistance to pis can be predicted successfully from genotype by the new sequence/structure encoding method. in order to avoid training to an "optimal" n-fold set for cross validation, cross validation sets are chosen independently for each training run. therefore, there is always a small variation in the results. multiple regression on hiv reverse transcriptase inhibitor resistance multiple regression analysis was performed similarly on genotype-phenotype data for drugs inhibiting hiv- rt. the predicted and observed values are compared for resistance to nrtis: 3tc, abc, d4t, ddi, tdf and azt in figure 3; and nnrtis: npv, dlv and efv in figure the regression results gave high r values of - for the different rt inhibitors, as shown in tables and the resistance to nrtis was predicted with excellent r values of - and very low standard deviations, while resistance predictions for nrtis gave r values in the larger range of -. larger standard deviations were obtained for analysis of abc and ddi possibly because the range of values in the dataset was smaller than for the others. therefore, graph based encoding had excellent success in predicting resistance to rt inhibitors. classification of resistance with support vector machine the support vector machine was proposed by vapnik, and is widely used as a supervised learning classifier in the machine learning classification area. in this experiment, 5-fold cross validation tests were performed by implementing in matlab svm toolbox and the linear kernel was used. the results are shown in tables for hiv- pr inhibitors, hiv- rt nrtis and hiv- rt nnrtis. this classification shows high accuracy, sensitivity and specificity for all inhibitors. for pis the accuracy values range from a low of to a high of, while sensitivity and specificity range from - and -, respectively. resistance to nrtis is classified with even higher accuracies of -, sensitivities of greater than and specificities of -, while for nnrtis the classification performance was superior with all values of over for accuracy, sensitivity and specificity. the excellent performance with the linear svm kernel demonstrates conclusively that the novel encoding using delaunay triangulation separates the resistant and non-resistant data into two distinct categories. classification with artificial neural networks as in the svm experiment, the 5-cross validation test was applied to the artificial neural networks to classify genotype-phenotype data for resistance. specifically, the three-layer feedforward network was used in matlab. the network had one hidden layer of nodes and was trained with backpropagation with a maximum of training epochs. the results are shown in tables for hiv- pr inhibitors, and rt inhibitors nrtis and nnrtis. the values calculated for accuracy, sensitivity and specificity for resistance to pis have a low of and reach. improved performance was achieved for classifying resistance to rt inhibitors compared with pis. results for nrtis gave values of accuracy, sensitivity and specificity of -, while for nnrtis all values were greater than. classification using sparse dictionary the sparse dictionary classifier was also implemented using the 5-fold cross validation tests using the approach described in. the results are shown in tables for hiv- pr inhibitors, hiv- rt nrtis and nnrtis. high values were obtained for accuracy, sensitivity, and specificity. accuracies ranged from - for resistance to pis, - for nrtis and - for nnrtis. the sensitivities were all greater than for the calculations on resistance to pis, and specificities were greater than. lower values were obtained for calculations on some of the rt inhibitors where values for sensitivity ranged from to, while high specificity values from to was calculated. these performance measures are somewhat poorer than for the standard svm and ann classifiers. it is not surprising; however, that more development may be necessary for applying the new sparse dictionary as a classifier since previously it has been employed primarily for image processing. comparison with standard genotype interpretation methods finally, we compared our methods with the standard drug resistance prediction methods hiv-grade, anrs-rules, stanford hivdb, and rega, which are available at http://www.hiv-grade.de/cms/grade/, using the same genotype-phenotype datasets described in methods. the procedure discussed in was used to convert the protein sequences into nucleotide sequences. other methods usually give resistance interpretations in three categories of "resistance, "intermediate" and "susceptible". since multiple classification is difficult with svm and ann, only two classes were considered for calculating the accuracy. both "resistant" and "intermediate" are considered as "resistant"; while "susceptible" is considered as "non-resistant". the results are shown in tables for hiv- pr inhibitors, hiv- rt nrtis and nnrtis. n/a means that no output was obtained from the server for this dataset. the accuracies demonstrate that classification with our structural encoding significantly outperforms other state of the art methods for predicting resistance to pis for the three tested classifiers svm, ann and the sparse dictionary. accuracies of - % were obtained with structural encoding compared to - % for the standard methods. the highest accuracies of greater than 95% were achieved with the sparse dictionary method. the prediction accuracy for resistance to the nrti class of rt inhibitors also showed the advantages of our structural encoding with values of - % compared with - % for standard methods. in this case, the svm and ann classifiers performed better than the new sparse dictionary giving accuracies of at least 97%. for the nnrtis, the structural encoding with svm or ann gave higher accuracies of - % compared with - % for standard methods. the sparse dictionary, however, showed lower performance with accuracies of - % for nnrti resistance, indicating some improvements may be needed for the new classifier. discussion the serious problem of drug resistance arising during therapy of hiv-infected individuals can be tackled by sequencing the hiv drug targets to identify mutations followed by computational prediction of resistance to guide the choice of effective therapy. computational predictions of the most effective drugs for the mutated hiv provide a major advantage of low cost and speed relative to experimental assays for resistance. most standard prediction methods are knowledge based methods, such as the genotype interpretation algorithms. these algorithms either use a set of rules, for example, the visible genetics/bayer diagnostics genotype interpretation rules, to generate the susceptibility of the infecting virus for each drug; or apply a score or'penalty' for each drug such as the stanford hiv database and mutation rate based score. also, a combined rule-based and penalty-based method has been proposed and applied to both hiv- pr and rt inhibitors. although these methods are fast, they suffer from the major disadvantage of relying on specific known mutations strongly associated with resistance and cannot identify newly appearing resistance mutations, or assess the effects of many mutations more weakly associated with resistance. various machine learning and statistical methods have been applied to this problem, including the widely used classifiers, ann, decision tree, and svm. statistical methods such as cluster analysis, recursive partitioning, and linear discriminant analysis have been evaluated, and non-parametric methods proposed for high dimensionality data. most of these methods are based on the linear protein sequence and omit potentially valuable information from the three-dimensional protein structure. additional information has been introduced in the form of physicochemical descriptors for the amino acid mutations leading to correlation coefficients of -. other groups have included structural features such as pr-drug contacts in the binding site with majority voting. in another example, delaunay triangulation of the rt structure was combined with a four-body statistical potential derived from protein structures in predictions for resistance to nvp and gave cross-validated accuracies of 85% with svm and 92% with random forest classifiers. molecular mechanics calculations on the pr-drug structure have been used to predict resistance of mutants, and gave high correlation between caclulation and ic from the experimental assay. however, these calculations must be performed for each mutant-drug combination and will be slow for assessing large numbers of mutants for resistance. we have developed a simple graph representation of protein structure for fast classification. the protein structure is a three-dimensional object that has many physical and chemical factors potentially effecting stability and activity. previously, we showed that delaunay triangulation was the best of several tested graph-based encodings of protein structure and sequence. the graph-based encoding algorithm condenses a complicated three-dimensional object, a protein structure, into a relatively small hash function with unique values per sequence and structure. one critical outcome is that the graph-based encoding results in a linearly separable data set that can be used readily by several different machine learning algorithms. similarly, the encoding is sufficiently linear that straightforward multiple linear regression can be performed on the training data. the hash value maintains enough information about the complicated object to provide useful information for machine learning and regression. this unified sequence-structure encoding gave high accuracy in initial tests on four pis. here, we demonstrate successful application of the structure vector in multiple regression analysis and classification on resistance data for seven inhibitors of hiv pr and nine inhibitors of rt. the 5-fold validated regression analysis gave excellent correlation between predicted and observed resistance with excellent r values of - for pis, - for nrtis and - for nnrtis. classification with svm, ann or a new sparse dictionary method gave high accuracies for predicting the resistance for pr and rt inhibitors. the structure vector encoding had superior accuracy to predictions on the same sequences using standard interpretation algorithms. the sparse dictionary classifier was the best of tested classifiers for prediction of resistance to pis, whereas svm classification gave the best performance on resistance prediction for rt inhibitors. this structure vector encoding of genotype data has the advantage of using a single 210-dimensional vector for each protein target. the algorithm has one slow step for preparing the encoding from a single protein structure that can be applied to all genotypes in a fast calculation, in contrast to molecular mechanics calculations that must be set up in a non-trivial manner for each individual protein sequence. the entire protein sequence is combined with the structure vector, so there is the potential for accommodating new mutations or combinations of mutations with weak but concerted effects on resistance. the procedure can be extended easily in future calculations for resistant mutants with insertions in the protein sequence, which occur commonly in rt. the new sparse dictionary classification approach can be extended to multiple classifiers by using more than two dictionaries, which is a significant advantage over the tested standard svm or ann classifiers, and may permit accurate predictions for different levels of resistance.  the simple unified encoding of structural information with genotype gives high accuracy for prediction of resistance to hiv pr and rt inhibitors as well as excellent correlation coefficients in regression analysis. the improvement over algorithms using only linear sequence information suggests the importance of local interactions between mutated residues in the protein structure, which is consistent with the correlated local changes observed in the crystal structures of a highly resistant pr mutant with substitutions. graph-based encoding of sequence and structure holds promise for fast and accurate predictions of resistance from sequence in order to guide the choice of effective drugs for treatment of hiv infections. in future, this approach can be expanded to predict resistance for other drugs and more diverse types of data. materials and methods data sets and data preparation all the datasets were retrieved from genotype-phenotype data on the stanford hiv drug resistance database. in this experiment, the proposed algorithm was tested on two different systems: hiv- pr and hiv- rt resistance data. for hiv- pr, eight pr inhibitors atazanavir, indinavir, nelfinavir, ritonavir, idv, lpv, tpv and sqv were tested. while for the study of hiv rt inhibitor resistance, nnrtis nevirapine, delaviridine, efavirenz, and nrtis lamivudine, abacavir, zidovudine, stavudine, didanosine and tenofovir were tested. for the drug resistance study on the hiv pr and hiv rt inhibitors, all the genotypes were expanded to individual unique amino acid sequences using the method discussed in. this expansion was needed since the genotyping experiment resulted in more than one possible amino acid at several positions in each genotype, due to potential experimental error or existence of multiple viral sequences infecting one patient. for each of the hiv- pr inhibitors the results were: for the inhibitor idv, a total of sequences were obtained from isolates; for the inhibitor lpv, a total of sequences were obtained from isolates; for the inhibitor tpv, a total of sequences were obtained from isolates; for the inhibitor sqv, a total of sequences were obtained from isolates; for the inhibitor atv, a total of sequences were obtained from isolates; for the inhibitor idv, a total of sequences were obtained from isolates; for the inhibitor nfv, a total of sequences were obtained from isolates; and for the inhibitor rtv, a total of sequences were obtained from isolates. for each of the hiv- rt inhibitors the results were: for the inhibitor npv, a total of sequences were obtained from isolates; for the inhibitor dlv, a total of sequences were obtained from isolates; and for the inhibitor efv, a total of sequences were obtained from isolates; for the inhibitor 3tc, a total of sequences were obtained from isolates; for the inhibitor abc, a total of sequences were obtained from isolates; for the inhibitor azt, a total of sequences were obtained from isolates; for the inhibitor d4t, a total of sequences were obtained from isolates; for the inhibitor ddi, a total of sequences were obtained from isolates; for the inhibitor tdf, a total of sequences were obtained from isolates. all positive and negative instances of a given mutant were removed from either training or testing dataset before the cross-validation. this may avoid the potential problem of having negative instances associated with a positive test item or positive instances associated with a negative test item, and thus assure the training accuracy. pre-processing of the datasets in order to unify the data in the original datasets, those sequences with an insertion, deletion, or containing a stop codon relative to the consensus have been removed so that the data represent proteases of amino acids. many of the sequence records in the dataset have multiple mutations at the same sites yet share the same drug-resistance value, which may be due to sequencing limitations or to the existence of multiple viral strains in the same isolate. in order to represent a single amino acids sequence for each mutant protein, we need to expand the data to multiple sequences with single amino acids at each location. for instance, in one 99-amino acid mutant of hiv pr, at one site there are two different types of amino-acids, and another site has three. in this case, this record must be expanded to a total of = different sequences, each of which has only one amino-acid for each of its residues, sharing the same drug resistance. we designed a fast way to perform this expansion as detailed in, which significantly enriches the test data.) cutoffs for resistance/susceptibility for each drug for the hiv- pr inhibitors: atv, idv, nfv, and rtv, among all these genotype sequences, those mutants with the relative resistant fold < were classified as non- resistant, denoted as 0; while those with the relative resistant fold ≥ were classified as resistant, denoted as. with the hiv- rt inhibitors: for abc and tpv, those mutants with the relative resistant fold < were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥ were classified as resistant, denoted as 1; for 3tc, azt, npv, dlv, efv, sqv, idv and lpv those mutants with the relative resistant fold < were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥ were classified as resistant, denoted as 1; for d4t, ddi and tdf, those mutants with the relative resistant fold < were classified as non-resistant, denoted as 0; while those with the relative resistant fold ≥ were classified as resistant, denoted as. encoding structure and sequence with delaunay triangulation the sequence and structure of the protein were represented using a graph-based encoding as described in. delaunay triangulation was used to define a graph which spanned the protein structure and defined adjacent pairs of amino acid residues. adjacent pairs of amino acids were summarized into a vector of the unique kinds of amino acid pairs by calculating the distance for each adjacent pair in the structure and tabulating by the types of amino acids in that adjacent pair. only the sequences of the mutated proteins are needed and only one protein structure is necessary. as a result, all mutants are represented as vectors of the same dimensionality, which is a desired property for most of the pattern recognition algorithms. the structures 3oxc for hiv- pr, and 2wom for hiv- rt were used as templates for delaunay triangulation. k-fold validation in order to fully use all the data, a k-fold cross-validation was performed in all the experiments for all the drugs. specifically, we randomly choose /k of all the sequences for training the classifier and the remaining 1/k data are used for testing. these tests used k = independent randomly selected k-folds were chosen throughout the study to avoid bias in the results. regression analysis for drug resistance prediction the genotype-phenotype datasets provide a drug resistance value, with respect to a certain type of drug, with each genotype. the mutations relative to a standard sequence are denoted as x x …,xn;xi∈ℜ where n is the total number of mutations and ℜ is the structure vector. also the corresponding drug resistance values are denoted as the real numbers y y …,yn;y∈ℜ including for the resistance value of the wild type virus. we then seek a linear model between the xi's and yi's by minimizing the cost function e: e:=∑i=1n with respect to the dimensional vector a and scalar b. furthermore, in order to better utilize the available data set, we performed a k-fold cross-validation. specifically, the training set of size n is randomly divided into k groups. among them, k - groups are utilized for constructing the linear model as in equation. then, the linear model is used to predict the drug resistance for the remaining group with n/k mutations. the predicted resistances are compared with the measured ones and the r values are recorded. finally, the average and standard deviation of the k r values are computed. sparse dictionary classification in this experiment, we applied our newly proposed method described in on both hiv- pr and hiv- rt data sets. in this case, the sequences of the mutants are considered as the group of signals, and given these signals, we would like to construct a dictionary to represent them sparsely. the construction of a dictionary can be considered as finding a suitable over-complete basis, in which the signals of interest would be represented with far fewer non-zero coefficients, than in an arbitrary fixed basis such as a fourier basis. the newly constructed basis is also called a dictionary. this dictionary can be used to assess how well the new signal fits the model represented by the dictionary, and therefore, it can be used as a new classification method. in our experiment, we assume there are groups of signals: one for drug resistant mutants, while the other group is non-drug resistant mutants. we construct two dictionaries for each group, respectively. after that, given a new signal, we use both dictionaries to represent this signal. by calculating and comparing the reconstruction error, the dictionary with the smaller error indicates that the signal belongs to this category. based on the theory of the dictionary, it can be observed that the group number is not limited to and such procedure could be used as a multi-group classification method. the dictionaries for each set of drug resistance data were constructed and the classification performed as described in. list of abbreviations haart, highly active antiretroviral therapy; pr, hiv protease; pi, protease inhibitor; rt, hiv reverse transcriptase; nrti, nucleoside rt inhibitor; nnrti, non-nucleoside rt inhibitor; ann, artificial neural networks; svm, support vector machine; apv, amprenavir; atv, atazanavir; idv, indinavir; lpv, lopinavir; nfv, nelfinavir; rtv, ritonavir; sqv, saquinavir; tpv, tipranvir; 3tc, lamivudine; abc, abacavir; azt, zidovudine; d4t, stavudine; ddi, didanosine; dlv, delaviridine; efv, efavirenz; nvp, nevirapine; tdf, tenofovir. competing interests the authors declare that they have no competing interests. authors' contributions all authors designed the experiments. xy and rwh designed the algorithms. xy implemented the algorithms and ran the predictions. all authors interpreted the results and wrote the manuscript. all authors read and approved the final manuscript. 
the method was tested on genotype-resistance data for mutants of hiv protease and reverse transcriptase. the approach of encoding the protein structure and sequence as a 210-dimensional vector, based on delaunay triangulation, has promise as an accurate method for predicting resistance from sequence for drugs inhibiting hiv protease and reverse transcriptase. prediction of resistance from genotype data is a valuable guide in choice of drugs for effective therapy. in order to improve the computational prediction of resistance from genotype data we have developed a unified encoding of the protein sequence and three-dimensional protein structure of the drug target for classification and regression analysis. drug resistance has become a severe challenge for treatment of hiv infections. cross-validated regression analysis with the sparse dictionary gave excellent correlation between predicted and observed resistance. our graph based sequence-structure approach gives high accuracy with a new sparse dictionary classification method, as well as support vector machine and artificial neural networks classifiers.
 drug resistance has become a severe challenge for treatment of hiv infections. mutations accumulate in the hiv genome and make certain drugs ineffective. prediction of resistance from genotype data is a valuable guide in choice of drugs for effective therapy.  in order to improve the computational prediction of resistance from genotype data we have developed a unified encoding of the protein sequence and three-dimensional protein structure of the drug target for classification and regression analysis. the method was tested on genotype-resistance data for mutants of hiv protease and reverse transcriptase. our graph based sequence-structure approach gives high accuracy with a new sparse dictionary classification method, as well as support vector machine and artificial neural networks classifiers. cross-validated regression analysis with the sparse dictionary gave excellent correlation between predicted and observed resistance.  the approach of encoding the protein structure and sequence as a 210-dimensional vector, based on delaunay triangulation, has promise as an accurate method for predicting resistance from sequence for drugs inhibiting hiv protease and reverse transcriptase. 12- june third ieee international conference on computational advances in bio and medical sciences new orleans, la, usa 