BACKGROUND
string kernels are a powerful and popular tool for machine learning in computational biology.
they have been successfully applied to numerous applications ranging from protein remote homology detection  <cit> , to gene identification  <cit> , to sub-cellular location prediction  <cit>  to drug design  <cit> .
the different kernel formulations commonly exploit the sequential structure of the sequences and by doing so can effectively eliminate implausible features, leading to improved results.
when using string kernels on protein sequences, one key disadvantage is that prior knowledge about the properties of individual amino acids , e.g., their size, hydrophobicity, secondary structure preference, cannot be easily incorporated.
while these properties can be learned implicitly by the machine learning methods if the training data sets are large enough, it would be advantageous to include this information in the sequence representation.
the goal of this work is to combine the benefits of string kernels with the ones of physico-chemical descriptors for aas.
the main idea is to replace the comparison of substrings, which is computed during kernel computation, with a term that takes the aa properties into account.
while this seems quite simple at first sight, it is less so, when considering k-mers instead of single aas.
the key insight is how to compute the kernels such that the beneficial properties of sequence kernels do not get lost.
in particular, we would like that either the use of uninformative descriptors  or the choice of distinct kernel parameters reduces the new kernel to the original string kernel.
string kernels for sequence classification
kernels that have been proposed for classifying nucleic and amino acids can be divided into two main classes:  kernels describing the sequence content of sequences of varying length and  kernels for identifying localized signals within sequences of fixed length.
the first class is typically used for classifying whole protein or mrna sequences, while the second class is typically used to recognize a specific site in a window of fixed length sliding over a sequence.
kernels describing l-mer content
the so-called spectrum kernel was first proposed for classifying protein sequences  <cit> :
where x, x′ are two sequences over an alphabet Σ, e.g.
protein or dna sequences.
is a mapping of the sequence x into a |Σ|l-dimensional feature-space.
each dimension corresponds to one of the |Σ|l possible strings s of length l and is the count of the number of occurrences of s in x. it is
where x is the substring of length l of x at position i.
several algorithms based on string or sparse data structures have been proposed to efficiently compute the above kernel and additional variants .
the kernel in  can alternatively be written as
here, we consider all pairs of substrings at any position in each of the two input sequences.
this formulation has the benefit that it makes the comparison between the substrings more explicit, which is needed in the derivation of the extensions.
kernels for localized signals
the spectrum kernel is less well-suited for identifying localized signals in sequences, since the information about the position of the substring in the input sequences is ignored, i.e.
lost, during kernel computation.
several kernels have been proposed to address this issue.
most notably the weighted degree  kernel  <cit>  and the oligo kernel  <cit> .
both kernels work on sequences of fixed length l and count co-occurring substrings in both sequences at the same or similar position.
we will use the wd kernel as representative for localized signal kernels.
it is defined as
where  is the weighting of the substring lengths.
the wd kernel is quite related to the spectrum kernel formulation in , where we consider only the l-mers occurring at the same position, i.e., where i = j. the oligo kernel is similar in spirit but it also compares substrings at different positions.
incorporation of knowledge on aa properties
in this work we propose modifications to existing string kernels that supplement the kernels’ beneficial properties by incorporating prior knowledge on physico-chemical and other properties of aas.
previous work on incorporating prior knowledge has been either focused on using physico-chemical properties for single aas, i.e., ignoring the sequential nature of the sequences , or took advantage of blast or psi-blast profiles for improving spectrum kernels  <cit> .
we propose a complementary approach of employing physico-chemical or other information to refine the similarity between two substrings used in most existing string kernels.
we illustrate the usefulness of these modifications for both classes of string kernels on two problems:  the prediction of mhc-binding peptides as an example for localized signals and  protein fold classification as an example for l-mer content.
methods
idea
the string kernels described above ,) have in common that they compare substrings of length l between the two input sequences x and x′.
the involved term  can equivalently be written as:
where  and .
can be indexed by a substring s ∈ Σl and is defined as , if  and  <dig> otherwise.
for the sake of the derivation, let us consider , generating a simple encoding of the letters into |Σ|-dimensional unit vectors.
it can be easily seen that we can rewrite the substring comparison as
the main problem of using Φ <dig> as the basis of substring comparisons, is that it ignores the relations between the letters in the alphabet.
while this is a negligible problem for nucleotide sequences where each nucleotide is unique, it is important to consider relatedness between aas.
the main idea of this work is to replace Φ <dig> with a feature map Ψ that takes relations between the aas into account.
one way is to use physico-chemical descriptors of aas, such as  <cit> .
alternatively, one may use aa substitution matrices for defining amino acid similarities, as e.g.
done in  <cit> .
the feature space is then not spanned by |Σ|l different combinations of letters, but by dl, where d is the number of properties used to describe the aa.
this leads to the following kernel on aa substrings:
using the feature representation corresponding to this kernel, we can now recognize sequences of aas that have certain properties :  there is a feature induced in the kernel corresponding to all combinations of products of features involving exactly one aa property per substring position.
for instance, when considering products of the form  ·  · , then we get n <dig> different monomials which each use exactly one of the n features from the three different groups.
there are no monomials xi,jxi,k for any i =  <dig> …, <dig> and j, k =  <dig> …,n.
if one wants to additionally allow the combination of several properties from every position, then the following two formulations are suitable: the first is based on the polynomial kernel:
and the second on the rbf kernel:
both kernels induce a considerably richer feature space, which can be beneficial for accurate classification of sequences.
aa substring kernel for localized string kernels
replacing the substring comparison  with the more general formulation in , , or  together with an informed choice of features Ψ for each letter a ∈ Σ , directly implies a generalized form of the string kernels described above.
for the wd kernel we can write:
is a linear combination of kernels and therefore a valid kernel  <cit> .
independent of the choice of aa substring kernel, the modified wd kernel can be computed efficiently, with a complexity comparable to that of the original.
of particular interest is the wd-rbf kernel, i.e.
the combination of the wd kernel and the rbf aa substring kernel:
for σ →  <dig> and an encoding Ψ with Ψ = Ψ if and only if a = b, the wd-rbf kernel corresponds to the wd kernel: the rbf aa substring kernel will be one only if the substrings are identical, otherwise it will be zero.
relation to non-substring-based kernels
when considering kernels for sequences of fixed length l, one may alternatively consider a representation of the sequence as vector of the physico-chemical properties of all sequence elements/aas, i.e.
.
then one may use a standard kernel to compute similarities between the sequences, as, e.g., done in  <cit> .
when using the polynomial kernel as basis, this would lead to the following kernel:
for the rbf kernel we get analogously,
please note that here we use the full sequence and do not separately consider subsequences.
both kernels consider higher order correlations between properties of the sequence at arbitrary position in the sequence.
hence, the sequential nature of the sequences is not fully taken into account .
aa substring kernel for l-mer content string kernels
the aa substring kernels , ,  can be combined with the spectrum kernel ,  analogously to the combination with the wd kernel.
for instance in combination with the rbf substring kernel, we arrive at:
as before, for σ →  <dig>  the above formulation is identical to the original spectrum kernel.
a drawback of this approach is, however, that one now has to compute the substring comparisons for every pair of occurring substrings.
hence, the computational complexity, o, is much higher than for the original spectrum kernel and makes this kernel impractical.
in order to reduce complexity we turn to modifications of the spectrum kernel: the mismatch kernel  <cit>  and the profile kernel  <cit> .
the mismatch kernel
while the spectrum kernel only considers pairs of identical l-mers, the mismatch kernel allows for some degree of mismatching.
instead of counting occurences of l-mers s in x it counts the occurences of l-mers that differ from s by at most m mismatches.
the mismatch kernel is defined as
and
with ∅s =  <dig> if x belongs to the mismatch neighbourhood n, i.e.
differs from s in at most m positions.
otherwise, ∅s =  <dig>  thus, we can write alternatively:
combination of an aa substring kernel with the -mismatch kernel limits comparisons to those l-mer pairs with at most 2m mismatches as opposed to all l-mer pairs for the spectrum kernel.
employing the mismatch tree data structure from  <cit> , the generalized mismatch kernel can be calculated efficiently with a complexity of o).
the -mismatch tree is a tree representation of the feature space: each leaf represents a fixed l-mer feature s. in order to benefit from this feature space-based data structure, it suggests itself to apply the generalization to the feature map Φs .
plugging one of the aa substring kernels into  yields
rather than simply counting similar substrings this feature representation accounts for the degree of similarity: similar substrings contribute stronger than dissimilar ones.
this strategy is particularly beneficial, when allowing many mismatches.
once again, the combination with the rbf aa substring kernel, namely the mismatch-rbf kernel, is of particular interest.
the corresponding feature map is defined as
for σ → ∞ it corresponds to the mismatch feature map  since the rbf aa substring kernel will be one for all substring pairs.
the profile kernel
just like the spectrum and the mismatch kernel, the profile kernel  <cit>  was proposed for protein classification and remote homology detection.
the main difference between the mismatch and profile kernel is the definition of the neighbourhood.
for the profile kernel one uses the positional mutation neighbourhood of x based on blast or psi-blast profiles p for each position i of x and for each letter k ∈ Σ:
where δ defines the “radius” of the mutation neighbourhood  <cit> .
then the feature map and kernel, respectively, are defined as
and
in order to incorporate aa properties, we propose to modify  analogously to the mismatch kernel:
the second term determines whether the substring is within the mutation neighbourhood and should be counted and the first term determines the contribution of the substring based on aa similarities.
this kernel can be computed as efficient as the original profile kernel.
since the elements in the neighbourhood are weighted based on aa property similarity, the kernel may be able to take advantage of larger neighbourhoods.
the profile kernel is similar to the profile-based direct kernels described in  <cit>  and similar ideas to incorporate aa properties can be applied there as well.
the profile and mismatch kernel have, however, the advantage that they allow for an efficient computation using the data structures proposed in  <cit> .
these data structures unfortunately are not applicable to the profile kernel formulations in  <cit> .
experimental methods
data
we evaluate the performance of the proposed kernels on two problems: the kernels for localized signals on mhc-peptide binding classification, and the kernels describing l-mer content on protein classification.
for mhc-peptide binding experiments we utilized the iedb benchmark data set from peters et al.
<cit> .
it contains quantitative binding data  of nonameric peptides with respect to various mhc alleles.
peptides with ic <dig> values greater than  <dig> were considered non-binders, all others binders.
protein classification data was taken from the supplementary material of  <cit> .
this commonly used data set comprises  <dig>  protein domains from  <dig> families.
corresponding profile information was taken from .
physico-chemical descriptors
a wide range of physico-chemical descriptors of aas have been published.
many of them can be obtained from the amino acid index database   <cit> .
within this work we use three sets of descriptors:  five descriptors derived from a principal component analysis of  <dig> physico-chemical properties taken from the aaindex  <cit>  ,  three descriptors representing hydrophobicity, size, and electronic properties , and   <dig> descriptors corresponding to the respective entries of the blosum <dig> substitution matrix  <cit>  .
evaluation of string kernels for localized signals
performance analysis.
preliminary experiments on three human mhc alleles  were carried out to analyze the performance of the different kernels wd , rbf , poly , wd-rbf , wd-poly  combined with different encodings .
the alleles were chosen to comprise a small data set  as well as a medium  and a large  data set from the iedb benchmark  <cit> .
performances of the wd kernel and the wd-rbf kernel with blosum <dig> encoding were subsequently analyzed on all  <dig> human mhc alleles contained in the iedb benchmark.
we used two times nested 5-fold cross-validation, i.e.
two nested cross-validation loops, to  perform model-selection over the kernel and regularization parameters ,  estimate the prediction performance  .
performance is measured by averaging the area under the roc curve .
learning curve analysis.
the performance dependence on the amount of training data was analyzed on allele a* <dig> in  <dig> runs of two times nested 5-fold cross-validation to average over different data splits to reduce random fluctuations of the performance values.
performance is measured by averaging the area under the roc curve .
in each run, thirty percent of the available data was used for testing.
from the remaining data training sets of different sizes  were selected randomly.
evaluation of string kernels describing l-mer content
mismatch kernel.
for the comparison of the mismatch kernel and the mismatch-rbf kernel, protein classification data and experimental setup were taken from the supplementary material of  <cit> .
the roc <dig> score, i.e.
the area under the roc curve computed up to the first  <dig> false positives, is used as performance measure.
profile kernel.
for the comparison of the profile kernel and the profile-rbf kernel, protein classification data and experimental setup were taken from the supplementary material of  <cit> .
corresponding psi-blast profiles were taken from  <cit> .
the roc <dig> score is used as performance measure.
svm computations
all svm computations were performed using the matlab interface of the freely available large scale machine learning toolbox shogun  <cit> .
all used kernels are implemented as part of the toolbox.
RESULTS
the main goal of this work is the methodological improvement of existing string kernels by incorporation of prior knowledge on aa properties.
in order to analyze the benefits of the proposed modifications we conducted performance comparisons between the original and the modified string kernels.
string kernels for localized signals
the prediction of mhc-binding peptides is one of the major problems in computational immunology, highly relevant for rational vaccine design.
mhc-i molecules bind small peptides derived from intracellular proteins and present them on the cell surface for surveillance by the immune system.
given a set of peptide sequences one would like to predict whether they bind to a certain mhc-i molecule.
since the majority of binders are of length nine, the application of kernels for localized signals suggests itself.
for a preliminary analysis we chose three human mhc alleles from the iedb benchmark data set: a* <dig> , b* <dig> , and a* <dig> .
the performance of various kernels utilizing sequential structure only , aa properties only , and a combination of both  was validated on these alleles.
we used three different encodings of aa properties.
cross-validation results are given in table  <dig> best performance is achieved by a different kernel type for each of the alleles: poly  for a* <dig>  rbf  for b* <dig> and wd-rbf  for a* <dig>  the latter performs second-best on a* <dig> and b* <dig>  as for the benefits of the modification of the wd kernel, the wd-poly and wd-rbf kernels outperform the wd kernel in  <dig> out of  <dig> cases.
from table  <dig> we can observe the trend that the kernels that use aa properties benefit more for smaller datasets.
to validate this hypothesis, we performed a learning curve analysis for wd and wd-rbf  on a* <dig>  the allele with the highest number of peptides in the iedb benchmark data set.
figure  <dig> shows the mean aurocs with confidence intervals  over  <dig> cross-validation runs.
we can clearly observe that the fewer examples are available for learning, the stronger is the improvement of the wd-rbf kernel over the wd kernel.
intuitively this makes sense, as the more data is available, the easier it will be to infer the relation of the aas from the sequences in the training data alone.
aurocs and standard deviation were determined in two times nested 5-fold cross-validation.
best  and second-best  performances per mhc allele are highlighted.
an asterisk marks performance improvement due to the proposed modifications.
the preliminary analysis showed the wd-rbf kernel with blosum <dig> encoding to perform best.
for a more comprehensive comparison, performance of wd and wd-rbf  kernels were assessed on all  <dig> human mhc alleles from the iedb benchmark.
for  <dig> alleles wd-rbf outperforms wd .
this is significant with respect to the binomial distribution .
finally, we compare our results with the ones obtained using a multi-task learning  method for mhc classification described in  <cit> .
here, the authors used two kernels, one to define the similarity between examples and one to define the similarity between tasks.
they report an auroc of  <dig> % using two string kernels.
when using the wd-rbf for computing the similarity between the examples, we can slightly improve upon their performance to  <dig> % .
hence, the aa property-enhanced kernels once more have a slight, but consistent advantage over the base-line kernels.
besides the performance improvement, the modified wd kernel allows, at least theoretically, for the extraction of biological insights: employing an analysis method analogous to  <cit>  individual patterns of aa properties that are relevant for the classification can be extracted.
string kernels describing l-mer content
to show that also the modification of kernels for describing l-mer content of sequences has desirable properties, we chose the problem of protein remote homology detection.
here, the task is to classify proteins into folds, super-families or families based on their sequence.
this problem has been previously tackled in a series of papers in  <cit>  which suggested the spectrum kernel, followed by the mismatch kernel and finally the profile kernel.
the profile kernel already uses aa similarities based on blast or psi-blast profiles which lead to significant improvements.
here, we would like to illustrate that using the aa property-enhanced versions of these kernels can still lead to an improvement.
we chose the family classification task for this analysis since it was considered in all mentioned previous studies.
comparison of the three kernels proposed in  <cit> , with their aa-property enhanced counterparts for remote homology detection of  <dig> protein families.
auroc <dig> is the average auroc <dig> score and #wins the number of families for which each method outperforms its counterpart .
the kernels taking advantage of aa properties lead to a higher average accuracy in all three cases .
for l and τ we use the published parameter settings.
for σ we chose the best result among σ = { <dig> , <dig> , <dig> }.
in summary, in our experiments we can observe that the newly proposed kernels lead to consistently better performances than the string kernels on aa sequences as well as the non-substring kernels.
CONCLUSIONS
we have proposed new kernels that combine the benefits of physico-chemical descriptors for amino acids with the ones of string kernels.
string kernels are powerful and expressive, yet one needs sufficiently many examples during training to learn relationships between amino acids in the very high dimensional space induced by the string kernel.
standard kernels based on physico-chemical descriptors of amino acids, on the other hand, cannot exploit the sequential structure of the input sequences and implicitly generate many more features, numerous of which will be biologically implausible.
here, one also needs more examples to learn which subset of features is needed for accurate discrimination, especially for longer protein sequences.
we could show that the proposed modifications of the wd kernel yield significant improvements in the prediction of mhc-binding peptides.
as expected, the improvement is particularly strong when data is less abundant.
for protein remote homology detection aa property-enhanced kernels can also lead to significant performance improvements.
for the most sophisticated kernels using blast or psi-blast profiles, however, information about the similarities of aas can already be derived from the profiles and the improvement is marginal.
overall, our experiments demonstrate that the proposed kernels indeed lead to a better performance than string kernels and non-substring kernels.
these improvements are not major, but consistent.
it has to be noted that a big difference between the previously proposed kernels and the proposed kernels cannot be expected: the proposed kernels essentially work on subsets of the features of previously proposed kernels and the improvements that we observe mainly come from the svm’s degraded performance when including uninformative features .
in summary, the proposed modifications, in particular the combination with the rbf aa substring kernel, consistently yield improvements without seriously affecting the computing time .
in all formulations, the original string kernel formulation can be recovered by appropriately choosing σ. hence, when σ is included in model selection, the performance of the proposed kernels should be at least as good as the original string kernels.
we therefore believe that the proposed kernels should be preferred over the original formulations for any protein sequence classification task.
list of abbreviations used
aa: amino acid; mhc: major histocompatibility complex; svm: support vector machine; wd: weighted degree.
competing interests
the authors declare that they have no competing interests.
authors' contributions
nct and gr conceived and designed the project.
nct prepared the data, implemented the kernels, performed experiments and drafted the manuscript.
cw performed the mtl experiments and contributed to the preparation of manuscript.
ok contributed to the discussion and helped writing the manuscript.
gr supervised the project, implemented and performed experiments and contributed to the manuscript.

 string kernels are a powerful and popular tool for machine learning in computational biology. they have been successfully applied to numerous applications ranging from protein remote homology detection, to gene identification, to sub-cellular location prediction to drug design. the different kernel formulations commonly exploit the sequential structure of the sequences and by doing so can effectively eliminate implausible features, leading to improved results. when using string kernels on protein sequences, one key disadvantage is that prior knowledge about the properties of individual amino acids, e.g., their size, hydrophobicity, secondary structure preference, cannot be easily incorporated. while these properties can be learned implicitly by the machine learning methods if the training data sets are large enough, it would be advantageous to include this information in the sequence representation. the goal of this work is to combine the benefits of string kernels with the ones of physico-chemical descriptors for aas. the main idea is to replace the comparison of substrings, which is computed during kernel computation, with a term that takes the aa properties into account. while this seems quite simple at first sight, it is less so, when considering k-mers instead of single aas. the key insight is how to compute the kernels such that the beneficial properties of sequence kernels do not get lost. in particular, we would like that either the use of uninformative descriptors or the choice of distinct kernel parameters reduces the new kernel to the original string kernel. string kernels for sequence classification kernels that have been proposed for classifying nucleic and amino acids can be divided into two main classes: kernels describing the sequence content of sequences of varying length and kernels for identifying localized signals within sequences of fixed length. the first class is typically used for classifying whole protein or mrna sequences, while the second class is typically used to recognize a specific site in a window of fixed length sliding over a sequence. kernels describing l-mer content the so-called spectrum kernel was first proposed for classifying protein sequences: where x, x′ are two sequences over an alphabet Σ, e.g. protein or dna sequences. is a mapping of the sequence x into a |Σ|l-dimensional feature-space. each dimension corresponds to one of the |Σ|l possible strings s of length l and is the count of the number of occurrences of s in x. it is where x is the substring of length l of x at position i. several algorithms based on string or sparse data structures have been proposed to efficiently compute the above kernel and additional variants. the kernel in can alternatively be written as here, we consider all pairs of substrings at any position in each of the two input sequences. this formulation has the benefit that it makes the comparison between the substrings more explicit, which is needed in the derivation of the extensions. kernels for localized signals the spectrum kernel is less well-suited for identifying localized signals in sequences, since the information about the position of the substring in the input sequences is ignored, i.e. lost, during kernel computation. several kernels have been proposed to address this issue. most notably the weighted degree kernel and the oligo kernel. both kernels work on sequences of fixed length l and count co-occurring substrings in both sequences at the same or similar position. we will use the wd kernel as representative for localized signal kernels. it is defined as where is the weighting of the substring lengths. the wd kernel is quite related to the spectrum kernel formulation in, where we consider only the l-mers occurring at the same position, i.e., where i = j. the oligo kernel is similar in spirit but it also compares substrings at different positions. incorporation of knowledge on aa properties in this work we propose modifications to existing string kernels that supplement the kernels’ beneficial properties by incorporating prior knowledge on physico-chemical and other properties of aas. previous work on incorporating prior knowledge has been either focused on using physico-chemical properties for single aas, i.e., ignoring the sequential nature of the sequences, or took advantage of blast or psi-blast profiles for improving spectrum kernels. we propose a complementary approach of employing physico-chemical or other information to refine the similarity between two substrings used in most existing string kernels. we illustrate the usefulness of these modifications for both classes of string kernels on two problems: the prediction of mhc-binding peptides as an example for localized signals and protein fold classification as an example for l-mer content. methods idea the string kernels described above,) have in common that they compare substrings of length l between the two input sequences x and x′. the involved term can equivalently be written as: where and. can be indexed by a substring s ∈ Σl and is defined as, if and otherwise. for the sake of the derivation, let us consider, generating a simple encoding of the letters into |Σ|-dimensional unit vectors. it can be easily seen that we can rewrite the substring comparison as the main problem of using Φ as the basis of substring comparisons, is that it ignores the relations between the letters in the alphabet. while this is a negligible problem for nucleotide sequences where each nucleotide is unique, it is important to consider relatedness between aas. the main idea of this work is to replace Φ with a feature map Ψ that takes relations between the aas into account. one way is to use physico-chemical descriptors of aas, such as. alternatively, one may use aa substitution matrices for defining amino acid similarities, as e.g. done in. the feature space is then not spanned by |Σ|l different combinations of letters, but by dl, where d is the number of properties used to describe the aa. this leads to the following kernel on aa substrings: using the feature representation corresponding to this kernel, we can now recognize sequences of aas that have certain properties: there is a feature induced in the kernel corresponding to all combinations of products of features involving exactly one aa property per substring position. for instance, when considering products of the form · ·, then we get n different monomials which each use exactly one of the n features from the three different groups. there are no monomials xi,jxi,k for any i = …, and j, k = …,n. if one wants to additionally allow the combination of several properties from every position, then the following two formulations are suitable: the first is based on the polynomial kernel: and the second on the rbf kernel: both kernels induce a considerably richer feature space, which can be beneficial for accurate classification of sequences. aa substring kernel for localized string kernels replacing the substring comparison with the more general formulation in,, or together with an informed choice of features Ψ for each letter a ∈ Σ, directly implies a generalized form of the string kernels described above. for the wd kernel we can write: is a linear combination of kernels and therefore a valid kernel. independent of the choice of aa substring kernel, the modified wd kernel can be computed efficiently, with a complexity comparable to that of the original. of particular interest is the wd-rbf kernel, i.e. the combination of the wd kernel and the rbf aa substring kernel: for σ → and an encoding Ψ with Ψ = Ψ if and only if a = b, the wd-rbf kernel corresponds to the wd kernel: the rbf aa substring kernel will be one only if the substrings are identical, otherwise it will be zero. relation to non-substring-based kernels when considering kernels for sequences of fixed length l, one may alternatively consider a representation of the sequence as vector of the physico-chemical properties of all sequence elements/aas, i.e.. then one may use a standard kernel to compute similarities between the sequences, as, e.g., done in. when using the polynomial kernel as basis, this would lead to the following kernel: for the rbf kernel we get analogously, please note that here we use the full sequence and do not separately consider subsequences. both kernels consider higher order correlations between properties of the sequence at arbitrary position in the sequence. hence, the sequential nature of the sequences is not fully taken into account. aa substring kernel for l-mer content string kernels the aa substring kernels,, can be combined with the spectrum kernel, analogously to the combination with the wd kernel. for instance in combination with the rbf substring kernel, we arrive at: as before, for σ → the above formulation is identical to the original spectrum kernel. a drawback of this approach is, however, that one now has to compute the substring comparisons for every pair of occurring substrings. hence, the computational complexity, o, is much higher than for the original spectrum kernel and makes this kernel impractical. in order to reduce complexity we turn to modifications of the spectrum kernel: the mismatch kernel and the profile kernel. the mismatch kernel while the spectrum kernel only considers pairs of identical l-mers, the mismatch kernel allows for some degree of mismatching. instead of counting occurences of l-mers s in x it counts the occurences of l-mers that differ from s by at most m mismatches. the mismatch kernel is defined as and with ∅s = if x belongs to the mismatch neighbourhood n, i.e. differs from s in at most m positions. otherwise, ∅s = thus, we can write alternatively: combination of an aa substring kernel with the -mismatch kernel limits comparisons to those l-mer pairs with at most 2m mismatches as opposed to all l-mer pairs for the spectrum kernel. employing the mismatch tree data structure from, the generalized mismatch kernel can be calculated efficiently with a complexity of o). the -mismatch tree is a tree representation of the feature space: each leaf represents a fixed l-mer feature s. in order to benefit from this feature space-based data structure, it suggests itself to apply the generalization to the feature map Φs. plugging one of the aa substring kernels into yields rather than simply counting similar substrings this feature representation accounts for the degree of similarity: similar substrings contribute stronger than dissimilar ones. this strategy is particularly beneficial, when allowing many mismatches. once again, the combination with the rbf aa substring kernel, namely the mismatch-rbf kernel, is of particular interest. the corresponding feature map is defined as for σ → ∞ it corresponds to the mismatch feature map since the rbf aa substring kernel will be one for all substring pairs. the profile kernel just like the spectrum and the mismatch kernel, the profile kernel was proposed for protein classification and remote homology detection. the main difference between the mismatch and profile kernel is the definition of the neighbourhood. for the profile kernel one uses the positional mutation neighbourhood of x based on blast or psi-blast profiles p for each position i of x and for each letter k ∈ Σ: where δ defines the “radius” of the mutation neighbourhood. then the feature map and kernel, respectively, are defined as and in order to incorporate aa properties, we propose to modify analogously to the mismatch kernel: the second term determines whether the substring is within the mutation neighbourhood and should be counted and the first term determines the contribution of the substring based on aa similarities. this kernel can be computed as efficient as the original profile kernel. since the elements in the neighbourhood are weighted based on aa property similarity, the kernel may be able to take advantage of larger neighbourhoods. the profile kernel is similar to the profile-based direct kernels described in and similar ideas to incorporate aa properties can be applied there as well. the profile and mismatch kernel have, however, the advantage that they allow for an efficient computation using the data structures proposed in. these data structures unfortunately are not applicable to the profile kernel formulations in. experimental methods data we evaluate the performance of the proposed kernels on two problems: the kernels for localized signals on mhc-peptide binding classification, and the kernels describing l-mer content on protein classification. for mhc-peptide binding experiments we utilized the iedb benchmark data set from peters et al.. it contains quantitative binding data of nonameric peptides with respect to various mhc alleles. peptides with ic values greater than were considered non-binders, all others binders. protein classification data was taken from the supplementary material of. this commonly used data set comprises protein domains from families. corresponding profile information was taken from. physico-chemical descriptors a wide range of physico-chemical descriptors of aas have been published. many of them can be obtained from the amino acid index database. within this work we use three sets of descriptors: five descriptors derived from a principal component analysis of physico-chemical properties taken from the aaindex, three descriptors representing hydrophobicity, size, and electronic properties, and descriptors corresponding to the respective entries of the blosum substitution matrix. evaluation of string kernels for localized signals performance analysis. preliminary experiments on three human mhc alleles were carried out to analyze the performance of the different kernels wd, rbf, poly, wd-rbf, wd-poly combined with different encodings. the alleles were chosen to comprise a small data set as well as a medium and a large data set from the iedb benchmark. performances of the wd kernel and the wd-rbf kernel with blosum encoding were subsequently analyzed on all human mhc alleles contained in the iedb benchmark. we used two times nested 5-fold cross-validation, i.e. two nested cross-validation loops, to perform model-selection over the kernel and regularization parameters, estimate the prediction performance. performance is measured by averaging the area under the roc curve. learning curve analysis. the performance dependence on the amount of training data was analyzed on allele a* in runs of two times nested 5-fold cross-validation to average over different data splits to reduce random fluctuations of the performance values. performance is measured by averaging the area under the roc curve. in each run, thirty percent of the available data was used for testing. from the remaining data training sets of different sizes were selected randomly. evaluation of string kernels describing l-mer content mismatch kernel. for the comparison of the mismatch kernel and the mismatch-rbf kernel, protein classification data and experimental setup were taken from the supplementary material of. the roc score, i.e. the area under the roc curve computed up to the first false positives, is used as performance measure. profile kernel. for the comparison of the profile kernel and the profile-rbf kernel, protein classification data and experimental setup were taken from the supplementary material of. corresponding psi-blast profiles were taken from. the roc score is used as performance measure. svm computations all svm computations were performed using the matlab interface of the freely available large scale machine learning toolbox shogun. all used kernels are implemented as part of the toolbox.  the main goal of this work is the methodological improvement of existing string kernels by incorporation of prior knowledge on aa properties. in order to analyze the benefits of the proposed modifications we conducted performance comparisons between the original and the modified string kernels. string kernels for localized signals the prediction of mhc-binding peptides is one of the major problems in computational immunology, highly relevant for rational vaccine design. mhc-i molecules bind small peptides derived from intracellular proteins and present them on the cell surface for surveillance by the immune system. given a set of peptide sequences one would like to predict whether they bind to a certain mhc-i molecule. since the majority of binders are of length nine, the application of kernels for localized signals suggests itself. for a preliminary analysis we chose three human mhc alleles from the iedb benchmark data set: a*, b*, and a*. the performance of various kernels utilizing sequential structure only, aa properties only, and a combination of both was validated on these alleles. we used three different encodings of aa properties. cross-validation results are given in table best performance is achieved by a different kernel type for each of the alleles: poly for a* rbf for b* and wd-rbf for a* the latter performs second-best on a* and b* as for the benefits of the modification of the wd kernel, the wd-poly and wd-rbf kernels outperform the wd kernel in out of cases. from table we can observe the trend that the kernels that use aa properties benefit more for smaller datasets. to validate this hypothesis, we performed a learning curve analysis for wd and wd-rbf on a* the allele with the highest number of peptides in the iedb benchmark data set. figure shows the mean aurocs with confidence intervals over cross-validation runs. we can clearly observe that the fewer examples are available for learning, the stronger is the improvement of the wd-rbf kernel over the wd kernel. intuitively this makes sense, as the more data is available, the easier it will be to infer the relation of the aas from the sequences in the training data alone. aurocs and standard deviation were determined in two times nested 5-fold cross-validation. best and second-best performances per mhc allele are highlighted. an asterisk marks performance improvement due to the proposed modifications. the preliminary analysis showed the wd-rbf kernel with blosum encoding to perform best. for a more comprehensive comparison, performance of wd and wd-rbf kernels were assessed on all human mhc alleles from the iedb benchmark. for alleles wd-rbf outperforms wd. this is significant with respect to the binomial distribution. finally, we compare our results with the ones obtained using a multi-task learning method for mhc classification described in. here, the authors used two kernels, one to define the similarity between examples and one to define the similarity between tasks. they report an auroc of % using two string kernels. when using the wd-rbf for computing the similarity between the examples, we can slightly improve upon their performance to %. hence, the aa property-enhanced kernels once more have a slight, but consistent advantage over the base-line kernels. besides the performance improvement, the modified wd kernel allows, at least theoretically, for the extraction of biological insights: employing an analysis method analogous to individual patterns of aa properties that are relevant for the classification can be extracted. string kernels describing l-mer content to show that also the modification of kernels for describing l-mer content of sequences has desirable properties, we chose the problem of protein remote homology detection. here, the task is to classify proteins into folds, super-families or families based on their sequence. this problem has been previously tackled in a series of papers in which suggested the spectrum kernel, followed by the mismatch kernel and finally the profile kernel. the profile kernel already uses aa similarities based on blast or psi-blast profiles which lead to significant improvements. here, we would like to illustrate that using the aa property-enhanced versions of these kernels can still lead to an improvement. we chose the family classification task for this analysis since it was considered in all mentioned previous studies. comparison of the three kernels proposed in, with their aa-property enhanced counterparts for remote homology detection of protein families. auroc is the average auroc score and #wins the number of families for which each method outperforms its counterpart. the kernels taking advantage of aa properties lead to a higher average accuracy in all three cases. for l and τ we use the published parameter settings. for σ we chose the best result among σ = {,, }. in summary, in our experiments we can observe that the newly proposed kernels lead to consistently better performances than the string kernels on aa sequences as well as the non-substring kernels.  we have proposed new kernels that combine the benefits of physico-chemical descriptors for amino acids with the ones of string kernels. string kernels are powerful and expressive, yet one needs sufficiently many examples during training to learn relationships between amino acids in the very high dimensional space induced by the string kernel. standard kernels based on physico-chemical descriptors of amino acids, on the other hand, cannot exploit the sequential structure of the input sequences and implicitly generate many more features, numerous of which will be biologically implausible. here, one also needs more examples to learn which subset of features is needed for accurate discrimination, especially for longer protein sequences. we could show that the proposed modifications of the wd kernel yield significant improvements in the prediction of mhc-binding peptides. as expected, the improvement is particularly strong when data is less abundant. for protein remote homology detection aa property-enhanced kernels can also lead to significant performance improvements. for the most sophisticated kernels using blast or psi-blast profiles, however, information about the similarities of aas can already be derived from the profiles and the improvement is marginal. overall, our experiments demonstrate that the proposed kernels indeed lead to a better performance than string kernels and non-substring kernels. these improvements are not major, but consistent. it has to be noted that a big difference between the previously proposed kernels and the proposed kernels cannot be expected: the proposed kernels essentially work on subsets of the features of previously proposed kernels and the improvements that we observe mainly come from the svm’s degraded performance when including uninformative features. in summary, the proposed modifications, in particular the combination with the rbf aa substring kernel, consistently yield improvements without seriously affecting the computing time. in all formulations, the original string kernel formulation can be recovered by appropriately choosing σ. hence, when σ is included in model selection, the performance of the proposed kernels should be at least as good as the original string kernels. we therefore believe that the proposed kernels should be preferred over the original formulations for any protein sequence classification task. list of abbreviations used aa: amino acid; mhc: major histocompatibility complex; svm: support vector machine; wd: weighted degree. competing interests the authors declare that they have no competing interests. authors' contributions nct and gr conceived and designed the project. nct prepared the data, implemented the kernels, performed experiments and drafted the manuscript. cw performed the mtl experiments and contributed to the preparation of manuscript. ok contributed to the discussion and helped writing the manuscript. gr supervised the project, implemented and performed experiments and contributed to the manuscript. 
