Substantial improvements in cancer survival rates could be achieved by developing better tools to detect occult malignancies at an earlier, more curable stage. Unfortunately, efforts to identify serum protein biomarkers that are sufficiently cancer-specific to be used for screening have found little success. Here, we pursue an alternative strategy based on detection of exceptionally tumor-specific mutant DNA fragments in the circulation of patients with early-stage lung cancer. Because these tumor-derived DNA fragments harbor genetic signatures that would be uncommon in healthy individuals, they hold great promise for screening applications where a high frequency of false-positive results would be unacceptable. However, it is a formidable challenge to create an assay that is able to detect trace quantities of mutant DNA released into the bloodstream from a small, early-stage tumor, without knowing the tumor’s mutation profile beforehand. Additional challenges are posed by economic factors as well as the presence of low-level mutations in the healthy population. To address these challenges, we have assembled a multidisciplinary team with highly complementary expertise from Microsoft Research and from Yale, Rice, and Harvard Universities. In this proposal, we describe innovative solutions in which we apply tools of biochemistry, thermodynamics, machine learning, and biostatistics to develop and validate an ultrasensitive, cost-efficient assay for detecting rare mutant DNA fragments in blood as markers of early-stage lung cancer.