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

This article focuses on the development of efficient algorithms for active sequential hypothesis testing (ASHT) to improve liquid biopsies for early-stage cancer detection. ASHT involves adaptively selecting genetic intervals to sequence from a large set of candidate cancer types (hypotheses) and DNA intervals (actions) to identify the true cancer type with high confidence and minimal cost. The authors propose novel greedy algorithms for both partially adaptive (fixed action sequence with adaptive stopping) and fully adaptive (action choices depend on prior outcomes) settings, providing the first approximation guarantees that scale logarithmically with the number of hypotheses and are independent of the number of actions. Experimental results on synthetic data and real genomic mutation data from the COSMIC dataset demonstrate that these algorithms outperform existing benchmarks, potentially reducing the number of genetic intervals needed for accurate cancer detection. The study also addresses fairness by ensuring error probabilities are controlled uniformly across all hypotheses, and discusses practical considerations such as computational efficiency and cost implications for commercial liquid biopsy tests.