in summary, the proposed modifications, in particular the combination with the rbf substring kernel, consistently yield improvements without affecting the computational complexity. although string kernels are already very powerful, when it comes to amino acids they have a major short coming. they ignore an important piece of information when comparing amino acids: the physico-chemical properties such as size, hydrophobicity, or charge. we propose new string kernels that combine the benefits of physico-chemical descriptors for amino acids with the ones of string kernels. the benefits of the proposed kernels are assessed on two problems: mhc-peptide binding classification using position specific kernels and protein classification based on the substring spectrum of the sequences. this information is very valuable, especially when training data is less abundant. string kernels are commonly used for the classification of biological sequences, nucleotide as well as amino acid sequences. our experiments demonstrate that the incorporation of amino acid properties in string kernels yields improved performances compared to standard string kernels and to previously proposed non-substring kernels.
 string kernels are commonly used for the classification of biological sequences, nucleotide as well as amino acid sequences. although string kernels are already very powerful, when it comes to amino acids they have a major short coming. they ignore an important piece of information when comparing amino acids: the physico-chemical properties such as size, hydrophobicity, or charge. this information is very valuable, especially when training data is less abundant. there have been only very few approaches so far that aim at combining these two ideas.  we propose new string kernels that combine the benefits of physico-chemical descriptors for amino acids with the ones of string kernels. the benefits of the proposed kernels are assessed on two problems: mhc-peptide binding classification using position specific kernels and protein classification based on the substring spectrum of the sequences. our experiments demonstrate that the incorporation of amino acid properties in string kernels yields improved performances compared to standard string kernels and to previously proposed non-substring kernels.  in summary, the proposed modifications, in particular the combination with the rbf substring kernel, consistently yield improvements without affecting the computational complexity. the proposed kernels therefore appear to be the kernels of choice for any protein sequence-based inference. availability data sets, code and additional information are available from http://www.fml.tuebingen.mpg.de/raetsch/suppl/aask. implementations of the developed kernels are available as part of the shogun toolbox. 10– december machine learning in computational biology whistler, canada 