  Motivation: Gene selection has become a common task in most gene expression
studies. The objective of such research is often to identify the smallest
possible set of genes that can still achieve good predictive performance. The
problem of assigning tumours to a known class is a particularly important
example that has received considerable attention in the last ten years. Many of
the classification methods proposed recently require some form of
dimension-reduction of the problem. These methods provide a single model as an
output and, in most cases, rely on the likelihood function in order to achieve
variable selection.
  Results: We propose a prediction-based objective function that can be
tailored to the requirements of practitioners and can be used to assess and
interpret a given problem. The direct optimization of such a function can be
very difficult because the problem is potentially discontinuous and nonconvex.
We therefore propose a general procedure for variable selection that resembles
importance sampling to explore the feature space. Our proposal compares
favorably with competing alternatives when applied to two cancer data sets in
that smaller models are obtained for better or at least comparable
classification errors. Furthermore by providing a set of selected models
instead of a single one, we construct a network of possible models for a target
prediction accuracy level.
