BACKGROUND
determination of binding between peptide and major histocompatibility complex class i  is a crucial step in the development of subunit vaccines.
the peptide-mhci complexes are required for t cell activation and thus for the initiation of the adaptative immune response.
although mhci binding does not alone determine the immunogenicity of peptides, it plays an important part, being a major bottleneck that separates immunogenic peptides from non-immunogenic ones.
hence, the ability to predict the binding between peptides and mhci molecules would greatly reduce costs and accelerate the experimental process of identifying immunogenic peptides, which can then be used in the development of vaccines and therapies against neoplastic, infectious, and autoimmune diseases.
our primary goal is to guide experimental research in identifying potential vaccine epitopes.
in a given microbial genome, there are tens of thousands of peptides and the experimental assessment of the affinity between each peptide and an mhci molecule represents a significant cost in terms of time and resources.
the investigator has to consider the benefits of identifying binders versus the cost associated with experimentally testing nonbinders in order to decide which and how many peptides will be tested in the laboratory.
this type of concern can be best addressed by the use of decision-theoretic approaches.
here we formalize such an approach to training decision trees to differentiate binders from nonbinders and show how costs that reflect this experimental tradeoff can be incorporated into the training of classifiers to increase their utility.
myriad approaches have been applied to the prediction of peptide-mhci binding.
these methods can be divided into two broad categories: 1) mhci structure-based methods, which use crystallized structures of mhci molecules to develop computational models of the interaction between mhci and peptides  <cit> ; and 2) peptide sequence-based methods, which infer the physico-chemical preferences of a particular mhci allele by analyzing the amino acid sequence of peptides with known affinity to it, where peptides with ic <dig> lower than a certain threshold, typically  <dig> nm  <cit> , are classified as binders, and otherwise as nonbinders.
earlier prediction methods used the amino acid frequencies in each position of mhci-eluted peptides to derive binding motifs and position specific scoring matrices .
methods of this type include syfpeithi  <cit>  and bimas  <cit> , which have been publicly available and used extensively by the experimental community.
as the number of peptides in the mhci databases increased, so did the number of different machine learning methods that were applied to this problem, which include artificial neural networks  <cit> , support vector machines  <cit> , hidden markov models  <cit> , gibbs sampling  <cit> , and classification trees  <cit> .
while some of these methods achieve outstanding performance in predicting binding between peptides and certain mhci alleles, all of them suffer from the fact that the available data for training is heavily biased towards one class of peptides .
there is a vast literature on the impact of class distribution of training sets on the performance of the prediction algorithms , and although there is not a straightforward answer to the question of what the ideal class distribution of training datasets is, it has been suggested that a balanced distribution or the estimated distribution of the target population should be used.
moreover, it is a well known phenomenon that highly unbalanced datasets are detrimental to classifier performance.
the imbalance in the peptide-mhci binding data depends on the experimental methods used to produce them: either elution assays, in which case the dataset consists purely of binders; or binding assays in which peptides are tested for binding or affinity to a particular mhci allele, leading to datasets consisting mostly of nonbinders.
the reason for this imbalance towards nonbinders is that binders are extremely rare in nature: it has been estimated that the proportion of peptides in a protein that will bind to a given mhc allele varies between  <dig>  and  <dig>   <cit> .
datasets generated in different laboratories using different assays and conditions are often inconsistent with each other and thus combination of datasets can be very difficult.
here we investigate how best to use unbalanced datasets to train algorithms for the prediction of peptide-mhci binding.
although there is no universally agreed upon method for dealing with unbalanced data, several techniques have been proposed to deal with this issue and have been demonstrated to improve prediction accuracy depending on the context in which they are used  <cit> .
elkan  <cit>  showed how to make a standard learning algorithm yield cost-sensitive results when trained with an unbalanced dataset.
another successful strategy is referred to as cost-sensitive methods, in which weights are used to compensate for the imbalance in the ratio of the two classes.
other methods pre-process the data to achieve a balanced class distribution.
in particular two resampling methods stand out: 1) undersampling, where random cases of the majority class are deleted until both classes have the same number of cases; and 2) oversampling, where random cases of the minority class are duplicated until both classes have the same number of cases.
our primary goal is to determine whether or not the accuracy of peptide-mhci binding prediction can be improved by the use of methods that compensate for the training data imbalance, such as resampling and cost-sensitive methods.
the results presented herein suggest that resampling procedures, such as undersampling and oversampling, do not consistently improve the utility of classifiers used in the context of peptide-mhci binding.
the cost-sensitive method, however, significantly improves prediction accuracy when the training data is biased towards nonbinders.
these results are derived from analysis using decision trees.
the underlying mathematical treatment is, however, quite general, and can be applied to any classifier capable of cost-sensitive learning, including most of the classifiers used in peptide-mhci binding prediction.
methods
approach
the development of subunit vaccines is a multi-step process; at each stage, the investigators must decide whether a particular peptide warrants further investment or should be omitted from further experimentation.
these decisions must be informed, either explicitly or implicitly, by consideration of the costs incurred in continuing the experiments and of the potential reward for a positive discovery.
one must also estimate the probability that a given decision will be erroneous, either as a false positive  or a false negative .
let the cost of misclassifying a binder be denoted κ <dig>  and that for misclassifying a non-binder, κ <dig>  we refer to κ <dig> as the "real-world" cost, as it can be interpreted as the number of nonbinders an investigator is willing to test in the laboratory in order to find one binder.
finally, suppose that we can parameterize a family of classifiers with the continuous vector θ. then the cost, k, incurred in making a decision on a peptide ϕ using the classifier t is
k = τ+κ2c- + τ-κ1c+,
where τ+ and τ- are indicators of true class and c+ and c- are indicators of the classification induced by t. the expected decision cost over all peptides is
ek=πk2∈2+k1∈ <dig>
where π is the proportion of binders in the population and ϵi is the expected rate of type i errors.
we would like to find the classifier t* that minimizes this expected cost.
in the training context, we use the "training cost function", kt, which has the same form as the decision cost described above, but differs from it in the fact that both the false positive λ <dig> and false negative λ <dig> costs are now tunable parameters:
kt = τ+c-λ <dig> + τ-c+λ <dig>
because we only ever have access to finite datasets to train classifiers, the training cost from using such classifiers can be decomposed into two parts: the decision-making cost described in eq.
<dig> and the residual, due to the deviation of the training set d from the whole population:
kt=n{pλ2ϵ2+λ1ϵ1}+∑ϕ∈d{τ+λ2δc−+τ−δc+}
where n is the size of the training dataset, p is its proportion of positives and the classification error is defined on positive  peptides as
δc- ≡ c- - ϵ <dig>
we may further abbreviate this expression to
kt = n {pλ2ϵ <dig> + λ1ϵ1} + r.
the expected decision cost described in eq.
<dig> is minimized at θˆ where
0=∂∂θek=πκ2∂ϵ2∂θ+κ1∂ϵ1∂θ.
similarly, the training cost function is minimized at θ * where
0=∂∂θl=pλ2∂ϵ2∂θ+λ1∂ϵ1∂θ+∂r∂θ.
denote the value of θ that minimizes the expected decision cost by θˆ, and that that minimizes the training cost function by θ * = θˆ + 1/n δθ.
now differentiation and taylor expansion yield the sufficient condition for the minimum of the training cost function to approach θˆ as r/n → 0:
λ2b=π1−π1−ppκ2κ1λ <dig>
this expression defines what we refer to as the "balancing cost", λ2b.
the basic intuition behind the balancing cost is that its use results in both classes having equal importance in the training of the classifier.
it is helpful to note that: 1) as the real-world false negative cost κ <dig> increases, so does the balancing cost; and 2) as the proportion of positives p in the training set increases in relation to the population positive frequency π, the balancing cost decreases .
finally, we have
δθ=−∂r∂θ− <dig>
with the right-hand side evaluated at θˆ, which provides a first-order correction for finite datasets.
figure  <dig> displays the relation between population and training sample positive proportions and costs as described in eq.
<dig> and can serve as a guideline of what weights to assign to peptides of different classes given the class distribution in the training set and the relative importance of positives versus negatives in the real-world application.
datasets
the peptide binding data used to train and test the decision trees were obtained from a publicly available database published by peters et al.
<cit> , where the peptide affinity to a particular mhci molecule is measured by one of two assays, and classified as binder when its ic <dig> is less or equal to  <dig> nm, and nonbinder otherwise.
decision trees were constructed for each one of  <dig> alleles in the dataset.
the cost-sensitive and resampling experiments  were performed for five alleles: a <dig>  a <dig>  a <dig>  b <dig> and b <dig>  the numbers of peptides in the datasets for these five alleles are shown in table  <dig>
cost adjustments
seven training sets for each allele studied were generated, such that all training sets for a given allele had the same number of observations but varying proportions p of positives, namely 5%, 10%, 25%, 50%, 75%, 90% and 95%.
these training sets were created as follows.
first, 25% of the binders and 25% of the nonbinders were randomly selected and set aside as a testing set.
the remaining 75% of the binders and of the nonbinders formed the "training superset", from which the peptides for the various training sets were sampled.
the total number of peptides in each of the seven training sets was fixed and equal to the number of peptides of the minority class in the training superset.
the minority class was the positive for all  <dig> alleles that we tested.
finally, the training sets were formed by randomly sampling without replacement positive and negative peptides from the training superset such that the described class distribution was reached.
the numbers of binders and nonbinders in the resulting training sets are shown in table  <dig>
number of binders  and nonbinders  in training sets.
the goal of this set of experiments was two-fold: 1) to investigate the relationship between class distribution and classifier performance, and 2) to learn how can misclassification costs be used to improve prediction accuracy for a given class distribution of the training set.
we emphasize that our goal is not to improve upon existing computational methods, but rather to show that the performance of a single classifier can be improved with the use of cost-sensitive techniques.
misclassification costs were used as weights with the purpose of artificially changing the class distribution of the training dataset.
the false negative cost  can be interpreted as the weight given to the peptides in the positive class, and similarly false positive cost  is the weight given to the negative class.
the overall scale of the training cost function  is arbitrary, so we have fixed λ <dig> =  <dig> and varied λ <dig> between 1/ <dig> and  <dig> in order to investigate the relationship between costs and class distribution.
previous works  have suggested that among the best class distributions for learning is the balanced distribution, one in which all classes are equally represented.
we assume that given an unbalanced training set, a balancing misclassification cost can be used to achieve an artificially nearly-balanced class distribution.
the balancing cost, λ2b, defined in eq.
<dig> can be interpreted to be the λ <dig> that weights the positive peptides to be the same number as the negatives and therefore compensates for the imbalance ratio of the two classes.
consider the simplest scenario, where λ <dig> =  <dig>  κ <dig> =  <dig>  κ <dig> =  <dig> and π =  <dig> , then the balancing cost reduces to
λ2b=p
we are particularly interested in how classifiers trained with this simplified balancing cost perform compared to the best classifiers for a given allele, as well as compared with classifiers trained with unit costs .
resampling
undersampling
the undersampling method consists of randomly eliminating peptides of the majority class from the training set until both classes have the same number of examples.
the training sets were constructed in a similar manner to the cost-modifying experiment.
first, we set aside 25% of binders and nonbinders into the testing set.
the remaining binders were put into the training set together with the same number of nonbinders, which were randomly sampled without replacement from the nonbinders training superset.
one of the issues concerning undersampling is the loss of information that results from the process, which can be aggravated when particularly important elements are removed from the training set.
to get around this problem, we used 10-fold crossvalidation and the results presented here are the average of the  <dig> experiments.
oversampling
the oversampling method consists of randomly replicating peptides of the minority class into the training set until both classes have the same number of examples.
the training sets were constructed as follows.
first, we set aside 25% of binders and nonbinders into the testing set.
all remaining peptides were put into the training set together with d peptides from the minority class which were sampled with replacement, where d is the difference between the number of peptides in the the training set belonging to the majority and minority classes.
hence, each peptide of the minority class is represented at least once and possibly multiple times in the training set.
similarly to the undersampling procedure, we used 10-fold crossvalidation and the results presented here are the average of the  <dig> experiments.
decision trees
the present study applies tree-based models to the peptide-mhci binding prediction problem.
we have chosen to use decision trees for the simplicity in their interpretation and also because they have not been thoroughly explored in the context of peptide-mhci binding.
moreover, decision and classification trees have become the canonical method for comparison of techniques used to deal with unbalanced datasets in the machine learning community.
finally, there seems to be a natural correspondence between the importance of the different residue positions in a peptide and the hierarchical way in which decision trees are constructed.
tree generation
breiman et al.
<cit>  provides an excellent and detailed description of classification and regression trees.
briefly, given a dataset in which each object, φ, is represented by a , x) pair, where x is a vector containing attributes of the object and τ is an indicator function of the class of the object, a tree-based classifier recursively partitions the data's attribute space into sub-regions, called nodes, in which the response variable is increasingly more homogeneous.
these trees are created in two steps:  induction of a large tree; and  pruning of the large tree into gradually smaller subtrees .
finally, one subtree must be chosen from the sequence of subtrees generated by the pruning process.
in the present study, we chose the tree that minimizes the training cost function  when applied to the test set.
the construction of a tree requires  a set of splits, which are binary questions with mutually exclusive and exhaustive outcomes used to partition the data, where the questions are coined in terms of the attributes of the objects in the dataset; and  a split function used to quantify the goodness of a split, by measuring the change in the homogeneity of the response variable in the tree due to splitting a node into two subsets based on the given split.
splits and split function
in the problem at hand, the training dataset consists of peptides ϕ, where τ is the class of the peptide  and x is the linear sequence of amino acids of the peptide, with xj being the jth amino acid from the amino terminal end of the peptide.
the binary questions about the sequence of peptides can be phrased in several distinct ways, and each one of them generates a different class of splits, called motifs, that can be used in the construction of trees.
we used motifs based on the anchor positions, which are represented by a single amino acid with a fixed position in the peptide, such that every amino acid is represented in every position of the peptide.
the amino acids, in turn, can be represented in one of two ways: 1) by the traditional amino acid single-letter code.
for example, alanine is represented by "a", arginine by "r" and so forth; and 2) by their physico-chemical properties, namely molecular weight, hydropathicity, volume, isoelectric point, polarity, ability to form hydrogen bonds and chain type  as previously shown  <cit> .
the split function used was the training cost described in eq.
<dig>
RESULTS
cost adjustments
the first goal of this set of experiments was to investigate the relationship between class distribution and classifier performance.
our results suggests that for a fixed training set size, decision trees perform best when trained with datasets of nearly balanced class distribution.
figure  <dig> shows the performance of classifiers trained with datasets of the same size but different class distributions and training costs for alleles a <dig> and b <dig> .
note that as the proportion of positives in the training set increases, the false negative rate decreases and the false positive rate increases as can be seen by the subtle shift in the curves from left to right.
our second goal was to determine whether or not prediction accuracy of a given classifier can be improved by the use of cost-sensitive techniques and, if so, to establish the relationship between classifier performance and training costs.
our results demonstrate that misclassification costs can be used to improve prediction accuracy.
in fact, for each one of the alleles we tested there was a cost λ <dig> that performed significantly better than the unit cost, as can be seen by the increase in auc shown in table  <dig>  although our goal is not to improve upon the performance of existing methods, we also show in table  <dig> the auc for  <dig> other methods as described in  <cit>  for purposes of comparison.
the second and third columns correspond to the decision trees described in the present work.
note the improvement in the performance of the trees with the use of training costs.
*values extracted from table  <dig> of peters et al.,  <dig>
note in figure  <dig> that for the training sets with majority of nonbinders, λ2b consistently reduced the total error rate as compared to the unit cost .
the impact of λ2b on the performance of classifiers trained with binders-enriched datasets was not consistent, being better than unit cost for some classifiers and worse for others.
in addition to representing an improvement over the unit cost, in a few cases λ2b coincided with the minimizing cost, that is, the most accurate classifier for a given allele and training set was the one trained with λ2b.
however, in most cases, the balancing cost over-compensated for the imbalance in the class distribution, such that it was larger than the minimizing cost
we then compared the performance of trees trained with the complete dataset using either the unit cost or λ2b .
the use of λ2b resulted in auc at least as large as those for unit cost, such that λ2b improved the roc curves as compared to the unit cost in the majority of the cases.
one interesting feature of the use of λ2b is that it consistently shifts the roc curve toward increasing sensitivity at the price of decreasing specificity, which is a desirable tradeoff when binders are rare.
thus, even in the cases when the increase in auc is not substantial, the use of λ2b can still represent an improvement over unit cost due to the shift it causes to the roc curve.
resampling
the results obtained using the balanced undersampled and oversampled training sets did not represent an improvement over those using the complete unbalanced training sets .
for alleles a <dig>  a <dig> and b <dig>  the roc curves for the trees trained with the entire dataset and those trained with the re-sampled dataset were indistinguishable from one another, whereas for alleles a <dig> and b <dig>  the use of undersampling severely damaged the accuracy of the trees.
real-world costs versus training costs
we built decision trees with the training data described in table  <dig> using different values of false negative cost , and evaluated them on a test set using the "real-world" cost κ <dig>  we call λˆ <dig> the training cost that minimizes the total cost of a classifier on the test set for a given κ <dig>  figure  <dig> shows the relationship between λˆ <dig> and κ <dig>  note that although the results are relatively noisy, in general the same trend shown in theory can be observed from this empirical data .
the λˆ <dig> increases with κ <dig> and as the proportion of positives in the training set increases, the line shifts to the right, indicating that for a particular value of κ <dig>  the suggested λˆ <dig> decreases.
discussion
prediction of peptide-mhci binding has great potential to accelerate and reduce the cost of subunit vaccine development.
one of the issues concerning the prediction of mhc-peptide binding is that binders are much less abundant than nonbinders, and thus much harder to find experimentally.
this circumstance typically leads to highly unbalanced training sets, which can hinder the performance of algorithms trained with them.
in fact, such training sets lead to a significant increase of type  <dig> errors and thus make it more difficult still to find binders.
our results show that highly unbalanced training sets do indeed reduce the accuracy of predictions made with decision trees and that these predictions improve as the training sets become more balanced.
we have examined three approaches that aim at improving classifier accuracy by compensating for the imbalance in the class distribution of the training sets: undersampling, oversampling and a cost-sensitive method.
overall, resampling did not improve the performance of the decision trees.
in fact, in several cases classifiers trained with undersampled training sets performed much worse than those trained with the full dataset.
this could have been caused by the loss of information relevant to the training process.
for this reason, undersampling methods may only be appropriately used with datasets in which the majority class contains a lot of redundancy, in which circumstance undersampling has been shown to outperform other random resampling methods in four distinct datasets  <cit> .
another potential drawback of undersampling, and in broader terms of random resampling methods, is that they may yield noisy results due to the variability introduced in the process by the randomness of the sampling procedure.
in contrast to undersampling, using misclassification costs as a means to artificially counterbalance data bias led to significant improvements in the performance of the decision trees in the majority of the cases.
although cost-sensitive procedures do not add any extra information to the training set, they seem to be more advantageous than random resampling techniques because they do not cause loss of information as does undersampling and do not have the extra variability introduced by the random sampling process.
several other studies have shown cost-modifying methods to be advantageous.
for example, japkowicz and stephen  <cit>  performed a systematic comparison of these methods in both artificially-generated and real-world domains, showing that cost-modifying methods yield better results than resampling techniques.
fundamentally, the cost-sensitive method described here can be straightforwardly applied to any classifier that is trained using datasets that include both classes of peptides, binders and nonbinders.
for instance, the individual weights of a weight matrix can be derived by minimizing the cost function  over these weights.
the indicator function c- can be defined by the score function's being above or below a given threshold, where the scoring function is typically the sum of the scores of each amino acid in each position of a peptide.
similarly, this cost function can be incorporated into a neural network by differentially weighting the output depending on the class of the training example and allowing it to be used in the learning process by the backpropagation procedure  <cit> .
likewise, for support vector machines, the cost function can be implemented through the definition of the "soft margin"  <cit> , allowing the svm to misclassify more examples of one class than examples of the other class.
in addition to showing that peptide-mhci binding predictions can be improved by the use of cost-sensitive decision trees, we have investigated the use of the balancing cost, λ2b, as a rule-of-thumb to train classifiers.
we have shown that although λ2b is not always the λ <dig> that minimizes the total cost of the classifier, it consistently outperforms the unit cost  when the training set is enriched for nonbinders.
moreover, we have showed that the use of λ2b shifts the roc curves towards areas of higher sensitivity in relation to roc curves generated with unit cost, which can be highly desirable in situations such as epitope discovery projects.
thus, although the relationship between training costs and class imbalance is relatively noisy, and further studies should be conducted before a complete guideline of what training costs should be used for a particular peptide-mhci binding dataset, our results allow us to suggest that a balancing cost should be used for datasets enriched for nonbinders, and the unit cost should be used for binders-enriched training sets.
CONCLUSIONS
the vaccine development process is costly and time-consuming, requiring decisions to be made at each step and it lends itself nicely to a decision-theoretic approach, which we have described here.
in particular, at the epitope discovery stage, there are real costs associated with the risk of missing a positive and with the experimental verification of nonbinders.
here we have described a decision-theoretic framework for the prediction of peptide-mhci binding and have provided a guideline on how to incorporate real-world costs together with misclassification costs at the training level in order to maximize prediction accuracy and push it in the desired direction.
authors' contributions
aps performed the computational experiments, analyzed the data and wrote the manuscript.
tbk supervised the study and wrote the manuscript.
gdt supervised the pilot experimental studies and helped revise the manuscript.
supplementary material
additional file 1
classifier performance vs class distribution for alleles a <dig>  a <dig> and b <dig>  comparison of the performance of classifiers built with training sets of same size but different proportions of positives for alleles a <dig>  a <dig> and b <dig> .
each point in a curve represents a classifier constructed with a different false negative training cost.
the classifier constructed with the unit cost  in each curve is marked with a solid circle and that constructed with the balancing cost is marked with a star.
the curve for the perfect classifier would lie on the dotted line.
the y-axis shows the total error rate of a classifier, which is the same as the classifier cost  when the type  <dig> and type  <dig> misclassification costs are identical .
fnr: false negative rate.
fpr: false positive rate.
click here for file
additional file 2
comparison of unit cost, balancing cost, undersampling and oversampling for alleles a <dig>  a <dig> and b <dig>  roc curves for alleles a <dig>  and b <dig>  comparing the results of trees constructed with the oversampled training set , the undersampled training set , and the full training set without training costs, that is, λ <dig> = λ <dig> =  <dig>  and with the balancing training cost, that is, λ <dig> =  <dig> and λ <dig> = /p .
compare to figure  <dig>  the roc curves were constructed by varying the threshold used to label a node from  <dig> to  <dig> and evaluating its sensitivity and specificity at each threshold.
click here for file
acknowledgements
we thank cliburn chan for insightful discussions, yongting cai for sharing experimental data used in our pilot studies and kent weinhold for his leadership and guidance.
this work was supported by the large scale antibody & t cell epitope discovery program , under the nih grant n01-a1- <dig>

 determination of binding between peptide and major histocompatibility complex class i is a crucial step in the development of subunit vaccines. the peptide-mhci complexes are required for t cell activation and thus for the initiation of the adaptative immune response. although mhci binding does not alone determine the immunogenicity of peptides, it plays an important part, being a major bottleneck that separates immunogenic peptides from non-immunogenic ones. hence, the ability to predict the binding between peptides and mhci molecules would greatly reduce costs and accelerate the experimental process of identifying immunogenic peptides, which can then be used in the development of vaccines and therapies against neoplastic, infectious, and autoimmune diseases. our primary goal is to guide experimental research in identifying potential vaccine epitopes. in a given microbial genome, there are tens of thousands of peptides and the experimental assessment of the affinity between each peptide and an mhci molecule represents a significant cost in terms of time and resources. the investigator has to consider the benefits of identifying binders versus the cost associated with experimentally testing nonbinders in order to decide which and how many peptides will be tested in the laboratory. this type of concern can be best addressed by the use of decision-theoretic approaches. here we formalize such an approach to training decision trees to differentiate binders from nonbinders and show how costs that reflect this experimental tradeoff can be incorporated into the training of classifiers to increase their utility. myriad approaches have been applied to the prediction of peptide-mhci binding. these methods can be divided into two broad categories: 1) mhci structure-based methods, which use crystallized structures of mhci molecules to develop computational models of the interaction between mhci and peptides; and 2) peptide sequence-based methods, which infer the physico-chemical preferences of a particular mhci allele by analyzing the amino acid sequence of peptides with known affinity to it, where peptides with ic lower than a certain threshold, typically nm, are classified as binders, and otherwise as nonbinders. earlier prediction methods used the amino acid frequencies in each position of mhci-eluted peptides to derive binding motifs and position specific scoring matrices. methods of this type include syfpeithi and bimas, which have been publicly available and used extensively by the experimental community. as the number of peptides in the mhci databases increased, so did the number of different machine learning methods that were applied to this problem, which include artificial neural networks, support vector machines, hidden markov models, gibbs sampling, and classification trees. while some of these methods achieve outstanding performance in predicting binding between peptides and certain mhci alleles, all of them suffer from the fact that the available data for training is heavily biased towards one class of peptides. there is a vast literature on the impact of class distribution of training sets on the performance of the prediction algorithms, and although there is not a straightforward answer to the question of what the ideal class distribution of training datasets is, it has been suggested that a balanced distribution or the estimated distribution of the target population should be used. moreover, it is a well known phenomenon that highly unbalanced datasets are detrimental to classifier performance. the imbalance in the peptide-mhci binding data depends on the experimental methods used to produce them: either elution assays, in which case the dataset consists purely of binders; or binding assays in which peptides are tested for binding or affinity to a particular mhci allele, leading to datasets consisting mostly of nonbinders. the reason for this imbalance towards nonbinders is that binders are extremely rare in nature: it has been estimated that the proportion of peptides in a protein that will bind to a given mhc allele varies between and. datasets generated in different laboratories using different assays and conditions are often inconsistent with each other and thus combination of datasets can be very difficult. here we investigate how best to use unbalanced datasets to train algorithms for the prediction of peptide-mhci binding. although there is no universally agreed upon method for dealing with unbalanced data, several techniques have been proposed to deal with this issue and have been demonstrated to improve prediction accuracy depending on the context in which they are used. elkan showed how to make a standard learning algorithm yield cost-sensitive results when trained with an unbalanced dataset. another successful strategy is referred to as cost-sensitive methods, in which weights are used to compensate for the imbalance in the ratio of the two classes. other methods pre-process the data to achieve a balanced class distribution. in particular two resampling methods stand out: 1) undersampling, where random cases of the majority class are deleted until both classes have the same number of cases; and 2) oversampling, where random cases of the minority class are duplicated until both classes have the same number of cases. our primary goal is to determine whether or not the accuracy of peptide-mhci binding prediction can be improved by the use of methods that compensate for the training data imbalance, such as resampling and cost-sensitive methods. the results presented herein suggest that resampling procedures, such as undersampling and oversampling, do not consistently improve the utility of classifiers used in the context of peptide-mhci binding. the cost-sensitive method, however, significantly improves prediction accuracy when the training data is biased towards nonbinders. these results are derived from analysis using decision trees. the underlying mathematical treatment is, however, quite general, and can be applied to any classifier capable of cost-sensitive learning, including most of the classifiers used in peptide-mhci binding prediction. methods approach the development of subunit vaccines is a multi-step process; at each stage, the investigators must decide whether a particular peptide warrants further investment or should be omitted from further experimentation. these decisions must be informed, either explicitly or implicitly, by consideration of the costs incurred in continuing the experiments and of the potential reward for a positive discovery. one must also estimate the probability that a given decision will be erroneous, either as a false positive or a false negative. let the cost of misclassifying a binder be denoted κ and that for misclassifying a non-binder, κ we refer to κ as the "real-world" cost, as it can be interpreted as the number of nonbinders an investigator is willing to test in the laboratory in order to find one binder. finally, suppose that we can parameterize a family of classifiers with the continuous vector θ. then the cost, k, incurred in making a decision on a peptide ϕ using the classifier t is k = τ+κ2c- + τ-κ1c+, where τ+ and τ- are indicators of true class and c+ and c- are indicators of the classification induced by t. the expected decision cost over all peptides is ek=πk2∈2+k1∈ where π is the proportion of binders in the population and ϵi is the expected rate of type i errors. we would like to find the classifier t* that minimizes this expected cost. in the training context, we use the "training cost function", kt, which has the same form as the decision cost described above, but differs from it in the fact that both the false positive λ and false negative λ costs are now tunable parameters: kt = τ+c-λ + τ-c+λ because we only ever have access to finite datasets to train classifiers, the training cost from using such classifiers can be decomposed into two parts: the decision-making cost described in eq. and the residual, due to the deviation of the training set d from the whole population: kt=n{pλ2ϵ2+λ1ϵ1}+∑ϕ∈d{τ+λ2δc−+τ−δc+} where n is the size of the training dataset, p is its proportion of positives and the classification error is defined on positive peptides as δc- ≡ c- - ϵ we may further abbreviate this expression to kt = n {pλ2ϵ + λ1ϵ1} + r. the expected decision cost described in eq. is minimized at θˆ where 0=∂∂θek=πκ2∂ϵ2∂θ+κ1∂ϵ1∂θ. similarly, the training cost function is minimized at θ * where 0=∂∂θl=pλ2∂ϵ2∂θ+λ1∂ϵ1∂θ+∂r∂θ. denote the value of θ that minimizes the expected decision cost by θˆ, and that that minimizes the training cost function by θ * = θˆ + 1/n δθ. now differentiation and taylor expansion yield the sufficient condition for the minimum of the training cost function to approach θˆ as r/n → 0: λ2b=π1−π1−ppκ2κ1λ this expression defines what we refer to as the "balancing cost", λ2b. the basic intuition behind the balancing cost is that its use results in both classes having equal importance in the training of the classifier. it is helpful to note that: 1) as the real-world false negative cost κ increases, so does the balancing cost; and 2) as the proportion of positives p in the training set increases in relation to the population positive frequency π, the balancing cost decreases. finally, we have δθ=−∂r∂θ− with the right-hand side evaluated at θˆ, which provides a first-order correction for finite datasets. figure displays the relation between population and training sample positive proportions and costs as described in eq. and can serve as a guideline of what weights to assign to peptides of different classes given the class distribution in the training set and the relative importance of positives versus negatives in the real-world application. datasets the peptide binding data used to train and test the decision trees were obtained from a publicly available database published by peters et al., where the peptide affinity to a particular mhci molecule is measured by one of two assays, and classified as binder when its ic is less or equal to nm, and nonbinder otherwise. decision trees were constructed for each one of alleles in the dataset. the cost-sensitive and resampling experiments were performed for five alleles: a a a b and b the numbers of peptides in the datasets for these five alleles are shown in table cost adjustments seven training sets for each allele studied were generated, such that all training sets for a given allele had the same number of observations but varying proportions p of positives, namely 5%, 10%, 25%, 50%, 75%, 90% and 95%. these training sets were created as follows. first, 25% of the binders and 25% of the nonbinders were randomly selected and set aside as a testing set. the remaining 75% of the binders and of the nonbinders formed the "training superset", from which the peptides for the various training sets were sampled. the total number of peptides in each of the seven training sets was fixed and equal to the number of peptides of the minority class in the training superset. the minority class was the positive for all alleles that we tested. finally, the training sets were formed by randomly sampling without replacement positive and negative peptides from the training superset such that the described class distribution was reached. the numbers of binders and nonbinders in the resulting training sets are shown in table number of binders and nonbinders in training sets. the goal of this set of experiments was two-fold: 1) to investigate the relationship between class distribution and classifier performance, and 2) to learn how can misclassification costs be used to improve prediction accuracy for a given class distribution of the training set. we emphasize that our goal is not to improve upon existing computational methods, but rather to show that the performance of a single classifier can be improved with the use of cost-sensitive techniques. misclassification costs were used as weights with the purpose of artificially changing the class distribution of the training dataset. the false negative cost can be interpreted as the weight given to the peptides in the positive class, and similarly false positive cost is the weight given to the negative class. the overall scale of the training cost function is arbitrary, so we have fixed λ = and varied λ between 1/ and in order to investigate the relationship between costs and class distribution. previous works have suggested that among the best class distributions for learning is the balanced distribution, one in which all classes are equally represented. we assume that given an unbalanced training set, a balancing misclassification cost can be used to achieve an artificially nearly-balanced class distribution. the balancing cost, λ2b, defined in eq. can be interpreted to be the λ that weights the positive peptides to be the same number as the negatives and therefore compensates for the imbalance ratio of the two classes. consider the simplest scenario, where λ = κ = κ = and π =, then the balancing cost reduces to λ2b=p we are particularly interested in how classifiers trained with this simplified balancing cost perform compared to the best classifiers for a given allele, as well as compared with classifiers trained with unit costs. resampling undersampling the undersampling method consists of randomly eliminating peptides of the majority class from the training set until both classes have the same number of examples. the training sets were constructed in a similar manner to the cost-modifying experiment. first, we set aside 25% of binders and nonbinders into the testing set. the remaining binders were put into the training set together with the same number of nonbinders, which were randomly sampled without replacement from the nonbinders training superset. one of the issues concerning undersampling is the loss of information that results from the process, which can be aggravated when particularly important elements are removed from the training set. to get around this problem, we used 10-fold crossvalidation and the results presented here are the average of the experiments. oversampling the oversampling method consists of randomly replicating peptides of the minority class into the training set until both classes have the same number of examples. the training sets were constructed as follows. first, we set aside 25% of binders and nonbinders into the testing set. all remaining peptides were put into the training set together with d peptides from the minority class which were sampled with replacement, where d is the difference between the number of peptides in the the training set belonging to the majority and minority classes. hence, each peptide of the minority class is represented at least once and possibly multiple times in the training set. similarly to the undersampling procedure, we used 10-fold crossvalidation and the results presented here are the average of the experiments. decision trees the present study applies tree-based models to the peptide-mhci binding prediction problem. we have chosen to use decision trees for the simplicity in their interpretation and also because they have not been thoroughly explored in the context of peptide-mhci binding. moreover, decision and classification trees have become the canonical method for comparison of techniques used to deal with unbalanced datasets in the machine learning community. finally, there seems to be a natural correspondence between the importance of the different residue positions in a peptide and the hierarchical way in which decision trees are constructed. tree generation breiman et al. provides an excellent and detailed description of classification and regression trees. briefly, given a dataset in which each object, φ, is represented by a, x) pair, where x is a vector containing attributes of the object and τ is an indicator function of the class of the object, a tree-based classifier recursively partitions the data's attribute space into sub-regions, called nodes, in which the response variable is increasingly more homogeneous. these trees are created in two steps: induction of a large tree; and pruning of the large tree into gradually smaller subtrees. finally, one subtree must be chosen from the sequence of subtrees generated by the pruning process. in the present study, we chose the tree that minimizes the training cost function when applied to the test set. the construction of a tree requires a set of splits, which are binary questions with mutually exclusive and exhaustive outcomes used to partition the data, where the questions are coined in terms of the attributes of the objects in the dataset; and a split function used to quantify the goodness of a split, by measuring the change in the homogeneity of the response variable in the tree due to splitting a node into two subsets based on the given split. splits and split function in the problem at hand, the training dataset consists of peptides ϕ, where τ is the class of the peptide and x is the linear sequence of amino acids of the peptide, with xj being the jth amino acid from the amino terminal end of the peptide. the binary questions about the sequence of peptides can be phrased in several distinct ways, and each one of them generates a different class of splits, called motifs, that can be used in the construction of trees. we used motifs based on the anchor positions, which are represented by a single amino acid with a fixed position in the peptide, such that every amino acid is represented in every position of the peptide. the amino acids, in turn, can be represented in one of two ways: 1) by the traditional amino acid single-letter code. for example, alanine is represented by "a", arginine by "r" and so forth; and 2) by their physico-chemical properties, namely molecular weight, hydropathicity, volume, isoelectric point, polarity, ability to form hydrogen bonds and chain type as previously shown. the split function used was the training cost described in eq.  cost adjustments the first goal of this set of experiments was to investigate the relationship between class distribution and classifier performance. our results suggests that for a fixed training set size, decision trees perform best when trained with datasets of nearly balanced class distribution. figure shows the performance of classifiers trained with datasets of the same size but different class distributions and training costs for alleles a and b. note that as the proportion of positives in the training set increases, the false negative rate decreases and the false positive rate increases as can be seen by the subtle shift in the curves from left to right. our second goal was to determine whether or not prediction accuracy of a given classifier can be improved by the use of cost-sensitive techniques and, if so, to establish the relationship between classifier performance and training costs. our results demonstrate that misclassification costs can be used to improve prediction accuracy. in fact, for each one of the alleles we tested there was a cost λ that performed significantly better than the unit cost, as can be seen by the increase in auc shown in table although our goal is not to improve upon the performance of existing methods, we also show in table the auc for other methods as described in for purposes of comparison. the second and third columns correspond to the decision trees described in the present work. note the improvement in the performance of the trees with the use of training costs. *values extracted from table of peters et al., note in figure that for the training sets with majority of nonbinders, λ2b consistently reduced the total error rate as compared to the unit cost. the impact of λ2b on the performance of classifiers trained with binders-enriched datasets was not consistent, being better than unit cost for some classifiers and worse for others. in addition to representing an improvement over the unit cost, in a few cases λ2b coincided with the minimizing cost, that is, the most accurate classifier for a given allele and training set was the one trained with λ2b. however, in most cases, the balancing cost over-compensated for the imbalance in the class distribution, such that it was larger than the minimizing cost we then compared the performance of trees trained with the complete dataset using either the unit cost or λ2b. the use of λ2b resulted in auc at least as large as those for unit cost, such that λ2b improved the roc curves as compared to the unit cost in the majority of the cases. one interesting feature of the use of λ2b is that it consistently shifts the roc curve toward increasing sensitivity at the price of decreasing specificity, which is a desirable tradeoff when binders are rare. thus, even in the cases when the increase in auc is not substantial, the use of λ2b can still represent an improvement over unit cost due to the shift it causes to the roc curve. resampling the results obtained using the balanced undersampled and oversampled training sets did not represent an improvement over those using the complete unbalanced training sets. for alleles a a and b the roc curves for the trees trained with the entire dataset and those trained with the re-sampled dataset were indistinguishable from one another, whereas for alleles a and b the use of undersampling severely damaged the accuracy of the trees. real-world costs versus training costs we built decision trees with the training data described in table using different values of false negative cost, and evaluated them on a test set using the "real-world" cost κ we call λˆ the training cost that minimizes the total cost of a classifier on the test set for a given κ figure shows the relationship between λˆ and κ note that although the results are relatively noisy, in general the same trend shown in theory can be observed from this empirical data. the λˆ increases with κ and as the proportion of positives in the training set increases, the line shifts to the right, indicating that for a particular value of κ the suggested λˆ decreases. discussion prediction of peptide-mhci binding has great potential to accelerate and reduce the cost of subunit vaccine development. one of the issues concerning the prediction of mhc-peptide binding is that binders are much less abundant than nonbinders, and thus much harder to find experimentally. this circumstance typically leads to highly unbalanced training sets, which can hinder the performance of algorithms trained with them. in fact, such training sets lead to a significant increase of type errors and thus make it more difficult still to find binders. our results show that highly unbalanced training sets do indeed reduce the accuracy of predictions made with decision trees and that these predictions improve as the training sets become more balanced. we have examined three approaches that aim at improving classifier accuracy by compensating for the imbalance in the class distribution of the training sets: undersampling, oversampling and a cost-sensitive method. overall, resampling did not improve the performance of the decision trees. in fact, in several cases classifiers trained with undersampled training sets performed much worse than those trained with the full dataset. this could have been caused by the loss of information relevant to the training process. for this reason, undersampling methods may only be appropriately used with datasets in which the majority class contains a lot of redundancy, in which circumstance undersampling has been shown to outperform other random resampling methods in four distinct datasets. another potential drawback of undersampling, and in broader terms of random resampling methods, is that they may yield noisy results due to the variability introduced in the process by the randomness of the sampling procedure. in contrast to undersampling, using misclassification costs as a means to artificially counterbalance data bias led to significant improvements in the performance of the decision trees in the majority of the cases. although cost-sensitive procedures do not add any extra information to the training set, they seem to be more advantageous than random resampling techniques because they do not cause loss of information as does undersampling and do not have the extra variability introduced by the random sampling process. several other studies have shown cost-modifying methods to be advantageous. for example, japkowicz and stephen performed a systematic comparison of these methods in both artificially-generated and real-world domains, showing that cost-modifying methods yield better results than resampling techniques. fundamentally, the cost-sensitive method described here can be straightforwardly applied to any classifier that is trained using datasets that include both classes of peptides, binders and nonbinders. for instance, the individual weights of a weight matrix can be derived by minimizing the cost function over these weights. the indicator function c- can be defined by the score function's being above or below a given threshold, where the scoring function is typically the sum of the scores of each amino acid in each position of a peptide. similarly, this cost function can be incorporated into a neural network by differentially weighting the output depending on the class of the training example and allowing it to be used in the learning process by the backpropagation procedure. likewise, for support vector machines, the cost function can be implemented through the definition of the "soft margin", allowing the svm to misclassify more examples of one class than examples of the other class. in addition to showing that peptide-mhci binding predictions can be improved by the use of cost-sensitive decision trees, we have investigated the use of the balancing cost, λ2b, as a rule-of-thumb to train classifiers. we have shown that although λ2b is not always the λ that minimizes the total cost of the classifier, it consistently outperforms the unit cost when the training set is enriched for nonbinders. moreover, we have showed that the use of λ2b shifts the roc curves towards areas of higher sensitivity in relation to roc curves generated with unit cost, which can be highly desirable in situations such as epitope discovery projects. thus, although the relationship between training costs and class imbalance is relatively noisy, and further studies should be conducted before a complete guideline of what training costs should be used for a particular peptide-mhci binding dataset, our results allow us to suggest that a balancing cost should be used for datasets enriched for nonbinders, and the unit cost should be used for binders-enriched training sets.  the vaccine development process is costly and time-consuming, requiring decisions to be made at each step and it lends itself nicely to a decision-theoretic approach, which we have described here. in particular, at the epitope discovery stage, there are real costs associated with the risk of missing a positive and with the experimental verification of nonbinders. here we have described a decision-theoretic framework for the prediction of peptide-mhci binding and have provided a guideline on how to incorporate real-world costs together with misclassification costs at the training level in order to maximize prediction accuracy and push it in the desired direction. authors' contributions aps performed the computational experiments, analyzed the data and wrote the manuscript. tbk supervised the study and wrote the manuscript. gdt supervised the pilot experimental studies and helped revise the manuscript. supplementary material additional file 1 classifier performance vs class distribution for alleles a a and b comparison of the performance of classifiers built with training sets of same size but different proportions of positives for alleles a a and b. each point in a curve represents a classifier constructed with a different false negative training cost. the classifier constructed with the unit cost in each curve is marked with a solid circle and that constructed with the balancing cost is marked with a star. the curve for the perfect classifier would lie on the dotted line. the y-axis shows the total error rate of a classifier, which is the same as the classifier cost when the type and type misclassification costs are identical. fnr: false negative rate. fpr: false positive rate. click here for file additional file 2 comparison of unit cost, balancing cost, undersampling and oversampling for alleles a a and b roc curves for alleles a and b comparing the results of trees constructed with the oversampled training set, the undersampled training set, and the full training set without training costs, that is, λ = λ = and with the balancing training cost, that is, λ = and λ = /p. compare to figure the roc curves were constructed by varying the threshold used to label a node from to and evaluating its sensitivity and specificity at each threshold. click here for file acknowledgements we thank cliburn chan for insightful discussions, yongting cai for sharing experimental data used in our pilot studies and kent weinhold for his leadership and guidance. this work was supported by the large scale antibody & t cell epitope discovery program, under the nih grant n01-a1- 
