The knowledge-gradient algorithm for sequencing experiments in drug discovery

Diana M. Negoescu, Peter I. Frazier, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

92 Scopus citations


We present a new technique for adaptively choosing the sequence of molecular compounds to test in drug discovery. Beginning with a base compound, we consider the problem of searching for a chemical derivative of the molecule that best treats a given disease. The problem of choosing molecules to test to maximize the expected quality of the best compound discovered may be formulated mathematically as a ranking-andselection problem in which each molecule is an alternative. We apply a recently developed algorithm, known as the knowledge-gradient algorithm, that uses correlations in our Bayesian prior distribution between the performance of different alternatives (molecules) to dramatically reduce the number of molecular tests required, but it has heavy computational requirements that limit the number of possible alternatives to a few thousand. We develop computational improvements that allow the knowledge-gradient method to consider much larger sets of alternatives, and we demonstrate the method on a problem with 87,120 alternatives.

Original languageEnglish (US)
Pages (from-to)346-363
Number of pages18
JournalINFORMS Journal on Computing
Issue number3
StatePublished - Jun 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


  • Decision analysis: sequential
  • Simulation: design of experiments
  • Statistics, Bayesian


Dive into the research topics of 'The knowledge-gradient algorithm for sequencing experiments in drug discovery'. Together they form a unique fingerprint.

Cite this