Optimal Learning for Drug Discovery in Ewing's Sarcoma

Peter I. Frazier, Diana Negoescu, Warren B. Powell

**We
are pleased to announce that Diana Negoescu '09 and Peter Frazier *09 received
the honorable mention in the first "Doing Good with Good OR" competition
sponsored by Informs. Their project addressed the problem of sequencing the
testing of different compounds. For example, in the simple molecule below,
there are two sites where we can put any of six substituents (in this case
the substituents are atoms, but more frequently these are small combinations
of atoms).**

**For larger molecules, there can easily be thousands
or tens of thousands of combinations.**

**The project involved the application of the knowledge
gradient (see the page on Optimal Learning)
to the problem of how to sequence experiments. Each experiment is used to
update a statistical model known in this literature as the Free-Wilson model.
The knowledge gradient identifies the compounds from which we will learn
the most. After each experiment, we update the Free-Wilson model, which
can then be used to predict which compound is the best. Since these experiments
are time consuming and expensive, the goal of this research was to run the
smallest number of experiments.**

** The
research used a version of the knowledge gradient which takes advantage of
correlated beliefs - trying one compound teaches us something about other
compounds due to similarities. This makes it possible to sequence a few hundred
experiments, after which we make a recommendation about the best out of 50,000
compounds. The research required modifications to the algorithm for computing
the knowledge gradient with correlated beliefs. The original algorithm could
handle problems with a few thousand choices, while the largest molecule tested
in this research had 87,000 combinations. The new algorithm, which was mathematically
equivalent, reduced the need to store a covariance matrix with 87,000 rows
and columns to one with only about 200 rows and columns, with a dramatic reduction
in execution times.**

**The figure to the left illustrates the ability of the
KGCB algorithm to quickly find the best molecule compared to a random strategy.
In this experiment, KGCB reliably found the best compound (out of 10,000 choices)
in as little as 20 to 60 experiments, versus 60 to over 120 experiments using
an unstructured strategy. **

**Slide presentation given by Diana Negoescu at Informs
for the competition**

Optimal Learning for Drug Discovery in Ewing's Sarcoma

**Additional readings:**

Diana Negoescu, Peter I. Frazier and Warren B. Powell, "The Knowledge-Gradient Algorithm for Sequencing Experiments in Drug Discovery," more complete technical paper describing the algorithmic research in detail. Click here for technical appendix.

Frazier, P., W. B. Powell and S. Dayanik, “A Knowledge Gradient Policy for Sequential Information Collection,” SIAM J. on Control and Optimization, Vol. 47, No. 5, pp. 2410-2439 (2008). - This is the original theory paper setting up the knowledge gradient algorithm with independent beliefs.

P. Frazier, W. B. Powell, S. Dayanik, “The Knowledge-Gradient Policy for Correlated Normal Beliefs,” Informs Journal on Computing (to appear). - This paper introduces the knowledge gradient algorithm for correlated beliefs. It is limited to problems where the number of potential alternatives to measure is not too large (say, < 1000).