436 Nucleic Acids Research, 2007, Vol. 35, No. 2 the set of all features F: X zs ¼ wf · rf , s‚ f 2F where wf is the weight for feature f. Scores for the highly active molecules are expected to exceed the scores of less active molecules by a value not less than a positive threshold parameter d, which is the width of the separating zone between the two classes. Increasing d improves the robust- ness of the solution: when predicting untrained molecules, we can reduce the number of misclassiﬁed molecules. This comes at the cost of increasing the number of unpredicted molecules since scores within the separating zone are not signiﬁcant enough to classify the underlying siRNA. The sets of above-average and low-activity siRNAs are linearly inseparable. To make the solution of the model feasible, nonnegative error variables eh are introduced for each sequence h in the set H, sequences with experimentally determined high-activity: X f 2F X f 2F wf rf , h þ eh > g þ d‚ wf rf , l þ el < g: where the geometric interpretation of g is the intersection with the vertical axis. For each sequence l in the set L of low-activity sequences we require that The sum of absolute values of weights wf must be limited to keep the model from growing unbound: kwk1 ¼ 1: Here kwk1 is the standard mathematical notation for the sum of the absolute values (ﬁrst norm). We solve the system of the above inequalities and equations to minimize the sum of the error variables eh. min l · Xeh þ ð1 nH h2H nL l Þ · eh þ y · kwk1: Here the user-deﬁned parameter 0 < l < 1 ﬁne-tunes the balance between sensitivity and selectivity. When l is set to a value higher than 0.5, errors related to above-average activity molecules are decreased by allowing more errors in the low-activity molecules. nH and nL are the number of the above-average and low-activity molecules in the training set, respectively. y is a small factor necessary for the calculation of the absolute values of the weights. Solving the above system of linear inequalities by con- strained optimization packages (e.g. CPLEX from ILOG, Incline Village, Nevada) leads to the minimization of errors by selecting the optimal values for the weights wf and the add- itive variable g. Provided that the model has a unique, globally optimal solution, any of the simplex, dual or barrier algo- rithms (23,30) ﬁnds it in practically polynomial time (24). Note that the solution for the above model is more sensi- tive to a few large errors than to several smaller ones. Incor- rect experimental measurements of the knockdown activity may considerably exceed the magnitude of real prediction 1 2 3 4 5 as errors. Such incorrect input data may dislocate the separating zone, resulting in an unjustiﬁably large number of misclassi- ﬁed molecules. We reduce this effect by iteratively elimi- nating the siRNA with the largest error in the previous optimization. The saved basic solution allows solving the model about ten times faster than the ﬁrst time. This is the key to the computational feasibility of several hundred iterations during feature selection (28). For the numerical prediction of the knockdown activities, brute force traditional multivariate regression analysis has limited utility due to the high number of features. Robust Regression (31) was not as accurate as constrained optimiza- tion methods or SVMs (data not shown). In our regression model, for each sequence s, we minimize the absolute value distance from the regression plane: X g þ es ¼ 0‚ 6 wf · rs, f f 2F where as is the experimentally determined knockdown activity of molecule s. Now we minimize the sum of the error variables es and the sum of the absolute values of the wf weights: min Xes þ y · kwk1: s2S 7 Here y is a small factor for the contribution of absolute values. Feature (property or variable) selection emerges as a highly successful new technique (32) for ﬁnding those biological or physical features that indicate or cause a certain effect; e.g. a disease. Selecting the most predictive features by traditional manual methods from among several hundred initial featu- res over thousands of observations is prohibitively time- consuming. Fortunately, machine learning tools can perform such complex tasks in short processor time. Examples include differentially expressed genes as indicators and/or causative agents of cancer (33), semi-supervised learning for molecular proﬁling (34) and optimal selection of hydrophobicity- related, structural and other features determining protein secretion signals (28), physicochemical descriptors to dis- criminate protein–protein interactions (35), and automatic parsing of the biomedical literature (36). These studies revealed diagnostic combinations of features that frequently constituted some important biological signature. Feature selection also reduces overtraining. This is a fundamental issue when we do not have 5–10 times more observations than features (32). For linear SVMs and constrained optimization models, we use a weight-based feature elimination algorithm (28). For comparability with related algorithms below, we abbreviate this algorithm as WFE. A feature’s weight is proportional to its contribution to the prediction (Equations 2 and 3). Fea- tures with zero weights do not contribute to the model and therefore should be eliminated. In each of the subsequent iterations, the feature with the lowest absolute value is elimi- nated. This iteration is repeated until the number of features reaches a user-speciﬁed limit and the cross-validation accu- racy decreases. Fortunately, the wf feature weights are trans- parent in constrained optimization models. In SVMs with linear kernels, wf ¼ Pv av rf,v, where av is the Lagrangian