The cost of DNA sequencing has fallen 10,000x in the last ten years, and we are finally in sight of the silver bullet for cancer screening: an early-stage blood test. As sequencing can now be performed affordably on a tiny fraction of a genome, what remains is a massive variable selection problem. We provide an efficient algorithm, based on a decomposition at the gene level, that scales to full genomic sequences across thousands of patients. We contrast our selected variables against DNA panels from two recent, high-profile studies and demonstrate that our own panels achieve significantly higher sensitivities at the same cost, along with accurate discrimination between cancer types for the first time.