We present a sparse knowledge gradient (SpKG) algorithm for adaptively selecting the targeted regions within a large RNA molecule to identify which regions are most amenable to interactions with other molecules. Experimentally, such regions can be inferred from fluorescence measurements obtained by binding a complementary probe with fluorescence markers to the targeted regions. We perform a regularized, sparse linear model with a log link function where the marginal contribution to the thermodynamic cycle of each nucleotide is purely additive. The SpKG algorithm uniquely combines the Bayesian ranking and selection problem with the frequentist l 1 regularized regression approach Lasso. We use this algorithm to identify the sparsity pattern of the linear model as well as sequentially decide the best regions to test before exhausting an experimental budget. We also develop two new algorithms: batch SpKG and batch SpKG-LM. The first algorithm generates more suggestions sequentially to run parallel experiments. The second one dynamically adds new alternatives, in the form of types of probes, which are created by inserting, deleting, or mutating nucleotides within existing probes. In simulation, we demonstrate these algorithms on the Tetrahymena Group I intron (a midsize RNA molecule), showing that they efficiently learn the correct sparsity pattern, identify the most accessible region, and outperform several other policies.
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Science Applications
- Management Science and Operations Research
- Decision analysis: sequential
- Simulation: design of experiments
- Statistics: Bayesian