Maximum n-times Coverage for Vaccine Design
This work addresses vaccine design for public health by providing a novel computational framework, though it is incremental as it builds on existing coverage problems.
The authors tackled the problem of designing peptide vaccines by introducing the maximum n-times coverage problem, which selects overlays to maximize weighted element coverage with a minimum coverage requirement, and demonstrated its superiority by producing a pan-strain COVID-19 vaccine design that outperformed 29 other designs in predicted population coverage and peptide display.
We introduce the maximum $n$-times coverage problem that selects $k$ overlays to maximize the summed coverage of weighted elements, where each element must be covered at least $n$ times. We also define the min-cost $n$-times coverage problem where the objective is to select the minimum set of overlays such that the sum of the weights of elements that are covered at least $n$ times is at least $τ$. Maximum $n$-times coverage is a generalization of the multi-set multi-cover problem, is NP-complete, and is not submodular. We introduce two new practical solutions for $n$-times coverage based on integer linear programming and sequential greedy optimization. We show that maximum $n$-times coverage is a natural way to frame peptide vaccine design, and find that it produces a pan-strain COVID-19 vaccine design that is superior to 29 other published designs in predicted population coverage and the expected number of peptides displayed by each individual's HLA molecules.