e22 Nucleic Acids Research, 2008, Vol. 36, No. 4 of the predictor, because a predictor with very high sensitivity but very low speciﬁcity (or vice versa) is not very useful. Accuracy can indicate the performance of a predictor on its own. However, the accuracy of a predictor can vary considerably with the ratio of positive samples and negative samples in the dataset. MCC is much less susceptible to this problem; it is the most widely used prediction measure for two-class prediction programs. The area under the receiver operating characteristic (or ROC) curve was used to measure the performance of a predicting program or strategy for which multiple conﬁg- urations or options are possible. For each conﬁguration or option, the sensitivity and speciﬁcity were evaluated, the ROC curve [sensitivity versus (1-speciﬁcity) curve] was plotted, and the area underneath this curve was calculated. Combinatorial strategy The ‘combination approach’ or ‘consensus approach’ is a simple meta-prediction strategy that has been used in two-class classiﬁcation problems in other problem domains (5,26). In this approach, the meta-predictor makes predictions by applying logic AND operations to all predictions made by element predictors. In other words, a positive prediction is made by the meta-predictor for a particular sample only if all element predictors make positive predictions on the same sample. Simple voting strategies: unweighted voting, unreduced weighted voting and reduced weighted voting The unweighted voting, unreduced weighted voting and reduced weighted voting strategies were described in the previous study (7). For multi-class prediction problems such as the protein subcellular localization prediction problem, the prediction can be made by picking from the multiple classes the one that gives rise to the highest score, and no score threshold needs to be set. For two-class prediction problems such as the phosphorylation site prediction problem, however, there is the need to set a score threshold. Generally, a linear voting-based two-class classiﬁer makes a positive prediction if the following condition is satisﬁed: N X j¼1 Pj wj T, where N is the number of element predictors (which is equal to 15 for unreduced voting for the phosphorylation site meta-predicting problem, and it will take a smaller integer value for reduced voting schemes); wj is the weight of the jth element predictor—for unweighted voting, wj = 1 for all js; Pj indicates the prediction made by the jth element predictor, Pj = 1 if a positive prediction is made, and Pj = 0 if otherwise; and T is the threshold score. For a simple majority voting, the threshold T should be set as the half of the sum of all weights for the element predictors. That is, 1 XN T ¼ 2 j¼1 wj: 1 2 PAGE 6 OF 11 Restricted grid search In a weighted voting strategy denoted by Equation (1), there are N + 1 parameters—N weight parameters (wj) and the threshold parameter T that need to be determined. Our task is to select proper values for these N + 1 (=16) parameters that would result in a classier with a good predicting performance (in terms of MCC or accuracy). Generally, two approaches can be taken to determine these parameter values: optimization and grid search (or exhaustive search). A large number of optimization algorithms are available which can be applied to ﬁnd a set of ‘optimal parameters’ that maximize the GCC or accuracy. Properly chosen optimization algorithms can be very eﬃcient in run time performance. However, optimization methods may ﬁnd a local, rather than a global, optimum. Grid search is not susceptible to the local optimum problem, but can be very costly in running time. Eﬀective searching of 16 parameters (15 weight and 1 threshold parameters) is a rather challenging task. We developed a restricted grid search scheme to select the values of these 16 parameters. First, we decided that the weight of any element predictors can only take one of the following 9 values: 0, 1 , 3 , 5 , 7 , 9 ,11,13, and 1. 15 15 15 15 15 15 15 Second, we required that the sum of the weights of all 15 element predictors equal 1. With these two restrictions, the number of possible weight combinations is limited to 27, corresponding to 2 659 764 weight permutations, as is summarized in Table 1. With Pj taking one of two possible values: 0 and 1, the weighted sum PjN¼1 ½Pj wj can produce a total of 16 diﬀerent values (Table 2). T could be any of these 16 values. With this scheme, the search space for the 16 parameters was eﬀectively limited to a manageable size of (2 659 764 16 = 42 556 224). The grid search of the 16 parameters was conducted on each of the four MetaPS06 datasets with 10-fold cross-validation. RESULTS Performance assessment of element predictors The predicting performance of each of the 15 element predictors was assessed using these unbiased MetaPS06 datasets. As is shown in Table 3, the element predictors vary considerably in predicting performance. For the four kinase families CDK, CK2, PKA and PKC, the element predictors that oﬀers the best predicting perfor- mance are PredPhospho (accuracy: 0.853, MCC: 0.708), NetPhosK_0.5 (accuracy: 0.871, MCC: 0.730), PredPhospho (accuracy: 0.827, MCC: 0.642) and PPSP_balanced (accuracy: 0.743, MCC: 0.477), respectively. Combinations of element predictors We examined the predicting performance of all combina- torial meta-predictors constructed with 2–6 element predictors, and the combinatorial meta-predictors yielding the best predicting performance are shown in Table 4. For CDK, four combinatorial meta-predictors achieved