Toward a Liquid Biopsy: Greedy Approximation Algorithms for Active Sequential Hypothesis Testing

• 成果类型: Article; Early Access
• 署名作者: Gan, Kyra; Jia, Su; Li, Andrew; Tayur, Sridhar
• 署名单位: Cornell University; Cornell University; Carnegie Mellon University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.00829
• 发表日期: 2025
• 关键词: Active learning; sequential hypothesis testing; Approximation algorithms; early-stage cancer detection

摘要

This paper addresses challenges in developing liquid biopsies for early-stage cancer detection through active sequential hypothesis testing (ASHT). In the problem of ASHT, a learner seeks to identify the true hypothesis (true cancer type) from a known set of hypotheses (candidate cancer types). The learner is given a set of actions (sequencing genetic intervals) and knows the distribution of the random outcome (whether a mutation is detected) of any action under any true hypothesis. Given a target error delta>0, the goal is to sequentially select the fewest number of actions to identify the true hypothesis with probability at least 1-delta. Motivated by applications in which the number of hypotheses or actions is massive (e.g., genomics-based cancer detection), we propose efficient greedy algorithms and provide the first approximation guarantees for ASHT, under two types of adaptivity. Our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. Numerical tests on synthetic and real DNA mutation data show that our algorithms significantly outperform previous heuristic policies.