BACKGROUND
in the literature several feature extraction approaches  <cit>  have been proposed for the representation of peptides ; some of them have been used for building ensembles of classifiers based on the perturbation of features .
nanni and lumini in  <cit>  proposed to build an ensemble of classifiers where each classifier is trained using a different physicochemical property of the amino acids, the selection of the best physicochemical properties to be combined is performed by sequential forward floating selection  <cit> ; the same feature extraction is also used in  <cit>  to train a machine learning approach for protein subcellular localization.
a system for the recognition of t-cell epitopes is presented in  <cit>  based on the combination of two support vector machines .
the first svm is trained using the information on amino acid positions, while the second svm is trained using information extracted from the sparse indicator vector and the blosum <dig> matrix.
in particular, in  <cit>  it is proposed an ensemble of svm classifiers where each classifier is trained using a different n-peptide composition with reduced amino acid alphabets for larger values of n. the authors report that the ensemble of svms outperforms a stand-alone svm trained using the well-known 2-peptide composition with the standard amino acid alphabet.
in  <cit>  the reduced alphabets are obtained in the following way: the 20-letter amino acid alphabet is reduced to smaller alphabets based on correlations indicated by the blosum <dig> similarity matrix, i.e.
amino acid pairs with high similarity scores are grouped together.
the most correlated amino acids naturally form groups which have similar physiochemical properties  and , are conserved in many reduced alphabets, as they are the polar ,  and  groups  <cit> ).
in figure  <dig> the schemes, from  <cit> , for reducing amino acid alphabet based on the blosum <dig> matrix derived by grouping and averaging the similarity matrix elements are reported.
the complete group of reduced alphabets studied in  <cit>  in addition to those delineated in figure  <dig> are the following:
<dig> letters, ;
<dig> letters, ;
<dig> letters, ;
<dig> letters, ;
and  <dig> letters, .
in this work an alternative way for building reduced alphabets is studied based on the use of genetic algorithm  for grouping the amino-acids.
the objective function of the genetic algorithm is the maximization of the area under the receiver operating characteristic curve  <cit>  for a given classification problem.
in this way, several alphabets are created for a given value of their size.
a different svm  <cit>  is trained on each feature set , finally this pool of classifiers is combined by the mean rule.
the approach proposed in this paper has been tested in three case studies: hiv-protease ; recognition of t-cell epitopes; prediction of peptides that bind human leukocyte antigens.
aids is a grave, often mortal, disease of the immune system transmitted through hiv, therefore it is important to understand how hiv works.
some of the more successful drugs are hiv- <dig> protease inhibitors; in order to discover efficient hiv- <dig> protease inhibitors several automatic approaches have been developed aimed at obtaining a good understanding of the protease specificity .
the standard paradigm for protease-peptide interactions is the "lock" and "key" model, where a sequence of amino acids fit as a "key" to the active site in the protease.
the active site pockets of the protease are denoted by s which correspond to residues p in the peptide p = p4p3p2p1p1'p2'p3'p4', where pi is an amino-acid belonging to Σ .
if the amino acids in p  fit the positions in s , then the protease cleaves the octamer between positions p <dig> and p1'.
several works that try to solve the hiv- <dig> protease specificity problem by applying techniques from machine learning have been published  <cit> .
some methods based on a standard feed-forward multilayer perceptron are presented in  <cit> .
in  <cit>  it is shown that hiv- <dig> protease cleavage is a linear problem and that the best classifier for this problem is the linear svm.
the interested reader can see  <cit>  for a good review.
antigenic peptides degraded from foreign or host proteins can bind to major histocompatibility complex  molecules.
the major role mhc plays is to present the binding antigenic peptides to t-cell receptors .
only when the tcrs recognize the antigen, the t-cell clone will be activated, and the cellular immune will happen.
however, not all the mhc-peptide complexes can be recognized by tcrs.
those portions of short binding peptides, which can be recognized, are called t-cell epitopes  <cit> .
deciphering the patterns of peptides that elicit a mhc restricted t-cell response  <cit>  is critical for vaccine development.
broadly, the methods developed to study the interaction between peptide and mhc are based on: structural information  <cit> ; mathematical approaches including binding motifs  <cit> ; quantitative matrices  <cit> ; artificial neural networks  <cit> ; support vector machines  <cit> .
the prediction of peptides that bind multiple human leukocyte antigen  molecules is crucial in the designing of vaccines that are useful to a broader population  <cit> .
several works have been developed for identification of hla binding peptides, they include support vector machines  <cit> , artificial neural networks  <cit> , hidden markov models  <cit> .
these methods use the interaction  between peptides and hla molecule to extract the features used to train the classifiers.
all the tests reported in this work have been conducted on  <dig> datasets:  <dig> hiv datasets , a peptide dataset for the recognition of t-cell epitopes  and two vaccine datasets ; please, see the dataset sub-section of the methods for a detailed description.
the ga optimization to find the best reduced alphabets is performed on two classification problems: hiv-protease  and recognition of t-cell epitopes.
finally, these reduced alphabets are used in a second hiv dataset and in a third problem ; the experimental results demonstrate that, even if the reduced alphabets are not obtained on the same dataset, the performance in the hiv-protease and in the prediction of peptides that bind human leukocyte antigens improves with respect to that obtained by the state-of-the-art reduced alphabets-based feature extraction method.
experimental results show that the novel multi-classifier approach outperforms the standard 2-peptide composition and the method proposed in  <cit>  for all the three considered problems, demonstrating that the proposed method for producing reduced alphabets for peptide classification can be successfully applied to several bioinformatics problems.
RESULTS
among the independent dataset tests, sub-sampling test , and jackknife test, which are often used for examining the accuracy of a statistical prediction method, the jackknife test is deemed the most rigorous and objective as analyzed by a comprehensive review  <cit>  and has been increasingly adopted by leading investigators to test the power of various prediction methods  <cit> .
anyway, in this work, due to computational issue, the testing results have been obtained using a 10-fold cross validation.
the fitness function of the genetic algorithm is the maximization of the area under the roc-curve  using a leave one out on the training set for each dataset.
the roc-curve is a two-dimensional measure of classification performance that plots the probability of classifying correctly the positive examples against the rate of incorrectly classifying negative examples.
auc is also used for comparing classification performance; according to  <cit> , auc is preferred to accuracy , since it is statistically consistent and more discriminating than the accuracy measure.
in fact, researchers are often interested in ranking of data samples rather than mere positive/negative classification results.
moreover, if class distribution is skewed or unbalanced, a classifier can still receive a high accuracy by simply classifying all data samples in the dominant class  <cit> .
in the hiv datasets and in the peptide dataset linear svm is used as stand-alone classifier, in the vaccine datasets radial basis function svm is used.
notice that in both cases the parameters for svm have not been optimized and they have been set to their default values .
no parameter optimization has been performed in each dataset, since the aim of this work was to propose a generic method that could work well in several problems.
tables  <dig> and  <dig> report the results of the proposed approach compared with a baseline approach obtained considering the reduced alphabets yet proposed in the literature  <cit> .
several alphabets have been tested with different size s and n-peptide composition : for the baseline approach they refer to the reduced alphabets studied in  <cit>  , for the novel approach to the optimized alphabets.
notice that when the size s of the alphabet is  <dig> no reduction is carried out and all the approaches have the same performance  of baseline.
in the following, the novel approach will be denoted by gaset where k is the number of computation runs of the ga optimization  and set is the training set considered for the ga optimization.
possible values of set are h = hiv <dig>  p = pep, hp = hiv1+pep which means that alphabets are built considering both the datasets .
the last two columns of tables  <dig> and  <dig> denote the performance of the ensembles obtained by the fusion among the whole set ; ; ; ; ; ) of  <dig> alphabets  and among the last  <dig> alphabets ; ; ; ; )  by the sum rule.
in the last rows of tables  <dig> and  <dig> other tests varying the parameters of the genetic algorithm  are reported: ga* denotes a variation of ga where the number of chromosomes used by ga is d =  <dig>  and the number of generation steps is e =  <dig> .
from the analysis of the experimental results reported in tables  <dig> and  <dig> for the datasets hiv <dig> and pep, the following observations may be made:
- the method proposed in  <cit>  outperforms the well known 2-peptide composition  in the pep dataset but not in the hiv <dig> dataset;
- the new method outperforms both 2-peptide composition and  <cit>  when k ≥  <dig>
- the performance of gahp is lower than gah, anyway it outperforms the standard 2-peptide composition and the method proposed in  <cit>  in both the datasets.
- gah and gap work better than ga*h and ga*p in the hiv <dig> and pep datasets, respectively; this behavior is probably due to the fact that ga* is more overfitted on the validation set used to create the alphabets.
the groups of reduced alphabets generated by different runs of the genetic algorithm are not always the same, due to the stochasticity of the generation approach; anyway this cannot be considered a drawback since it permits to create an ensemble based on the perturbation of features.
in the following a sample of reduced alphabets obtained by gahp is reported:
n =  <dig>  s =  <dig>  ;
n =  <dig>  s =  <dig>  ;
n =  <dig>  s =  <dig>  ;
n =  <dig>  s =  <dig>  .
the variation among the alphabets obtained in different runs of the genetic algorithm have been studied using the average jaccard coefficient.
the jaccard coefficient  <cit>  is a measure of the degree of similarity between two clusterings  that is maximized if all the couples of patterns which belong to the same group in a, belong to the same group also in b:
jac = ss/
where ss is the number of couples of amino acids that in both alphabets are grouped together and sd is the number of couples of amino acids that belong to the same group in one alphabet but not in the other.
table  <dig> reports the average jaccard coefficient evaluated on  <dig> alphabets obtained by gahp, these results show that the alphabets are quite stable.
in figures  <dig>   <dig> the graphs showing the auc gained by the gahp approach and the baseline approach on all the  <dig> tested datasets are reported.
gahp outperforms the approaches obtained with the other n-peptide composition based feature extractions also in the datasets not used for the optimization of the reduced alphabets; these tests are a further demonstration of the importance of building an ensemble of classifiers perturbing the feature set.
the error bars in figure  <dig>   <dig>  representing the standard deviation of the mean, show that gahp is slightly more stable than baseline.
in table  <dig> the error rates related to the approaches compared above are reported.
even if auc is a more robust measure for comparing classifiers, it could be interesting to compare methods also in term of accuracy/error rate.
the results of the new approach in terms of error rate are not as good as in terms of auc, anyway it should be noted that the new ensemble has not been optimized to minimize the error rate.
finally, in order to confirm the benefit of the novel alphabet generation with respect to the baseline approach, the det curve has been plotted.
the det curve  <cit>  is a two-dimensional measure of classification performance that plots the probability of false acceptation against the rate of false rejection.
in figure  <dig> the det curve obtained by fus <dig> is plotted varying the alphabets hp) for vac <dig> dataset.
in figure  <dig> the det curve obtained by fus <dig> for vac <dig> dataset is plotted.
CONCLUSIONS
in this paper, it is proposed a new algorithm which uses a series of support vector machines in conjunction with a set of reduce alphabets of the amino-acids to obtain a novel multi-classifier based on the perturbation of features, where each classifier is trained using a different reduced alphabet.
the reduced alphabets are generated using a novel approach based on genetic algorithm whose objective function is the maximization of the auc obtained in several classification problems.
the alphabets creation problem can be viewed as a clusterization problem: the genetic algorithm is suited for this purpose since it does not need a vectorial representation of the amino-acid and permits an ad-hoc search based on an appropriate fitness function; therefore the resulting alphabets are optimized for the considered classification problem.
of course, several other meta-heuristic approaches  could be tested for the same aim.
the validity of the novel strategy for the generation of reduced alphabets is demonstrated by the performance improvement obtained by the proposed approach with respect to another reduced alphabets-based method in the tested problems.
the importance of the encoding based on reduced alphabets goes over the performance of the proposed approach, and can be related to the possibility of creating an ensemble based on methods that use different feature extractions.
in the literature  <cit> , it has been clearly shown that the fusion of classifiers based on different feature encodings permits to obtain a large error reduction with respect to the performance of a stand-alone method.

 in the literature several feature extraction approaches have been proposed for the representation of peptides; some of them have been used for building ensembles of classifiers based on the perturbation of features. nanni and lumini in proposed to build an ensemble of classifiers where each classifier is trained using a different physicochemical property of the amino acids, the selection of the best physicochemical properties to be combined is performed by sequential forward floating selection; the same feature extraction is also used in to train a machine learning approach for protein subcellular localization. a system for the recognition of t-cell epitopes is presented in based on the combination of two support vector machines. the first svm is trained using the information on amino acid positions, while the second svm is trained using information extracted from the sparse indicator vector and the blosum matrix. in particular, in it is proposed an ensemble of svm classifiers where each classifier is trained using a different n-peptide composition with reduced amino acid alphabets for larger values of n. the authors report that the ensemble of svms outperforms a stand-alone svm trained using the well-known 2-peptide composition with the standard amino acid alphabet. in the reduced alphabets are obtained in the following way: the 20-letter amino acid alphabet is reduced to smaller alphabets based on correlations indicated by the blosum similarity matrix, i.e. amino acid pairs with high similarity scores are grouped together. the most correlated amino acids naturally form groups which have similar physiochemical properties and, are conserved in many reduced alphabets, as they are the polar, and groups ). in figure the schemes, from, for reducing amino acid alphabet based on the blosum matrix derived by grouping and averaging the similarity matrix elements are reported. the complete group of reduced alphabets studied in in addition to those delineated in figure are the following: letters,; letters,; letters,; letters,; and letters,. in this work an alternative way for building reduced alphabets is studied based on the use of genetic algorithm for grouping the amino-acids. the objective function of the genetic algorithm is the maximization of the area under the receiver operating characteristic curve for a given classification problem. in this way, several alphabets are created for a given value of their size. a different svm is trained on each feature set, finally this pool of classifiers is combined by the mean rule. the approach proposed in this paper has been tested in three case studies: hiv-protease; recognition of t-cell epitopes; prediction of peptides that bind human leukocyte antigens. aids is a grave, often mortal, disease of the immune system transmitted through hiv, therefore it is important to understand how hiv works. some of the more successful drugs are hiv- protease inhibitors; in order to discover efficient hiv- protease inhibitors several automatic approaches have been developed aimed at obtaining a good understanding of the protease specificity. the standard paradigm for protease-peptide interactions is the "lock" and "key" model, where a sequence of amino acids fit as a "key" to the active site in the protease. the active site pockets of the protease are denoted by s which correspond to residues p in the peptide p = p4p3p2p1p1'p2'p3'p4', where pi is an amino-acid belonging to Σ. if the amino acids in p fit the positions in s, then the protease cleaves the octamer between positions p and p1'. several works that try to solve the hiv- protease specificity problem by applying techniques from machine learning have been published. some methods based on a standard feed-forward multilayer perceptron are presented in. in it is shown that hiv- protease cleavage is a linear problem and that the best classifier for this problem is the linear svm. the interested reader can see for a good review. antigenic peptides degraded from foreign or host proteins can bind to major histocompatibility complex molecules. the major role mhc plays is to present the binding antigenic peptides to t-cell receptors. only when the tcrs recognize the antigen, the t-cell clone will be activated, and the cellular immune will happen. however, not all the mhc-peptide complexes can be recognized by tcrs. those portions of short binding peptides, which can be recognized, are called t-cell epitopes. deciphering the patterns of peptides that elicit a mhc restricted t-cell response is critical for vaccine development. broadly, the methods developed to study the interaction between peptide and mhc are based on: structural information; mathematical approaches including binding motifs; quantitative matrices; artificial neural networks; support vector machines. the prediction of peptides that bind multiple human leukocyte antigen molecules is crucial in the designing of vaccines that are useful to a broader population. several works have been developed for identification of hla binding peptides, they include support vector machines, artificial neural networks, hidden markov models. these methods use the interaction between peptides and hla molecule to extract the features used to train the classifiers. all the tests reported in this work have been conducted on datasets: hiv datasets, a peptide dataset for the recognition of t-cell epitopes and two vaccine datasets; please, see the dataset sub-section of the methods for a detailed description. the ga optimization to find the best reduced alphabets is performed on two classification problems: hiv-protease and recognition of t-cell epitopes. finally, these reduced alphabets are used in a second hiv dataset and in a third problem; the experimental results demonstrate that, even if the reduced alphabets are not obtained on the same dataset, the performance in the hiv-protease and in the prediction of peptides that bind human leukocyte antigens improves with respect to that obtained by the state-of-the-art reduced alphabets-based feature extraction method. experimental results show that the novel multi-classifier approach outperforms the standard 2-peptide composition and the method proposed in for all the three considered problems, demonstrating that the proposed method for producing reduced alphabets for peptide classification can be successfully applied to several bioinformatics problems.  among the independent dataset tests, sub-sampling test, and jackknife test, which are often used for examining the accuracy of a statistical prediction method, the jackknife test is deemed the most rigorous and objective as analyzed by a comprehensive review and has been increasingly adopted by leading investigators to test the power of various prediction methods. anyway, in this work, due to computational issue, the testing results have been obtained using a 10-fold cross validation. the fitness function of the genetic algorithm is the maximization of the area under the roc-curve using a leave one out on the training set for each dataset. the roc-curve is a two-dimensional measure of classification performance that plots the probability of classifying correctly the positive examples against the rate of incorrectly classifying negative examples. auc is also used for comparing classification performance; according to, auc is preferred to accuracy, since it is statistically consistent and more discriminating than the accuracy measure. in fact, researchers are often interested in ranking of data samples rather than mere positive/negative classification results. moreover, if class distribution is skewed or unbalanced, a classifier can still receive a high accuracy by simply classifying all data samples in the dominant class. in the hiv datasets and in the peptide dataset linear svm is used as stand-alone classifier, in the vaccine datasets radial basis function svm is used. notice that in both cases the parameters for svm have not been optimized and they have been set to their default values. no parameter optimization has been performed in each dataset, since the aim of this work was to propose a generic method that could work well in several problems. tables and report the results of the proposed approach compared with a baseline approach obtained considering the reduced alphabets yet proposed in the literature. several alphabets have been tested with different size s and n-peptide composition: for the baseline approach they refer to the reduced alphabets studied in, for the novel approach to the optimized alphabets. notice that when the size s of the alphabet is no reduction is carried out and all the approaches have the same performance of baseline. in the following, the novel approach will be denoted by gaset where k is the number of computation runs of the ga optimization and set is the training set considered for the ga optimization. possible values of set are h = hiv p = pep, hp = hiv1+pep which means that alphabets are built considering both the datasets. the last two columns of tables and denote the performance of the ensembles obtained by the fusion among the whole set;;;;; ) of alphabets and among the last alphabets;;;; ) by the sum rule. in the last rows of tables and other tests varying the parameters of the genetic algorithm are reported: ga* denotes a variation of ga where the number of chromosomes used by ga is d = and the number of generation steps is e =. from the analysis of the experimental results reported in tables and for the datasets hiv and pep, the following observations may be made: - the method proposed in outperforms the well known 2-peptide composition in the pep dataset but not in the hiv dataset; - the new method outperforms both 2-peptide composition and when k ≥ - the performance of gahp is lower than gah, anyway it outperforms the standard 2-peptide composition and the method proposed in in both the datasets. - gah and gap work better than ga*h and ga*p in the hiv and pep datasets, respectively; this behavior is probably due to the fact that ga* is more overfitted on the validation set used to create the alphabets. the groups of reduced alphabets generated by different runs of the genetic algorithm are not always the same, due to the stochasticity of the generation approach; anyway this cannot be considered a drawback since it permits to create an ensemble based on the perturbation of features. in the following a sample of reduced alphabets obtained by gahp is reported: n = s =; n = s =; n = s =; n = s =. the variation among the alphabets obtained in different runs of the genetic algorithm have been studied using the average jaccard coefficient. the jaccard coefficient is a measure of the degree of similarity between two clusterings that is maximized if all the couples of patterns which belong to the same group in a, belong to the same group also in b: jac = ss/ where ss is the number of couples of amino acids that in both alphabets are grouped together and sd is the number of couples of amino acids that belong to the same group in one alphabet but not in the other. table reports the average jaccard coefficient evaluated on alphabets obtained by gahp, these results show that the alphabets are quite stable. in figures the graphs showing the auc gained by the gahp approach and the baseline approach on all the tested datasets are reported. gahp outperforms the approaches obtained with the other n-peptide composition based feature extractions also in the datasets not used for the optimization of the reduced alphabets; these tests are a further demonstration of the importance of building an ensemble of classifiers perturbing the feature set. the error bars in figure representing the standard deviation of the mean, show that gahp is slightly more stable than baseline. in table the error rates related to the approaches compared above are reported. even if auc is a more robust measure for comparing classifiers, it could be interesting to compare methods also in term of accuracy/error rate. the results of the new approach in terms of error rate are not as good as in terms of auc, anyway it should be noted that the new ensemble has not been optimized to minimize the error rate. finally, in order to confirm the benefit of the novel alphabet generation with respect to the baseline approach, the det curve has been plotted. the det curve is a two-dimensional measure of classification performance that plots the probability of false acceptation against the rate of false rejection. in figure the det curve obtained by fus is plotted varying the alphabets hp) for vac dataset. in figure the det curve obtained by fus for vac dataset is plotted.  in this paper, it is proposed a new algorithm which uses a series of support vector machines in conjunction with a set of reduce alphabets of the amino-acids to obtain a novel multi-classifier based on the perturbation of features, where each classifier is trained using a different reduced alphabet. the reduced alphabets are generated using a novel approach based on genetic algorithm whose objective function is the maximization of the auc obtained in several classification problems. the alphabets creation problem can be viewed as a clusterization problem: the genetic algorithm is suited for this purpose since it does not need a vectorial representation of the amino-acid and permits an ad-hoc search based on an appropriate fitness function; therefore the resulting alphabets are optimized for the considered classification problem. of course, several other meta-heuristic approaches could be tested for the same aim. the validity of the novel strategy for the generation of reduced alphabets is demonstrated by the performance improvement obtained by the proposed approach with respect to another reduced alphabets-based method in the tested problems. the importance of the encoding based on reduced alphabets goes over the performance of the proposed approach, and can be related to the possibility of creating an ensemble based on methods that use different feature extractions. in the literature, it has been clearly shown that the fusion of classifiers based on different feature encodings permits to obtain a large error reduction with respect to the performance of a stand-alone method. 