establishment of peptide binding to major histocompatibility complex class i is a crucial step in the development of subunit vaccines and prediction of such binding could greatly reduce costs and accelerate the experimental process of identifying immunogenic peptides. in contrast, cost-sensitive methods significantly improve accuracy of decision trees. our method consistently improves the performance of decision trees in predicting peptide-mhc class i binding by using cost-balancing techniques to compensate for the imbalance in the training dataset. because of the experimental methods used to measure binding or affinity between peptides and mhci molecules, however, available datasets are enriched for nonbinders, and thus highly unbalanced. our results confirm that highly unbalanced training sets can reduce the accuracy of classifier predictions and show that, in the peptide-mhci binding context, resampling methods do not improve the classifier performance. we have developed a decision-theoretic framework to construct cost-sensitive trees to predict peptide-mhci binding and have used them to 1) assess the impact of the training data's class distribution on classifier accuracy, and 2) compare resampling and cost-sensitive methods as approaches to compensate for training data imbalance. finally, we propose the use of a training scheme that, when the training set is enriched for nonbinders, consistently improves the overall classifier accuracy compared to cost-insensitive classifiers and, in particular, increases the sensitivity of the classifiers. although there is no consensus on the ideal class distribution for training sets, extremely unbalanced datasets can be detrimental to the performance of prediction algorithms. many methods have been applied to the prediction of peptide-mhci binding, with some achieving outstanding performance.
 establishment of peptide binding to major histocompatibility complex class i is a crucial step in the development of subunit vaccines and prediction of such binding could greatly reduce costs and accelerate the experimental process of identifying immunogenic peptides. many methods have been applied to the prediction of peptide-mhci binding, with some achieving outstanding performance. because of the experimental methods used to measure binding or affinity between peptides and mhci molecules, however, available datasets are enriched for nonbinders, and thus highly unbalanced. although there is no consensus on the ideal class distribution for training sets, extremely unbalanced datasets can be detrimental to the performance of prediction algorithms.  we have developed a decision-theoretic framework to construct cost-sensitive trees to predict peptide-mhci binding and have used them to 1) assess the impact of the training data's class distribution on classifier accuracy, and 2) compare resampling and cost-sensitive methods as approaches to compensate for training data imbalance. our results confirm that highly unbalanced training sets can reduce the accuracy of classifier predictions and show that, in the peptide-mhci binding context, resampling methods do not improve the classifier performance. in contrast, cost-sensitive methods significantly improve accuracy of decision trees. finally, we propose the use of a training scheme that, when the training set is enriched for nonbinders, consistently improves the overall classifier accuracy compared to cost-insensitive classifiers and, in particular, increases the sensitivity of the classifiers. this method minimizes the expected classification cost for large datasets.  our method consistently improves the performance of decision trees in predicting peptide-mhc class i binding by using cost-balancing techniques to compensate for the imbalance in the training dataset. 