A class of new kernels has been developed for vectors derived from a coding scheme of the k-peptide composition for protein sequences. Each kernel defines the biological similarity for two mapped k-peptide coding vectors. The mapping transforms a k-peptide coding vector into a new vector based on a matrix formed by high BLOSUM scores associated with pairs of k-peptides. In conjunction with the use of support vector machines, the effectiveness of the new kernels is evaluated against the conventional coding scheme of k-peptide (k ≤ 3) for the prediction of subcellular localizations of proteins in Gram-negative bacteria. It is demonstrated that the new method outperforms all the other methods in a 5-fold cross-validation.