An accurate blood test for early-stage cancer (a “liquid biopsy”) is arguably the most important open problem in oncology, and the race to a solution is tantalizingly close to the finish. In this talk, we will discuss the state of this race as of 2022, particularly how technology and data have enabled progress so far, and how optimization will play a role in reaching the finish line.
Along the way, we will address a set of problems that occur in the development of liquid biopsies via the lens of Active Sequential Hypothesis Testing (ASHT), wherein a learner seeks to identify a true hypothesis using the fewest number of actions. Motivated by applications in which the number of hypotheses or actions is massive (such as our own), we propose efficient (greedy, in fact) algorithms and provide the first approximation guarantees for ASHT. Our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. We numerically evaluate the performance of our algorithms using both synthetic and real-world DNA mutation data, demonstrating that our algorithms drastically outperform previous heuristics.