the new approach has been tested in three peptide classification problems: hiv-protease, recognition of t-cell epitopes and prediction of peptides that bind human leukocyte antigens. in this paper, it is proposed an optimization approach for producing reduced alphabets for peptide classification, using a genetic algorithm. each alphabet is constructed by a genetic algorithm whose objective function is the maximization of the area under the roc-curve obtained in several classification problems. the tests demonstrate that the idea of training a pool classifiers by reduced alphabets, created using a genetic algorithm, allows an improvement over other state-of-the-art feature extraction methods. the validity of the novel strategy for creating reduced alphabets is demonstrated by the performance improvement obtained by the proposed approach with respect to other reduced alphabets-based methods in the tested problems.
 in this paper, it is proposed an optimization approach for producing reduced alphabets for peptide classification, using a genetic algorithm. the classification task is performed by a multi-classifier system where each classifier is trained using features extracted by different reduced alphabets. each alphabet is constructed by a genetic algorithm whose objective function is the maximization of the area under the roc-curve obtained in several classification problems.  the new approach has been tested in three peptide classification problems: hiv-protease, recognition of t-cell epitopes and prediction of peptides that bind human leukocyte antigens. the tests demonstrate that the idea of training a pool classifiers by reduced alphabets, created using a genetic algorithm, allows an improvement over other state-of-the-art feature extraction methods.  the validity of the novel strategy for creating reduced alphabets is demonstrated by the performance improvement obtained by the proposed approach with respect to other reduced alphabets-based methods in the tested problems. 