Maximum n-times Coverage for Vaccine Design
Ge Liu, Alexander Dimitrakakis, Brandon Carter, David Gifford
Abstract
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 $\tau$. 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.
BibTeX
@inproceedings{
liu2022maximum,
title={Maximum n-times Coverage for Vaccine Design},
author={Ge Liu and Alexander Dimitrakakis and Brandon Carter and David Gifford},
booktitle={International Conference on Learning Representations},
year={2022},
url={https://openreview.net/forum?id=ULfq0qR25dY}
}