e22 Nucleic Acids Research, 2008, Vol. 36, No. 4 PAGE 10 OF 11 Table 9. Parameters selected by the restricted grid search in the weighted voting meta-predictors GPS Kinase Kinase Kinase Kinase NetPhos NetP NetP PPSP_ PPSP_ PPSP_ Pred Scansite_ Scansite_ Scansite_ T Phos_90 Phos_95 Phos_100 Phos_bit K_0.3 hosK_0.5 hosK_0.7 highsens balanced highspec Phospho low medium high score CDK 135 CK2 0 PKA 0 PKC 115 0 0 1 15 3 15 1 15 0 0 1 15 3 15 0 0 0 0 0 0 0 0 1 15 0 3 15 0 1 15 1 15 0 0 1 15 0 1 15 0 0 1 15 0 0 9 15 3 15 5 15 1 15 1 15 0 0 1 15 1 15 3 15 0 0 0 5 15 1 15 3 15 1 15 0 0 3 15 0 1 15 0 4 15 2 15 5 15 7 15 of the kinase families. The combination strategy has been successfully applied in making two-class predictions in other problem domains, including the predictions of secreted proteins (5) and transmembrane proteins (26). By applying a logic AND operation to the predictions made by the element predictors, this strategy, in essence, attempts to achieve improved speciﬁcity at the cost of reduced sensitivity. This strategy is expected to work eﬀectively for cases where element predictors have relatively high sensitivity but lower speciﬁcity values. The reduced weighted voting strategy (with weights set by the accuracy or MCC of the element predictors) has produced good meta-predictors in the protein subcellular localization prediction problem (7), but this strategy fails to yield meta-predictors with expected performance in the prediction of phosphorylation sites for the CK2 kinase family. The exact reason for this failure is not clear, although stronger correlation among the element pre- dictors may play a role. Multiple element predictors from a single prediction program are expected to be more highly correlated than those from diﬀerent programs. In the protein subcellular localization prediction problem, only one of the eight prediction programs provided multiple element predictors. In the phosphorylation site prediction problem, however, four of the six prediction programs did so. A general weighted voting strategy Weighted voting with weight parameters selected by grid search is a more general form of the weighted voting strategy. It does not assume that element predictors with better performance will contribute more to the perfor- mance of the meta-predictors. Rather, the weights of all element predictors are determined directly from the data through exhaustive search. This ﬂexible approach not only results in meta-predictors with better predicting performance than combinatorial meta-predictors and reduced voting meta-predictors in the phosphorylation site prediction problem, but it is also expected to work eﬀectively for a wide range of other problem domains. Grid search of large numbers of parameters (16 in this particular case) is very costly in running time. The key to this weighted voting scheme is the ability to restrict the search space to a manageable size without compromising the eﬀectiveness of the search. If an unrestricted grid search is conducted with 16 parameters, each of which is searched in four steps (that is, each parameter is allowed to take four possible values), the total number of parameter permutations is 416 42 billion. A grid search of this scale would take about 14 months to complete with a computer equipped with an Intel Core 2 DUO processor. With the carefully devised restricted search scheme developed in this study, the grid search of the 16 parameters—15 of which were searched in 9 steps, and the 16th in 16 steps) was completed in only about 10 h for each of the four kinase families. Limitation of voting-based strategies A limitation imposed by voting-based meta-prediction strategies is that they require the output produced by diﬀerent element predictors (which is taken as input of the element predictors) to be compatible with one another. We are working on decision tree- and SVM-based meta- prediction strategies to overcome this problem. It is hoped that these new strategies, which can take advantage of more versatile output of element predictors, will lead to more eﬀective meta-predictors applicable in a wider range of problem domains. SUPPLEMENTARY DATA Supplementary Data are available at NAR Online. ACKNOWLEDGEMENTS We thank Dr W. Pan at the University of Minnesota for inspiring discussions and Dr Q. Zhu at the University of Houston for helpful assistance. We also thank the Supercomputing Institute, University of Minnesota for computational resources. T.L. acknowledges the support of NIH (1R21CA126209) and Minnesota Medical Foun- dation. X.G. acknowledges the support of NIH/GM/AI (R43 GM076941, 1R21CA126209) and the R. A. Welch Foundation (E-1270). Funding to pay the Open Access publication charges for this article was provided by NIH/NCI. Conﬂict of interest statement. None declared. REFERENCES 1. Editorial (2006) Web Server issue. Nucleic Acids Res., 34, W1. 2. Tompa,M., Li,N., Bailey,T.L., Church,G.M., De Moor,B., Eskin,E., Favorov,A.V., Frith,M.C., Fu,Y. et al. (2005) Assessing computational tools for the discovery of transcription factor binding sites. Nat. Biotechnol., 23, 137–144.