Maximum n-times Coverage for Vaccine Design
Authors: Ge Liu
Alexander Dimitrakakis
Brandon Carter
David Gifford
Venue: ICLR 2022 Poster (2022)
Keywords: computational biology
vaccine design
COVID-19
maximum n-times coverage
combinatorial optimization
integer linear programming

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.

Published as a conference paper at ICLR 2022
MAXIMUM n-TIMES COVERAGE FOR VACCINE DESIGN
Ge Liu, Alexander Dimitrakakis, Brandon Carter, David Gifford Computer Science and Artificial Intelligence Laboratory Massachusetts Institute Technology gifford @ mit.edu
ABSTRACT
We introduce the maximum n-times coverage problem that selects i overlays to maximize the summed coverage of weighted elements, where each element must be covered at least 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 times is least the multi-set multi-cover
т. Maximum n-times coverage is a generalization problem, is NP-complete, and not submodular. We introduce new practical solutions for n-times coverage based on integer linear programming and sequential greedy optimization. We show that maximum netimee coverage a natural way to frame peptide vaccine design, and find that it produces a pan-strain COVID-19 vaccine design that superior 29 other published designs in predicted population coverage and the expected number of peptides displayed by each individual's 's HLA molecules.
INTRODUCTION
In the maximum n-times coverage problem, a set of overlays is selected to cover elements zero or more times, where each overlay is predetermined cover one or more elements. Each element is assigned a weight that reflects its importance. The objective of the problem is to maximize the sum of the weights of elements that are covered least n times by most & overlays. When the coverage of elements by overlays is determined by a machine learning method, the result summarizes machine learning results with a compact solution that shaped by the element weights employed.
Our introduction of weighted elements and required n-times coverage creates a new class of problem without a known solution or complexity bound for approximate solutions. The closest problem to the maximum n-times coverage problem is the multi-set multi-cover problem which does not assign weights to the elements and thus can be formulated as the Covering Integer Program (CIP) problem (Srinivasan 1999). Thus like CIP, maximum n- o-times coverage is NP-complete. A (n) time approximation algorithm for CIP can violate coverage constraints (Dobson 1982] Kolliopoulos 2003 Kolliopoulos & Young. 2001). Deletion-robust submodular maximization protects against adversarial deletion (Bogunovic et af.) 2018: Mirzasoleiman et al. 2017) and robust submodular optimization protects against objective function uncertainty (Iyer] 2019), but neither guarantees that each element is covered n times.
In this work, we investigate properties of the maximum n-times coverage problem, provide a practical solution to the problem, and use the solution for machine learning based vaccine design. We show that maximum n- n-times coverage not submodular, and introduce NTIMES-IIe and MARGINALGREEDY. efficient algorithms for solving the n-times coverage problem on both synthetic data and real vaccine design. In our framing of vaccine design, an element is a specific collection of HIAA alleles (a genotype), weights are the frequency of genotypes in the population, n is the desired number of peptides displayed by each individual, and an overlay a peptide that is predicted to displayed by each genotype specified number of times. The solution of the maximum n-times coverage problem allows us to find a set of overlays that maximizes the sum of element weights (population coverage). We show that framing vaccine design maximum n-times coverage produces solution that produces superior predicted population coverage when compared to 29 previous published vaccines for COVID-19 with less than 150 peptides.

---

Published as a conference paper at ICLR 2022
2
THE MAXIMUM n-TIMES COVERAGE PROBLEM
2.1 MULTI-SET MULTI-COVER PROBLEM
In the standard SET COVER and MAXIMUM COVERAGE problems, we are given a set U of [
elements (also known as the universe) and a collection S = {Si, ,, S, of m subsets of U such that U. S U. The goal in the SET COVER problem is to select a minimal-cardinality set of subsets from S such that their union covers U. The MUL MULTI-COVER (MSMC) problem a generalization of the SET COVER problem, where multi-sets are sets in which an element can appear more than once. The objective of the MSMC problem is to determine the minimum number of multisets (a multi-set can be chosen multiple times) such that each element i covered at least b; times. It can be formulated into Covering Integer Program (CIP) problem (Srinivasan 1999):
Definition 1. (Covering Integer Program, CIP) Given A E RR b E RT, E 1R4, d E RT,, CIP P = (A, b, w. d) seeks to minimize w subject to Ax 2 b, x E 2T..aadd x S d.
Here Ai represents the number of times i-th element appears the j-th multi-set. The w is set be all 1 in MSMC. The constraints x S b are called multiplicity constraints which limit the number of times a single multi-set can be reused, and they generally make covering problems much harder as natural linear programming (LP) relaxation can have an unbounded integrality gap (Chuzhoy & Naor 2006). Dobson 1982) provides combinatorial greedy H (max; >. Acj) >-approximation algorithm (T) stands for 1-th harmonic number) but multiplicity constraints can be dealt with effectively only in the (0.1) case, and thus this algorithm can be as bad as polynomial. Kolliopoulos & Young (2001): Kolliopoulos 2003 gave tighter- tighter-bound solution that can obtain O n (logg)-approximat -approximation.
Weights
0.3
0.45
0.1
0.15
Covered elements
Chosen overlays
Total coverage
Coverage 2 3 times
Elements
X1
X2
X3
X4
As)
3
0
1
(2)
A1
3
1
0
0
Select subset
Overlays
Objective
Ang)(
0.3 + 0.45
Aa
0
0
2
2
(Xg.
of overlays
A2)
(X1.
X2.
Ag
0
3
0
1
(X2
Objective
A2. 0.3 0.45 0.15
Figure 1: Example of n-times coverage calculation.
2.2 MAXIMUM 7-TIMES COVERAGE
We introduce the maximum n-times coverage problem, variant of the MSMC problem that accounts for multiple coverage of each element while also assigning weights to different elements. We are given a set X' with elements (X1, X2, X2.-.., X1} each associated with non-negative weight w( wxX.). and a set of m overlays A = [A1,A2. Ag......44 Am) }. Each overlay A, covers each element i in X' an element specific number of times e, (X,). which is similar to a multi-set. When (X,),
the element X; is not covered by overlay Aj. We use very strict multiplicity constraint such that each overlay can be used only once. Given subset of overlays S A, the total number of times an element X; is covered by O is the sum of (x,),) for each overlay in O:
C(X,1O) (x,(
JEO
We define the n-times coverage function (O) as the sum of weights of elements X' that are covered at least n times by O. Figure [ shows an example computation of the n-times coverage function.
fn(0) Σ w (XXi) 0)2n)
Σ w/ 1 (X) (X)22)
(2)
The objective of the MAXIMUM n-TIMES COVERAGE problem is to select a set of k overlays 0 S A such that (O) is maximized. This can be formulated as the maximization of the monotone set function (O) under cardinality constraint k:
0 arg max O0)
(3)
ocA.
2

---

Published as a conference paper at ICLR 2022
We define MIN-COST R-TIMES COVERAGE the minimum set of overlays such that the sum of the weights of elements covered at least n times is 2 т. We assume A provides sufficient n-times coverage for (A) We define the n-TIMES SET COVER problem as the special case of MIN-COST 7-TIMES COVERAGE where T = E, w (;)-
MIN-COST n-TIMES COVERAGE
0
arg arg min |O| s.t. fn(O) 2T
(4)
7-TIMES SET COVER
0 = arg min |OI S.t. [n(O) = Sa(A)
(5)
0
Theorem 1. The n-times coverage function fa) is not submodular.
The proof can be found in Appendix A Since the n-times coverage problem is not submodular,
cannot take advantage of the proven near-optimal performance of the greedy algorithm for the SUBMODULAR MAXIMUM COVERAGE problem. Thus we seek new solutions.
3 THE NTIMES-ILA ILP SOLUTION FOR MAXIMUM n-TIMES COVERAGE
We first formulate the maximum-n times coverage problem as an integer linear program (ILP). We associate binary variable a, with each overlay A, such that a, = 1 if A, O and otherwise a, 0. Thus the cardinality constraint can be written as |O| = Σ 0g S k. and the number of times an element X, is covered by O is C(X,l0) Eieo 6 (X, E a&G (X,). The main challenge to encode the objective function fn(O) Ej=1 w(X,) 1 EΣ (X,22x in a linear fashion. We replace the step function L (X,)))))2)) with variable ty such that for each element Xy:
tj =
(X,) 2 and =
Σ (aa(Xx)))) < n
(6)
We enforce the conditions in (6) with the Big M method (Sherali et al. 2013). where we include the following inequalities for each element X3 X:
- 1(1-11 S Σ (x - n + S Mlj,
We set E (0, 1) and choose M to be a large number such as 10,000 which is larger than the term E (X,)
Here prove that t, =1 = Em (xC)(Xx))
Proof. When ty 1, inequality becomes 0 E (X, + S M. If M is large number, we can ignore the right inequality and rearrange to get >m ii= 0 (X,) n Since Σ (X,; and n are both integers and e (0, 1), we find Ex= (,c;(X,) 2 n. All these steps can be taken in the reverse order to prove that Em= (X,(X)) 2 = tj = 1, given that ty is binary variable.
We also prove that 1, 0 + En 0:0; (.:;;(x)) (X,)
<
Proof. We start by showing the forward direction. If t; = 0, then inequality 7 becomes - M < Ei (X,,(Xx)))))) + < 0. As M is large, -M is large negative number, so we can ignore the left inequality. Hence, Σ = (x,, <n- 1 c (X,( and n are integers, for any e (0, Σ i=1 (xc,()) < Rearranging this we get Σ 1= 0:C, 0:c;(Xx (X,) n < O, which forces tú binary variable to be equal 0 from inequality
In the reverse direction. if Σ - (x((X))
because both the quantities Σ m
Therefore, the objective function to maximize becomes fa(O) = Σ/ wl E)_, Σj (X,(),), which is linear as a sum over terms of a binary variable multiplied by constant. The complete NTIMES-ILE ILP formulation of n-times coverage is:
(XX)) =
Variables
3

---

Published as a conference paper at ICLR 2022
d1, .. Om representing presence of each overlay Ai,... Am in final solution
-1,-.4 4 representing if each element X1,-.. X has been covered at least times
Constraints
- - ai S k (the maximum total number of overlays allowed in the final subset)
-M t,) - E. axc((X)) n Mt, for each {1,...?}
. Objective to maximize
- fx = ((x)
If we want to enforce non-redundancy constraints such that pairs of overlays that violate certain distance criteria are not both chosen, we can include additional constraints + Or S 1 for every pair of overlays (At, A,) that we don't 't want both to included in the final subset.
THE MARGINALGREEDS ALGORITHM FOR MAXIMUM n-TIMES COVERAGE
Although NTIMES-ILP can produce near-optimal solutions on problems with reasonable size, may become intractable for problems where hundreds of thousands of elements and/or overlays are involved, such as certain variants of the vaccine design problem. Thus, we seek polynomial time algorithm that provides good solutions to the maximum n-times coverage problem. A naive greedy solution is problematic when the n-times objective directly approached. This a consequence of potential early bad overlay choices by greedy approach that can cause it to fail later to find overlays with sufficient n-times coverage. In addition, during greedy optimization available overlay choices may not provide differential marginal gain to avoid ties and random overlay selection. The MARGINAL GREEDY algorithm is specifically designed to avoid carly bad choices that will lead to failure by marginally approaching the n-times coverage objective. MARGINAL GREEED preserves marginal gains by employing look-ahead tie-breaking that assists in selecting overlays that benefit longer term objectives.
Algorithm 1 MARGINAL GREEDY algorithm (for MIN-COST n- N-TIMES COVERAGE)
Weights of the elements in X:: (X11), w(X2).... w (X),, ground set of overlays where each overlay j in A covers X, for ey (X;) times, target minimum # times being covered Atarggt coverage cutoff for different nı: TI, T2, .2.3 Treargett beam size
Input:
Initialize beam B (0).t t
for I,..., Atarget do
Using set function (S( = Ei=1 u/ w(X:)1 (Xx))(EEees ( as objective function. repeat Kt 00 for E B do for a A' do
Kt is the set of candidate solutions
b Beam search
> Add the candidate solution J {a)} to Kt B++1 - (Top b candidate solutions in Kt as scored by (r))
Kt + K" (a}
1-1+1
m' k- median score of candidate solutions in the beam B'
until m 2 Tn (in Rearger-th -h cycle the termination condition is m (n) 2 Ttarget) (for MAXIMUM n-TIMES COVERAGE with cardinality constraint k. there is additional termination condition >>>>>>>>>> k)
O arg max B fmerrges (S)
Output: The final selected subset of overlays O*
MARGINALGREEDY optimizes n-times coverage with a sequence of greedy optimization cycles where the ne-th cycle optimizes the coverage function (S). We establish coverage starting at 1 and incrementally increase the n-times criteria to ntarget- Thus early overlay selections are guided by less stringent cycle-specifer coverage objectives. A set of coverage cutoffs (TI, T2, ....... Starget) is used as the termination condition for each greedy optimization cycle, and when not specified, we assume 71 72
Tharget by default. We beam search to keep track of top b candidate
4

---

Published as a conference paper at ICLR 2022
solutions each iteration. In general the larger the beam size, the closer the result is to the true optimal. However, there is a tradeoff between beam size and running time. In our results we choose the largest beam size that maintains a practical running time as we describe below.
The full algorithm is given in Algorithm I A similar algorithm can be used to solve the n-TIMES SET COVER problem in which Ttarget Inarrger (A). For the MAXIMUM n-TIMES COVERAGE problem with cardinality constraint k. the optimization terminates when t > k. When beam search is not used to reduce computation time (b = 1), we have extended the algorithm break ties during the n-times coverage iteration by looking ahead to (n + 1)-times coverage. We call this extension look ahead tie tie-breaking. Another advantage of MARGINAL high coverage for n4 < Ntarget by controlling the cycle-specine coverage cutoffs T₁. This is desired in vaccine design where wider population coverage is also important and we want to make sure that almost 1 100% of the population will be covered at least once.
that it is capable of guaranteeing
VACCINE POPULATION COVERAGE MAXIMIZATION
Contemporary peptide vaccine design methods use machine learning scoring of peptide display for HLA alleles followed by the selection of peptides to maximize 1-times coverage. These methods do not accurately model the frequency of HLA haplotypes in a population and thus can not accurately assess the population coverage provided by vaccine. Malone et al. (2020) uses haplotypes but does not explicitly model their frequencies. For a selected set of peptides, the TEDB Population Coverage Tool (Bui et al., 2006) estimates peptide-MHC binding coverage and the distribution of peptides displayed for a given population but does not consider linkage disequilibrium between HLA loci.
We frame vaccine design as maximum n-times coverage because ideally each vaccinated individual in population will be "covered"' by multiple immunogenic peptides. While it might be assumed that an individual will be vaceinated if they display single peptide, three independent lines of reasoning support the need for n-times coverage:
1. When an individual displays multiple peptides their immune system activates and expands more than one set of T cell clonotypes that are poised to fight viral infection (Sekine et al. 2020 Schultheii et al. 2020: Grifoni et al. 2020).
2. The peptides that are immunogenic vary from one individual to another, and thus having multiple peptides displayed increases the probability at least one will be strongly immuno- genic (Croft et al. 2019).
3. If a virus evolves and changes its peptide composition, using multiple peptides reduces the chance of viral escape (Wibmer et al. 202I).
Prior work has not considered formalizing these aspects of vaccine design with an n-times constraint and thus has produced solutions to the 1-times coverage task. Existing solutions to 1-times coverage do not anticipate or solve the n-times coverage task. Both Malone et al. (2020) and [Tousaint let al. (2008) provide solutions to 1-times coverage, [undeegaard et al. (2010) does not provide specific population coverage guarantees, and Oyarzun & Kobe (2015) reviews methods for 1-times coverage. Discrete optimization has been used for other aspects of vaceine design that are unrelated to population coverage, such designing a single peptide sequence that covers a set of diverse but related set of input epitopes (Theiler & Korber 2018), and designing spacers for string-of- peptide delivery (Schubert & Kohlbacher 2016).
For peptide to be effective in a vaccine must be presented by an individual's Major Histocom- patibility Complex (MHC) molecules and be immunogenic. A displayed peptide is immunogenic when it activates cells, which expand number and mount a response against pathogens or tumor cells. Memory T cells provide robust immunity against COVID-19, even in the absence of detectable antibodies (Sekine et al.) 2020)) The use of peptide vaccine components to activate cells is in development for cancer (Hu et al. 2018 and viral diseases including HIV (Arunachalam et al., 2020).
HPV (Kenter et al.] 2009) and malaria (Li et al. 2014 Roosedahl Huber et 2014).
A challenge for the design of peptide vaccines is the diversity of human MHC alleles that each have specific preferences for the peptide sequences they will display. The Human Leukocyte Antigen (HLA) loci, located within the MHC, encode the HIA class I and class II molecules. We consider
5

---

Published as a conference paper at ICLR 2022
the three classical class I loci (HLA-A, HLA-B, and HLA-CC and three loci that encode class II molecules (HLA-DR, HLA-DQ, and HLA-DP). A single chromosome contains one allele at each locus. We use haplotype represent combination of HLA alleles in single chromosome, denoted as A,ByCk for MHC class I or DR, DQ, D& for MHC class II. Each haplotype has a frequency G(i, k) in given population where Σ E Ek=1 kk 1. Each individual inherits two haplotypes form their diploid genotype and may carry 3-6 different alleles per MHC class depending on the zygosity. The frequency of diploid genotype is thus (MHC class I as an example);
(8) We use observed frequencies of 2,138 MHC class I and 1,711 MHC class II haplotypes for our population coverage optimization. Each haplotype represents a specific combination of 230 different HLA-A, HLA-B, and HLAAC alleles (MHC class 1) or 280 different HLAADPP, HL.A-DQ, and HIA-- DR alleles (MHC class II) (Liu et al., 2020). Our use of haplotypes models the linkage disequilibrium between HLA genes. We separately select MHC class and class II epitopes using n-times coverage and then combine them in single vaccine delivery construct for an effective immune response.
phiikkiaazzk F(A, B/ Ck2, Aig Bi Ckg) = Gi,,, (12, K2)
We adopt an experimentally calibrated model of peptide-HL.A HLA immunogenicity to design vaccines using n-timmes coverage (Liu et al. 2021) (Appendix B We utilize the observed immunogenicity of peptides in convalescent COVID- patient peripheral blood mononuclear cell samples (Snyder ctt al. 2020 Klinger et al., 2013 Nolan et al. 2020), and use these data to select machine learning models to predict immunogenicity for peptides or HLA alleles that are not observed in the clinical data. We define peptide-HLA hit (peptide, HLA allele) pair where the peptide is predicted to be immunogenic and displayed by the HLA allele. Once we have determined a candidate set of peptides that are predicted to be immunogenic, we then need to select a minimal subset of peptides such that each individual in Ttarget of the population is predicted to have at least n peptide-HL. HLA hits.
We first introduce BvalVax-Robuss an evaluation tool for estimating the population coverage of proposed peptide vaccine set. EvalVax-Robuse evaluates the percentage of the population having at least n peptide-HLA binding hits in each individual. For a given peptide p and a class HLA allele X E A UAB B U,, our machine learning model outputs a binary hit prediction (x(X)= E {0, 1} indicating peptide-HLA immunogenicity, For each diploid genotype we compute the total number of peptide-HLA hits as the sum of (X) over the unique HLA alleles in the genotype.
of dnjskrézizkz cp(A,, B,, Okt By,
ex(X
(9)
XE(Ai, B, .ct Ju(Ai,.B,,.Ca
The total number of peptide-HLA hits provided by set of peptides O is the sum of number of hits per peptide: chink C(A,, B3, Ck. A., A,,
Σ C,,,,, Bj, Ok, A,, Byy
(10)
PEO
We define the EvalVax- Robbut predicted population coverage with 2 n peptide- HLii hits for a peptide vaccine set P as:
LAI MΣΣΣΣX Σ
LAI
B
IC|
(O)
F Fiuikiaak 1 (h 2 n}
(11)
i= = =1= 12=
Eval population coverage optimization can be accomplished by solution to the maximum n-times coverage problem, as we can rewrite equation (IT) into equation (2) by setting X' to be the set of possible genotypes in.i K1 i2j2k2, and the weights wxX,) be the genotype frequencies &r The peptide candidate set is the set of possible overlays AA, where each peptide p E A kaizzkz times. We directly applied MARGINAL
an overlay which covers a genotype pp on EvalVax-Robur objective function with beam size of 10 for MHC class I and 5 for MHC class II, but we further reduced peptide redundancy by eliminating unselected peptides that are within three (MHC class 1) or five (MHC class II) edits on sequence distance metric from the selected peptides at each iteration. The same non redunddddn constraints are added to NTIMES- - as described in Section 3 As the number of unique genotypes is on the scale of millions (IM for MHC class I and 0.6M for MHC class II), for NTIMES- ILP we used an alternative objective f (O) that computes n-times coverage at the haplotype level for better tractability.
|A| [8| [c
fr((O) hap = ΣΣ ΣΣΣ
G(i,j.k) 1(C 2 n}
(12)
6

---

Published as a conference paper at ICLR 2022
A.times set LoverSSSAALL.OOOO..
Macimum petines coverage/SMLL..e))
Maximum n-timne coverageiSMALL.cs
meths
1M47: wwr.br 1822
LMtGurs
P-tme oovenge
0.8-
0.-
0.6
retiedd
Narg CreedyyDuun
Hargiorodyylou
02-
Gredy
Random obbeet
Rersom subset Thee Ogt ma!
Greedy
00
Toge Optinal
0.5
6 Aum ovedly used
6 Jum, overlsys uand coverageiLAGG
10
0-onsc100)
coverage
Maximum
12
Gready
Taue Optinal
0.6-
rchod
0.
nethed [UDOund)
0.4
UriGurt
0.4
Random
0.0
0.0
Optimal
125
Peppurod Fumbbr of Uinc soaaell
Kum ovellyys
Num,
Figure 2: The MARGINAL.GREEDY and NTIMES-ILP algorithms outperform the greedy algorithm on both LARGE and SMALL toy examples. Superior performance is seen both the n-TIMES SET COVER where smaller number of overlays is used by MARGINALGREED and NTIMES-ILP to achieve 100% coverage at different criteria of n, and on the MAXIMUM R-TIMES COVERAGE problems where MARGINALGREEDY and NTIMES- ILP achieve higher coverage given same number of overlays. Shaded regions indicate 95% confidence intervals.
RESULTS
6.1
TOY EXAMPLES
We empirically evaluate the NTIMES- ILP and MARGINALGREEDY algorithms with two toy amples: a LARGE dataset where a set of 30 overlays are randomly generated to cover set of 10 elements (with equal weights) 1, or 2 times, and SMALL dataset where a set of 10 overlays that were randomly generated to cover a set of 5 elements with equal weights 0, 1, or 2 times. Figure shows the efficiency the NTIMES-ILP and MARGINALGRREDE algorithms on both the n-TIMES SET COVER and MAXIMUM R-TIMES COVERAGE problems for varying values of n. We compare our algorithms to greedy algorithm that directly optimizes n-times coverage and find the greedy algorithm degenerates to sub-optimal solutions for large values of n. These sub sub-optimal solutions can be as bad as random. We also compute the true optimal solution with exponential-tings exhaustive search. We repeated problem generation and optimization with 6 different random seeds to provide confidence bounds and used beam size As shown in Figure 2 NTIMES-ILE achieves true optimal in all datasets and MARGINAL outperforms greedy on all tasks and datasets. We observed that MARGINALGREEDY has a significant advantage over greedy in tests with larger and in regions of higher coverage. Appendix [ contains additional results for a more complex dataset with unequal element weights and sparser overlays, as well as a comparison an additional local search baseline (hill climbing with restarts).
with look-ahead tie-breaking for MARGINAI.GRFEI
6.2 COVID-19 19 VACCINE DESIGN USING MAXIMUM N-TIMES COVERAGE
We used both the NTIMES-ILP and MARGINALGREEDY algorithms to design peptide vaccines for COVID-19 and evaluated the population coverage with different number of HLA-peptide hits (1 S 8) using Eval Robust..........omoo For MARGINALGREEDS the time complexity of the algorithm is polynomial, O(bdp), where v is the vaccine size, b is the beam width, d is the number HLA diploid genotypes, and is the number of peptides. For the COVID-19 19 vaccine problem, this is O ), and our implementation typically takes 225 CPU hours (with parallelization finishes in <1 hour) for vaccine design. By point of contrast, exhaustive search is (*) d, which is O(10s5).
We compared our vaccine designs with 29 vaccine designs in the literature on the probability that vaccine has at least N peptide-HLA hits per individual in a population, and the expected number of per individual peptide-HLA hits in the population, which provides insight on how well a vaccine is displayed on average. Figure 3 shows the comparison between OptiVan Vax (A) MHC class and (B) class II vaccine designs at all vaccine sizes from 1-45 peptides (colored curves) and baseline vaccines
7

---

Published as a conference paper at ICLR 2022
Optifiic va Bexalines 1
NHC1 Optifiis va Besalites p
(3)
MHCC Oytitees va. Baxelines pir
16
25
Snodow
0.0
20-
Bi Mi.hgpalppp..e
Addid
Exatin Bobui
3.6
25-
onanachbya
Strohwee
10
12-
02
peptides
peptides
humber peptides
MBHC2 Outivbx Base
H44C2 Basclines
MHC2 Opti/aac p (1)
sandon
Distee Poteee-tbbutttoo Coneenttoo
10.0
Gat
244
022
0.0
20
20
35
10
20
30
40
Number of papt dis
Namber of peptides
humber of peptides
Number of peptades
Figure 3: Eval population coverage evaluation of SARS-CoV-2 vaccines for (top) MHC class and (bottom) MHC class II. (a) Vax--Rbustt population coverage with n 2 1 peptide- HLad hits per individual, performances of 3 variants of OptiVa Vax are shown by curves and bascline performance shown by red crosses (labeled by name of first author).
population coverage with n 2 5 -Lgiide-HLAAA hits. (c) veralVax-Robll population coverage with n 2 8 peptide-HL.c hits. (d) Comparison of OptiVa Vax and baselines expected number of peptide- HLA hits.
(b)
WaeVVee--aaaa Robustt pina 51-90 52%
Op00 septidee
IS-GFFL IN WARARSLL
ITSAARO LOR
PILTNONS ADR/30
LYPTAST (D)
"SNErOO (ORFIE
FRAGEARTI CORPTN
VE2H RARA (22)
LANWTEAY (OFFTel
CACYLNTIC (09736
Yet
Ro
(a) EralVicePobuat aiea SJ- 1b)
Osttlc--PPOuro VHCZ papticias prackdtdd binding 450-M
CATAATAALL 150
ALLSANATICATTION CONTMA
ITOPRAATI UNSMRAATTAA VAA ORF IN
WONENOERUTON.DDDD (2)
CUEAT
Figure 4: SARS-CoV-2 OptiVax selected peptide vaccine using NTIMES-ILP on haplotypes for (A) MHC class I and (B) MHC class II. (a) EvalVax-Robuu population coverage at different per- individual number of peptide-HLA hit cutoffs for populations self- reporting having White, Black, or Asian ancestry and average values. (b) Binding of vaccine peptides to each of the available alleles.
(red crosses) from prior work. We observe superior performance of OptiVax vaccine designs on all evaluation metries at all vaccine sizes for both MHC class and class II. Most baselines achieve reasonable coverage at 2 1 peptide hits. However, many fail to show a high probability of higher hit counts, indicating lack of predicted redundancy if single peptide is not displayed. Note that OptiVax- OptiVax-Margine MarginalGGredyy also outperforms all baselines on n = 1 coverage and achieve 99.99% (MHC class 1) and 99.67% (MHC class II) coverage for n 1, suggesting its capability to cover almost full population at least once while optimizing for higher peptide display diversity.
MHC class I results. We selected an optimized set of peptides from all SARS-CoV. proteins using NT ILP and MArGiNALGREEDY We use an MHC class I integrated model of peptide-HLA immunogenicity for our objective function. After all filtering steps, we considered 1,100 candidate peptides. With Opti VaP, we design a vaccine with 19 peptides that achieves 99.999% Eval Vax- Robust coverage over populations self-reporting as having Asian, Black, or White ancestry with at least one HeLtide-HLA hit per individual. This set of peptides also provides 98.52% coverage with at least peptide-HLE HLA hits and 85.40% coverage with at least 8 peptide- HLA hits (Figure 4 Table S2). With Opti VatiVax-Ne VaaiaaaMaaginaGreeee MarginalGreedy, we design vaccine with 19 peptides that achieves 99.999% VaalVa--Roballl coverage over populations repf-repo as having Asian, Black, or White ancestry with at least one peptide-HI -I.A hit per individual. This set of peptides also provides 98.58%
8

---

Published as a conference paper at ICLR 2022
140
Vax Acbust ginz St-00 Sals
(b)
Ostiva www.yyyrooyyyooooyyoo.o pepoides predkttes sinding <5teet
SONDRSRE 3H
PESMISOD JOMEELS
WANITAA (22)
PROMASGIA IONVER
TEKOOINES (0R722
AVROLUT LoS
7TM mm SORPTAL
HEAB
Erggteoeerrrreyyyyoooo Creapy
STOEP med DOLL 30
TSANOOMA PONEEALD JORTSA
KLLISAAA TAATHACIT
COA (2R73)
THGAA6I SCWVARAAAA can 1SU
10123
Figure 5: SARS-Co Opti Vax selected peptide vaccine set using MARGINAL
coverage with at least 5 peptide-HLA hits and 87.97% coverage with at least 8 peptide-HI.A hits (Figure 5A, Table(S2) The population level distribution of the number of peptide-HLA hits in White, Black, and Asian populations is shown in Figure SA, where the expected number of peptide-HLA hits 11.355, 11.151 and 12.984, respectively.
MHC class II results. We use an MHC class II model of peptide-HL. HLA immunogenicity for our objective function. After all filtering steps, we considered 4, 4,195 candidate peptides. With NTIMES- ILP, we design a vaccine with 19 peptides that achieves 99.65% Eval coverage with at least one reptide-HLA hit per individual. This set of peptides also provides 94.22% coverage with at least 5 Speptde-HHLe HLA hits and 83.76% coverage with at least peptide-HLA hits (Figure 4B, Table S2). With MARGINALGREEDY, we design a vaccine with 19 peptides that achieves 99. 9.63% Eval Vax- Robust coverage with at least one peptide-HLA hit per individual. This set of peptides also provides 96.75% coverage with at least 5 peptide- -I hits and 87.35% coverage with at least 8 peptide-HL.A hits (Figure 43. Table (2).. The population level distribution of the number of peptide-HLA hits per individual in populations self-reporting as having Asian, Black, or White ancestry is shown in Figure 5B where the expected peptide- -LL hits is 17.206, 16.085 and 11. 11.210, respectively.
Table S2 shows the evaluation of our ApiiVax-Robuse vaccine designs using the MARGINALGREEDD algorithm compared to 29 designs by others as baselines. We note that is natural that our designs that were both optimized and evaluated with the same objective performed the best. To provide fair comparison, we also evaluated all designs with an immunogenicity model that does not incorporate clinical data and found that our designs also performed the best (Figure ST. The metric used in all cases is vaccine population coverage, which a common metric (Bui et al. 2006). Thus, part of the contribution of the present work is emphasizing the value of combining machine learning predictions with combinatorial optimization for principled vaccine design.
7 CONCLUSION
We introduced the maximum n-times coverage problem, and showed that it is not submodular. We presented both a novel ILP based method and beam search algorithm for solving the problem, and used them to produce a peptide vaccine design for COVID-19. We compared the resulting optimized peptide vaceine designs with 29 other published designs and found that the optimized designs provide substantially better population coverage for both MHC class I and class II presentation of viral peptides. The use of n-times coverage as an objective increases vaccine redundancy and thus the probability that one of the presented peptides will be immunogenic and produce a T cell response. We are presently testing our pan-strain COVID-19 vaccine in mouse challenge studies for protection against COVID variant of concern. Our pan-strain vaccine delivers MHC class and class II n-times coverage optimized epitopes with a single mRNA-LNP construct. Our methods can also be used to augment existing vaccine designs with peptides improve their predicted population coverage by initializing the algorithm with peptides that are present in an existing design. We provide an open- source implementation of our methods at http::t////. / wwg.t.huuu.... com/ gi fffifffrddooo Tab/ opt i

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was supported in part by Schmidt Futures, a Google Cloud Platform grant, and C3.AI DTI Award to D.K.G. Ge Liu's contribution was made prior to joining Amazon.
REFERENCES
Miysaa I Abdelmageed, AbdeIrahman Hamza Abdelmoneim, Mujahed Mustafa, Nafisa M Elfadol, Naseem S Murshed, Shaza W Shantier, and Abdelrafie M Makhawi. Design of multi epitope-based peptide vaccine against E protein of human 2019-nCoV: An immunoinformatics approach. bioRxiv, 2020.
Tobias Achterberg. SCIP: solving constraint integer programs. Mathematical Programming Compu- tation, 1(1): 2009.
Syed Faraz Ahmed, Ahmed A Quadeer, and Matthew R McKay. Preliminary identification of potential vaccine targets for the COVID-19 coronavirus (SARS-CoV-2) based on SARS-CoV immunological studies. Viruses, 12(3):254, 2020.
Mst Rubaiat Nazneen Akhand, Kazi Faizul Azim, Syeda Farjana Hoque, Mahmuda Akther Moli, Bijit Das Joy, Hafsa Akter, Ibrahim Khalil Afif, Nadim Ahmed, and Mahmudul Hasan. Genome based evolutionary study of SARS-CoV-2 towards the prediction of epitope based chimeric vaccine. bioRxiv, 2020.
Prabhu Arunachalam, Tysheena P. Charles, Vineet Joag, Venkata S. Bollimpelli, Madeleine K. D. Scott, Florian Wimmers, Samantha L. Burton, Celia C. Labranche, Caroline Petitdemange, Sailaja Gangadhara, Tiffany M. Styles, Clare F. Quarnstrom, Korey A. Walter, Thomas Ketas, Traci Legere, Pradeep Babu Jagadeesh Reddy, Sudhir Pai Kasturi, Anthony Tsai, Bertrand Z. Yeung, Shakti Gupta, Mark Tomai, John Vasilakos, George M. Shaw, Chil-Yong Kang, John P. Moore, Shankar Subramaniam, Purvesh Khatri, David Montefiori, Pamela A. Kozlowski, Cynthia A. Derdeyn, Eric Hunter, David Masopust, Rama R. Amara, and Bali Pulendran. T cell-inducing vaccine durably prevents mucosal SHIV infection even with lower neutralizing antibody titers. Nature Medicine, 2020.
Amrita Banerjee, Dipannita Santra, and Smarajit Maiti. Energetics based epitope screening in SARS CoV-2 (COVID 19) spike glycoprotein by immuno-informatic analysis aiming a suitable vaccine development. bioRxiv, 2020.
Vargab Baruah and Sujoy Bose. Immunoinformatics-ain identification of T cell and B cell epitopes in the surface glycoprotein of 2019-nCoV. Journal of Medical Virology, 2020.
Manojit Bhattacharya, Ashish Sharma, Prasanta Patra, Pratik Ghosh, Garima Sharma, Bidhan C Patra, Sang-Soo Lee, and Chiranjib Chakraborty. Development of epitope-based peptide vaccine against novel coronavirus 2019 (SARS-COV-2): Immunoinformatics approach. Journal of medical virology, 92(6):618 12166366 2020.
Ilija Bogunovic, Junyao Zhao, and Volkan Cevher. Robust maximization of non-submodular objec- tives. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
Huynh-Hoa Bui, John Sidney, Kenny Dinh, Scott Southwood, Mark Newman, and Alessandro Sette. Predicting population coverage of T-cell epitope-based diagnostics and vaccines. BMC bioinformatics, 7(1):153, 2006.
Roman M Chicz, Robert G Urban, William S Lane, Joan Gorga, Lawrence J Stern, Dario AA Vignali, and Jack L Strominger. Predominant naturally processed peptides bound to HLA-DRI are derived from MHC-related molecules and are heterogeneous in size. Nature, 358(638)) 1992.
Julia Chuzhoy and Joseph Naor. Covering problems with hard capacities. SIAM Journal on Computing, 36(2):498-51) 2006.
UniProt Consortium. UniProt: a worldwide hub protein knowledge. Nucleic acids research, 47 (D1): 2019.
10

---

Published as a conference paper at ICLR 2022
Bruno Coutard, Coralie Valle, Xavier de Lamballerie. Bruno Canard, NG Seidah, and E Decroly. The spike glycoprotein of the new coronavirus 2019-nCoV contains a furin-like cleavage site absent in CoV of the same clade. Antiviral research, 176:104743 2020.
Nathan P Croft, Stewart A Smith, Jana Pickering, John Sidney, Bjoern Peters, Pouya Faridi, Matthew Witney, Prince Sebastian, Inge EA Flesch, Sally L Heading, et al. Most viral peptides displayed by class I MHC on infected cells are immunogenic. Proceedings of the National Academy of Sciences, 116(8):312231117, 2019.
Gregory Dobson. Worst-case analysis greedy heuristics for integer programming with nonnegative data. Mathematics of Operations Research, 7(4):515-531, 1982.
Stefan Elbe and Gemma Buckland-Merred Data, disease and diplomacy: GISAID's innovative contribution to global health. Global Challenges, 1(1):33-46, 2017.
Ethan Fast, Russ B Altman, and Binbin Chen. Potential T-cell and B-cell epitopes of 2019-nCoV. bioRxiv, 2020.
Alba Grifoni, Daniela Weiskopf, Sydney Ramirez, Jose Mateus, Jennifer M Dan, Carolyn Rydyznski Moderbacher, Stephen A Rawlings, Aaron Sutherland, Lakshmanane Premkumar, Ramesh S Jadi, et al. Targets T cell responses to SARS-CoV-2 coronavirus in humans with COVID-19 disease and unexposed individuals. Cell, (3((7)1149--100) 2020.
Ekta Gupta, Rupesh Kumar Mishra, and Ravi Ranjan Kumar Niraj. Identification of potential vaccine candidates against SARS-CoV-2, step forward to fight novel coronavirus 2019-nCoV: A reverse vaccinology approach. bioRxiv, 2020.
Ramneck Gupta, Eva Jung, and Søren Brunak. Prediction of N-glycosylation sites in human proteins. In preparation, 2004, URL http: www. cbs. dt dk/ /k//sevvvice////ttGtly..
James Hadfield, Colin Megill, Sidney M Bell, John Huddleston, Barney Potter, Charlton Callender, Pavel Sagulenko, Trevor Bedford, and Richard A Neher. Nextstrain: real-time tracking of pathogen evolution. Bioinformatics, 34(23):4121-44
2018.
Charles V Herst, Scott Burkholz, John Sidney, Alessandro Sette, Paul Harris, Shane Massey, Trevor Brasel, Edecio Cunha-Neto, Daniela S Rosa, William Chong Hang Chao, et al. An effective CTL peptide vaccine for ebola zaire based on survivors' CD&+ targeting a particular nucleocapsid protein epitope with potential implications for COVID-19 vaccine design. Vaccine, 2020.
Zhuting Hu, Patrick A Ott, and Catherine J Wu. Towards personalized, tumour-specific,, therapeutic vaccines for cancer. Nature Reviews Immunology, 18(3):168, 2018
Rishabh Iyer. A unified framework of robust submodular optimization. arXiv:1906.06390 2019.
arXiv preprint
Vanessa Jurtz, Sinu Paul, Massimo Andreatta, Paolo Marcatili, Bjoern Peters, and Morten Nielsen. NetMHCpan-4.0: improved peptide-MHC class interaction predictions integrating eluted ligand and peptide binding affinity data. The Journal of Immunology, 199(9):3360-33)) -366, 2017.
Gemma G Kenter, Marij JP Welters, A Rob PM Valentijn, Margriet JG Lowik, Dorien MA Berends- van der Meer, Annelies PG Vloon, Farah Essahsah, Lorraine M Fathers, Rienk Offringa, Jan Wouter Drijfhout, et al. Vaccination against HPV-16 oncoproteins for vulvar intraepithelial neoplasia. New England Journal of Medicine, 169111918838-11 -18888888888888888 2009.
Arbaaz Khan, Aftab Alam, Nikhat Imam, Mohd Faizan Siddiqui, and Romana Ishrat. Design of an based peptide vaccine against the Severe Acute Respiratory Syndrome Coronavirus-2 (SARS-CoV-2) A vaccine informatics approach. bioRxiv, 2020.
Mark Klinger, Francois Pepin, Jen Wilkins, Thomas Asbury, Tobias Wittkop, Jianbiao Zheng, Martin Moorhead, and Malek Faham. Multiplex identification of antigen-specifie T cell receptors using combination of immune assays and immune receptor sequencing. PLoS One, 10(10):e0141561 2015.
11

---

Published as a conference paper at ICLR 2022
Stavros G Kolliopoulos.
Approximating covering integer programs with multiplicity constraints. Discrete applied mathematics, 129(2-3::461-4733 2003.
Stavros G Kolliopoulos and Neal E Young. Tight approximation results for general covering integer programs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. IEEE, 2001.
Chloe Hyun-Jung Lee and Hashem Koohy, In silico identification of vaccine targets for 2019-nCoV. F1000Research, 9, 2020.
Weidang Li, Medha D Joshi, Smita Singhania, Kyle Ramsey, and Ashlesh Murthy. Peptide vaccine: progress and challenges. Vaccines, 2(3):515-553)) 2014.
Ge Liu, Brandon Carter, Trenton Bricken, Siddhartha Jain, Mathias Viard, Mary Carrington, and David K Gifford. Computationally optimized SARS-CoV-2 MHC class I and II vaccine formula- tions predicted to target human haplotype distributions. Cell Systems, 11(2):311144, 2020.
Ge Liu, Brandon Carter, and David K Gifford. Predicted cellular immunity population coverage gaps for SARS-CoV-2 subunit vaccines and their augmentation by compact peptide sets. Cell Systems, 12(1):102-1077 2021.
Claus Lundegaard, Buggert, Ac Karlsson, Ole Lund, Carina Perez, and Morten Nielsen. PopCover: method for selecting of peptides with optimal population and pathogen coverage. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, pp. 658-659, 2010.
Brandon Malone, Boris Simovski, Clément Moliné, Jun Cheng, Marius Gheorghe, Hugues Fontenelle, Ioannis Vardaxis, Simen Tennøe, Jenny-Ann Malmberg, Richard Stratford, et al. Artificial intel- ligence predicts the immunogenic landscape of SARS-CoV-2 leading to universal blueprints for vaccine designs. Scientific Reports, 10(1): 1-14, 2020.
Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Deletion-robust submodular maximiza- tion: Data summarization with the right to be forgotten. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2449-2458, JMLR. org, 2017.
Debarghya Mitra, Nishant Shekhar, Janmejay Pandey, Alok Jain, and Shiv Swaroop. Multi-epitope based peptide vaccine design against SARS- PORS-CoV-L V-2 using its spike protein. bioRxiv, 2020.
Sean Nolan, Marissa Vignali, Mark Klinger, Jennifer N Dines, Ian M Kaplan, Emily Svejnoha, Tracy Craft, Katie Boland, Mitch Pesesky, Rachel M Gittelman, et al. large-scale database of T-cell receptor beta (TCR33) sequences and binding associations from natural and synthetic exposure to SARS-CoVa Research Square, 2020. doi:
Timothy J O'Donnell, Alex Rubinsteyn, and Uri Laserson. MHCflurry 2.0: Improved pan-allele prediction of MHC class I-presented peptides by incorporating antigen processing. Cell Systems, 11(1):42 48, 2020.
Patricio Oyarzun and B Kobe. Computer-aidee design T-cell epitope-basse based vaccines: addressing population coverage. International Journal of Immumogenetics, 42(55:313333) 321, 2015.
Asaf Poran, Dewi Harjanto, Matthew Malloy, Michael S Rooney, Lakshmi Srinivasan, and Richard Gaynor. Sequence-basee prediction of vaccine targets for inducing T cell responses to SARS-CoV-2 utilizing the bioinformatics predictor RECON. bioRxiv, 2020.
Arunachalam Ramaiah and Vaithilingaraja Arumugaswami. Insights into cross-species evolution of novel human coronavirus 2019-nCoV and defining immune determinants for vaccine development. bioRxiv. 2020.
Melissa Rist, Alex Theodossis, Nathan P Croft, Michelle A Neller, Andrew Welland, Zhenjun Chen, Lucy Sullivan, Jacqueline M Burrows. John J Miles, Rebekah M Brennan, et al. HLA peptide length preferences control CD8+ T cell responses. The Journal of Immunology, 1910)) 191(2):561-571, 2013.
12

---

Published as a conference paper at ICLR 2022
Sietske Rosendahl Huber, Josine van Beek, Jørgen de Jonge, Willem Luytjes, and Debbie van Baarle. cell responses to viral infections opportunities for peptide vaccination. Frontiers in immunology. 5:171, 2014.
Ratnadeep Saha and Burra VLS Prasad. In silico approach for designing of multi-epitope based vaccine against novel Coronavirus (SARS-COV-2). bioRxiv, 2020.
Paul Saikko, Jeremias Berg, and Matti Järvisalo. LMHS: a SAT-IP hybrid MaxSAT solver. Inter- national Conference Theory and Applications of Satisfiability Testing, pp. 539-546. Springer, 2016.
Haroldo Santos and Tulio Toffolo. Mixed integer linear programming with Python, 2020.
Benjamin Schubert and Oliver Kohlbacher. Designing string-of-beettt of-beads vaccines with optimal spacers. Genome Medicine, 8(1):1-10, 2016.
Christoph Schultheiß, Lisa Paschold, Donjete Simnica, Malte Mohme, Edith Willscher, Lisa von Wenserski, Rebekka Scholz, Imke Wieters, Christine Dahlke, Eva Tolosa, et al. Next-generation sequencing of and B cell receptor repertoires from COVID-19 patients showed signatures associated with severity of disease. Immunity, 53(2):442-453 2020.
Takuya Sekine, André Perez-Potti, Olga Rivera- Balees--allssteos, Kristoffer Strålin, Jean- Gorin, Annika Olsson, Sian Llewellyn-Lacey. Habiba Kamal, Gordana Bogdanovic. Sandra Muschiol, et al. Robust T cell immunity in convalescent individuals with asymptomatic or mild COVID-19. Cell, 183:158-168, 2020.
Hanif D. Sherali, John J. Jarvis, and Mokhtar S. Bazaraa. Linear Programming And Network Flows. John Wiley & Sons Incorporated, 2013.
Abhishek Singh, Mukesh Thakur, Lalit Kumar Sharma, and Kailash Chandra. Designing multi- epitope peptide-based vaccine against SARS-CoV-2. bioRxiv, 2020.
Thomas M Snyder, Rachel M Gittelman, Mark Klinger, Damon H May, Edward J Osborne, Ruth Taniguchi, H Jabran Zahid, Ian M Kaplan, Jennifer N Dines, Matthew N Noakes, al. Magnitude and dynamics of the T-Cell response to SARS-CoV-2 infection at both individual and population levels. medRxiv, 2020. doi: https:/dooioog//0.11///000000000
201666777.
Aravind Srinivasan. Improved approximation guarantees for packing and covering integer programs. SIAM Journal on Computing, 29(2):648-670, 1999.
Sukrit Srivastava, Sonia Verma, Mohit Kamthania, Rupinder Kaur, Ruchi Kiran Badyal, Ajay Kumar Saxena, Ho-Joon Shin, Michael Kolbe, and Kailash Pandey. Structural basis to design multi-epitope vaccines against Novel Coronavirus 19 (COVID19) infection, the ongoing pandemic emergency: an in silico approach. bioRxiv, 2020.
Muhammad Tahir ul Qamar, Abdur Rehman, Usman Ali Ashfaq, Muhammad Qasim Awan, Israr Fatima, Farah Shahid, and Ling-Ling Chen. Designing of next generation multiepitope based vaccine (MEV) against SARS-COV-2: Immunoinformatics and in silico approaches. bioRxiv, 2020.
James Theiler and Bette Korber. Graph-based optimization of epitope coverage for vaccine antigen design. Statistics in Medicine, 37(2):181-194 2018.
Nora C Toussaint, Pierre Dönnes, and Oliver Kohlhacher. A mathematical framework for the selection of an optimal set of peptides for epitope-based vaceines. PLOS Computational Biology, 4(12): e1000246, 2008.
Yoya Vashi, Vipin Jagrit, and Sachin Kumar. Understanding the B and T cells epitopes of spike protein of severe respiratory syndrome coronavirus-2: A computational way to predict the immunogens. bioRxiv, 2020.
Qiong Wang. Ye Qiu, Jin- Yan Li, Zhi-Jian Zhou, Ce-Heng Liao, and Xing Yi Ge. A unique protease cleavage site predicted the spike protein of the novel pneumonia coronavirus (2019-ncov) potentially related to viral transmissibility. Virologica Sinica, pp. 1-3, 2020.
13

---

Published as a conference paper at ICLR 2022
Constantinos Kurt Wibmer, Frances Ayres, Tandile Hermanus, Mashudu Madzivhandila, Prudence Kgagudi, Brent Oosthuysen, Bronwen E. Lambson, Tulio de Oliveira, Marion Vermeulen, Karin van der Berg. Theresa Rossouw, Michael Boswell, Veronica Ueckermann, Susan Meiring, Anne von Gottherg, Cheryl Cohen, Lynn Morris, Jinal N. Bhiman, and Penny L.. Moore. SARS-CoV-2 501 Y.V2 escapes neutralization by South African COVID-19 donor plasma. Nature Medicine, 27 (4):622-625, 2021.
Margreet A Wolfert and Geert-Jan Boons. Adaptive immune activation: glycosylation does matter. Nature Chemical Biology, 912):776-784, 2013. doi: 10. 1..10088/eemmbo... 1403.
Haoyang Zeng and David Gifford. Quantification of uncertainty in peptide-MHC binding prediction improves high-affinity peptide selection for therapeutic design. Cell Systems, 9(2):159-166) 166, 2019.
14

---

Published as a conference paper at ICLR 2022
A PROOF THAT R-TIMES COVERAGE IS NOT SUBMODULAR
Theorem 2. The n-times coverage fincttin fo( is not submodular.
Proof. We show (O) is not submodular for 2 (a similar counter example can be found for any n > 1). Consider the example overlays A in Table S1 When 2 = 2, none of {A)))(A2)-{As) or {A2, A3} provides n-times coverage while {A,, A3) covers X₂ two times and {A1, covers X4 two times. Therefore, the marginal gain of adding A,, A2. or Aa into an empty set is always zero, whereas adding A into {A2} {Aa} achieves non-zero gains and adding A into (A2, As} achieves even higher gain:
(A(A)))) :- fn=2(1A)) - fR=2(0)
0
(y(Ail(A2) = [1= - (m=2((A2))
-w(X,) - -0= 0.48
(A(A))(aa) = (n=2({AI,Aa)) fn= (Aa)))
w((2)) 0 0.01
(y As)) = /n=2((A1 A2, As}) ) ((22 As))
w(X2) + w(1,)
0.49
Given that {Aa} C {A2, As} and (A()))(A3) < ( {A2, As)), the function fn= does satisfy the diminishing return property (Definition 2) and thus is not submodular.
Table S1: Coverage map of overlays used in the counter example.
((X))
0.01
0.01
0.5
0.48
X1
X2
X3
X4
A
0
1
0
1
A2
0
0
1
A3
1
1
0
0
Definition 2. (Submodularity) A function :V
IR is submodular for every A C B CVV and
e e e \ B it holds that (elAA) 2 (e)
Equivalently, f is submodular function if for every A. B.B & f(B).
B DETAILS OF VACCINE DESIGN
We score peptide-HI.A HI.A immunogenicity based upon clinical data from convalescent COVID-19 19 patients (Section 5). For peptide-HLA combinations not observed our clinical data we selected machine learning model of immunogenicity that best predicted the peptide-HLA combinations we did observe. Our selected MHC class model predicts peptide-HLA combination will be immunogenic if they are predicted to bind with an affinity of < 50 nM by the mean of the predictions from PUFFIN (Zeng Gifford 2019)) NetMHCpan-4.0 (Jurtz al. 2017) and MHCflurry 2.0 (O (O'Donnell et al. 2020). Our selected MHC class II model predicts immunogenic if they are predicted to bind with an affinity of < 50 nM by NetMHCIlppn-4.00
Heptide-HLA combination will be
Peptides of length 8-10 residues can bind to HLA class molecules whereas those of length 13-25 bind to HLA class molecules (Rist et al., 2013 Chiez et al.) 1992). We obtained the LARS-CoV-2
viral proteome from the first documented case from GISAID (Elbe & Buckland-Merrett 2017)
(sequence entry Wuhan/IPBCAMS. WH-01/2019). We applied sliding windows length 8-10 (MHC class 1) and 13-25 (MHC class II) to identify candidate peptides for inclusion in peptide vaccine. resulting in 29.403 candidate peptides for MHC class and 125,593 candidate peptides for MHC class II.
15

---

Published as a conference paper at ICLR 2022
Candidate peptide filtering. For our MARS-CoVAL peptide vaccine design, eliminate peptides that are expected to mutate and thus cause vaccine escape, peptides crossing cleavage sites, peptides that may be glycosylated, and peptides that are identical to peptides in the human proteome.
Removal of mutable peptides. We eliminate peptides that observed to mutate above input threshold rate (0.002) to improve coverage over all SARS-Co variants and reduce the chance that the virus will mutate and escape vaccine-induced immunity in the future. When possible, select peptides that are observed to be perfectly conserved across all observed SARS-CoV-2 viral genomes. Peptides that are observed be perfectly conserved in thousands of examples may be functionally constrained to evolve slowly or not at all.
For SARS-CoV-2, we obtained the most up date version of the GISAID database (Elbe & Buckland- Merrett, 2017) (as of 4:04pm EST February 4, 2021) and used Nextstrain (Hadfield et al.. [2018 to
remove genomes with sequencing errors, translate the genome into proteins, and perform multiple sequence alignments (MSAs). We retrieved 451,198 sequences from GISAID, and 426,072 remained after Nextstrain quality processing. After quality processing, Nextstrain randomly sampled 34 genomes from every geographic region and month to produce a representative set of 12,884 genomes for evolutionary analysis. Nextstrain definition of a "region" " can vary from a city (c.g.. "Shanghai") to larger geographical district. Spatial and temporal sampling in Nextstrain is designed to provide representative sampling of sequences around the world.
The 12,884 genomes sampled by Nextstrain were then translated into protein sequences and aligned. We eliminated viral genome sequences that had a stop codon, a gap, an unknown amino acid (because of uncalled nucleotide in the codon), had gene that lacked a starting methionine, except for ORFIb which does not begin with a methionine. This left total of 12,789 sequences that were used to compute peptide level mutation probabilities. For each peptide, the probability of mutation was computed as the number of non-reference peptide sequences observed divided by the total number of peptide sequences observed.
Removal of cleavage regions. SARS-CoV-2 contains a number of post-translation cleavage sites in ORFla la and ORFIb that result in a number of nonstructural protein products. Cleavage sites for ORF1a and ORFIb were obtained from UniProt (Consortium) 2019) under entry PODTDI. In addition, a furin-like cleavage site has been identified in the Spike protein (Wang et al. 2020 Coutard jet al. 2020). This cleavage occurs before peptides are loaded in the endoplasmic reticulum for class I or endosomes for class II. Any peptide that spans any of these cleavage sites is removed from consideration. This removes 3,887 peptides out of the 163,796 we consider across windows 8-10 (class 1) and 13-25 (class II) (~2.4%).
Removal of glycosylated peptides. Glycosylation is post-translationa modification that involves the covalent attachment of carbohydrates to specific motifs on the surface of the protein. We climinate all peptides that are predicted to have N-linked glycosylation as it can inhibit MHC class peptide loading and T cell recognition of peptides (Wolfert & Boons 2013). We identified peptides that may be glycosylated with the NetNGlye N-glycosylation prediction server (Gupta al. (004) and eliminated peptides where NetNGlyc predicted a non-zero N-glycosylation probability in any residue. This resulted in the elimination of 18,957 of the 154,996 peptides considered (~~ (~~12)).
Self-epitope removal. T cells are selected to ignore peptides derived from the normal human proteome, and thus we remove any self peptides from consideration for a vaccine. In addition, it possible that a vaccine might stimulate the adaptive immune system to react to a self peptide that was presented at an abnormally high level, which could lead to an autoimmune disorder. All peptides from SARS CoV-2 were scanned against the entire human proteome downloaded from UniProt (Consortium, 2019) under Proteome ID UP000005640. A total of 48 exact peptide matches (46 8-mers, two 9-mers) were discovered and eliminated from consideration.
Datasets.
(Liu et al.) 2020) software was obtained from GitHub /aEtps://qithu/ com http///fffooddoooo 1 ab/ opt i vax) and is available under an MIT license. Models and haplotype fre- quencies (Liu et al. 2020) were obtained from Mendeley Data /ttg://0000./00/00117177/
Opti
from GitHub commit wwwps/2200orroo00.0000..00000000
16

---

Published as a conference paper at ICLR 2022
cExkEy92p4. https://dei weceii.or//ii 2ttg//0.1763//s33222
and are available under
a Creative Commons Attribution 4.0 International license.
Computational resources. We utilized Google Cloud Platform machines with 224 CPU cores for MarginalGreedy optimization and parallelized computation across all CPU cores. For ILP designs, we used our own computing resources with 8 CPU cores. The prediction of peptide-HLa HLA binding with machine learning models (NetMHCpan, NetMHCIIpan, MHCfuurr, PUFFIN) was done using our own computing resources with 200 CPU cores and NVIDIA GeForce RTX 2080 Ti GPUs.
ILP solver. We use the Python-Mil solver (Santos & Toffolo 2020). which is well-maintained Mixed Integer Program (MIP) Solver with a Python API. Other solvers, such as the SCIP (Achterberg 2009) and the LMHS (Saikko al. 2016) solvers were considered, yet were deemed not be the best options for this problem, as they are optimized to solve more general problems than MIPs without any guarantees of better performance compared the Python-MIP solver.
Exp. # peptide- HLA bits / vaccine size
# poptide- HLA hits (White)
Esp. # peptide- hits (Black)
#
Vax- p(n 2 1)
EvalVax- Robust p(n 2 5)
EvalVax- Robust p(n 2 8)
poptide- hits
Vaccine Size
Peptide
(Asian)
MHC Class I Peptide Vaccine Evaluation
S Seprotein
3795
100.00%
99.43%
99.06%
40.183
38,212
38. 250
44.086
Jusuuuiit
2055
100.00%
99.05%
97.37%
20.788
20.616
20.397
21.351
OptiVax-Man SargaaaagnnnnGGroooygurrr
19
100.00%
98. 58%
87.97%
11.830
11.355
11.151
12.984
19
100.00 00%
98.52%
85.40%
11.164
10.883
10.430
12.180
Srivastava et al 2020
37
99 99.90%
80.06%
44.74%
7.163
7,533
7.018
6.938
Kandom subset binders
19
09%
67.00%
43.42%
7.131
7.308
6,229
7.796
Fast
2020
13
89. 69%660%
57.38%
30.55%
5,358
5,616
4.386
6.672
Jesilell 2020
52
97.76%
30.93%
13.50%
4.719
5.207
4.473
4.477
21720
13
75.78%
48%
20.60%
4.113
4.397
3.384
4.558
Ahmed cf
2020
16
73. 49%
26. 60%
9.29%
3.085
3.051
2 2.248
3.957
ell 2020
Abuelmugeed el
2020
79.09% 10
7.05%
0.11%
2,000
2.192
1.777
2,030
Barucah & Bose
2020
95.31%
6.39%
0.00%
2.365
3.128
2.031
2.537
38.91%
3.01%
0.00%
0,804
0.747
0.388
1.278
Singh et al.
A134
67. 87%
2.84%
0.00%
1.499
1.431
1.305
1.760
Vishi
51
84.86%
2.53%
0.00%
1.802
1.976
1.711
1.720
Poran 0t m
2120
10
72. 56%
0.81%
0.00%
1.355
0.997
1.383
1.686
KJian
A11hamn d1
2120
31
61 44%
0.04%
0.00%
0.840
1.062
0.774
0.682
1311115chr ya
2020
53.78%
0.00%
0.977
0.635
Sahaa Prased 2020
39.30%
0.00%
0.00%
0.423
0.496
0.291
0.482
Mitra et 20120)
33%
0.00%
0.00%
0.355
0.504
0.251
0.311
MHC Class 11 Peplide Vaccine Evaluation
Opti Max-MarginalGroodyyyou
19
99. 63%
96.75%
87.35%
14.017
16.989
14.375
10.686
protein
16315
99. 29%
96.53%
96.04%
395. 395.096
541.429
416.406
227.455
OptiVax. IIP(Ouur)
19
99.65%
94.22%.
83.76%
13.540
15.900
14.762
9.958
S1-subunit
8905
98.86%
91.87%
90.97%
177.838
265.183
175.613
92.717
Ramaiah & Arumugaswan 2020
131
98. 88%
90. 20.20%
83.97%
33. 7413
45.011
38 254
17.932
32.47%
Fast et al 2020)
86.99% 13
15.24%
3.69%
2.560
3.650
2.262
1.769
83.5
12.49%
2.398
3.2
2.354
1.679
Athand 2120
31
60.45%
9.22%
1.01%
1,856
2,531
2.536
0.591
Singh et al A034
56.29%
0.96%
0.00%
0.981
1.438
1.113
0.392
Abdelmagoel
2020
28.40%
0.90%
0.00%
0.274
0.244
Talir uf Vaind C[ 2020
72.75% 11
0.27%
0.00%
1.278
1,810
1.461
0.530
Vishi et ai
201241
20
12%
0.04%
0.00%
0.673
0.959
0.618
0.442
Porah ot A1210
69.37
0.00%
0.00%
0.983
1.409
0.910
0.569
2020
54.96%
0.00%
0.00%
0.654
0.736
0.717
0.510
Baruihh & Bosc
21120)
0.00%
0.00%
0.00%
0.000
0.000
0.000
0.000
Table S2: Comparison of cxisting basclines, S-protein peptides, and Opti -oobuuxx peptide vaccine designs on various population coverage evaluation metrics. The rows are sorted by SvalVVx-Robuul p(n 2 1). Random subsets generated 200 times. The binders used for generating random subsets are defined as peptides that are predicted to bind with < 50 nM to more than of the alleles.
17

---

Published as a conference paper at ICLR 2022
C EVALUATION OF OPTIVAX-ROBUST VACCINE DESIGN AND BASELINES WITH NON- WWWN--EPERMEETTALY-ALLBLRRRR MACHINE LEARNING
PREDICTIONS
We found that OPTI VAX produced vaccine designs superior to the baselines we tested even when used immunogenicity models that did not rely upon clinical data of peptide immunogenicity. Since our immunogenicity model used experimental data that was not accessible to the baseline methods, designs have advantage over baseline vaccines that did not use calibrated machine learning predictions. We repeated vaccine design using an ensemble of NetMHCpan-44.0 .. and MHCilurry with 50 nM predicted affinity cutoff for predicting MHC class immunogenictty and NetMHCIIpan-4. for MHC class II. As shown in Figure SS] Opti Vax-RRbbut again shows superior performance on all metrics all vaccine size under 35, indicating the success of MARGINAL.GEEDD in optimizing population coverage with diverse peptide display.
o4
Seacc OptiVax Besalines pio 13
MHC1 Dptiviic Revellnes
MeICI Optittex Baselinss x
MPICL Cptiria Baad (Ex #hita
Finilass
1.0
20-
6.8-
-5-
BP Aigikypp ant
Baiselling Antied
0.6
E-6
0.4-
0.4
sx sove
30
Outfeer aerom me meee pad
62-
Huge
0.0
0.0
60
32 Kurrber peptides
Rumber peptidles
Number pestides
Number poptides
191
MHCZ OptiMiic va deserimes pln 11
(8)
SHCC2 Optivas va musulinss at
MnCZ Optifricc va Baserimes pir 50 St
N09C2 OptiVies vs Dunsliies (Eap #hiba
1.0
Eiubfe Seioak 21
3-8-
Harginel vety
Ballyy
Exatita Robure
lavBor
U.B-
0.4
Aysion
0.2
0.0
20
30
10
20
40
15
30
30
40
10
Number of papticie
of peptilis
Number of post
Mumber pestides
Figure S1: Eval Vax population coverage evaluation of SARS-CoV-2 vaccines for (top) MHC class I
and (bottom) MHC class II using non-experimentally calibrated machine learning predictions. (a)
Vax -ox-Ro population coverage with n 2 peptide-HI.AA hits per individual, performances of 3 variants of Opti Vax are shown by curves and baseline performance is shown by red crosses (labeled by name of first author). (b) Eval Vax-Robust population coverage with n 2 5 peptide-Hl. HLA hits. (c)
EvalVax Daal-ax-Robur Robust population coverage with n 2 8 peptide- HLA hits. (d) Comparison of OptiVax and baselines expected number of peptide-HLA. HLA hits.
D ADDITIONAL EXPERIMENTS ON A DATASET WITH UNEQUAL WEIGHTS AND SPARSE COVERAGE
We further expanded our evaluation to include a hill climbing based method and a more complex dataset. We generated a dataset named LARGE with sparse overlay coverage and unequal element weights to provide further basis of comparison for n-times coverage methods. The LARGE dataset was created by generating a set of 30 overlays to cover a set of 10 elements with unequal weights, and the probability of covering an element 0, 1, times is 0.6, 0.3, and 0.1, respectively. We added an additional baseline method using hill climbing with random restarts for comparison with other methods. For hill climbing we used stochastic local search that queries a randomly selected subset of neighbors (Algorithm 2). We used stochastic local search because for solution size of k. a single exhaustive local search step requires querying all possible solutions that are 1 peptide different from the current solution, which may result in k # total the oracle that computes n-times population coverage. This approach is too expensive in typical vaccine design problems with thousands of candidate peptides. For a fair comparison we have set the number of restarts and hill climbing steps such that the total number of oracle queries needed to build hill climbing solution of size l is equivalent to that of MarginalGreedy Figure S2 shows that hill climbing is effective when the solution size is small, and but fails to reach 100% coverage when MarginalGreedy reaches 100% coverage. MarginalGreedy and True Optimal reach 100% coverage
poaddddte__ppttiee queries to
18

---

Published as a conference paper at ICLR 2022
with approximately the same number of overlays. Our integer programming n-times coverage formulation achieves exact true optimal results on the LARGE dataset.
Maximum n times coverage(LARGE, sparse and unequally weighted,n=6)
1.0
method
ILP(Ours)
MargiGreedy(Ours)
0.8
HillClimb restart=3
n-times coverage
HillCimb--rettart>
0.6
Greedy
Random subset
True Optimal
0.4
0.2
0.0
2
8
10
12
14
Num. overlays used
Figure $2: Comparison of n-times coverage methods on the LARGE dataset that includes hill
climbing (Algorithm 2). The LARGE dataset contains unequal element weights and sparse coverage.
Algorithm 2 HILLCLIMB algorithm (in MAXIMUM R-TIMES COVERAGE with cardinality constraint)
Input: Weights of the elements in X X'w((X,), (Xx)), ..... w(X)), ground set of overlays A where each overlay j in A covers X; for ej (X;) times, cardinality constraint k, target minimum # times being covered reterget number of restarts M, number of hill climbing steps T, number of neighbors considered in one hill climb step N. Initialize solution set = /
Using Rttarge times coverage function f(O) = Em w(X,) (EE 2 as objective.
for m = 1, M do
Randomly select a set of overlays from as starting solution O", compute Thest = f(00) as the best coverage far. for step = 1, ,,...,7 do Randomly pick overlay from O' candidate be replaced Randomly select N overlays from currently unselected set N C A \ for a' V do if f(O {a} (d')) > Thest then 0" 0 fa} (a')
LLoop over the selected neighbors
Replace the overlay with a better one
Thest + f(00)
S - (0
Add the best solution current run into solution pool > Use the best result as final solution
O= = arg max f(O) Output: The final selected subset of overlays O*
HIGH-RESSOLUTION FIGURES FOR VACCINE MHC HITS
19

---

Published as a conference paper at ICLR 2022
OptiVax- votiVax-MargiGrenn MargiGreedy(Ours) _MHM1 peptides predicted binding <50nM
HLA-A
HLA-A
OptiVax-ILP(Ours) MHC1
Figure S3: High-resoluton MHC class I binding plats from oo Temme
peptides predicted binding <50nM
HLA-B
HLA-B
HLA-C
HLA-C
20


Reviews:
[{"review_id": "tjqo0WG4Pe", "reviewer": "Reviewer_Z6bA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem that they introduce and the solution are natural. I would say this part of the paper is interesting but unsurprising. Such generalizations are common and the tricks that this paper employes are not unusual. Still, it's a good contribution.\n\nThe stronger contribution in my view is the observation that this problem helps in the COVID vaccine design pipeline. I'm far from being an expert on this, so I'm not confident in my assessment, but it seems strong.\n\n\n\n", "summary_of_the_paper": "This paper suggest the n-times coverage problem (a natural generalization of set-cover where items need to be covered n>1 times by the sets we choose) and motivates it with an application for the design of COVID vaccines. This application involves some ML pipeline, and this new combinatorial optimization problem helps with one of the steps.\n\nThe problem is shown to be not-submodular, and therefore the most standard methods don't quite work. Nonetheless, the authors present a greedy algorithm to get a reasonable approximation.\n\nThe paper evaluates the quality of their algorithm on artificial data and shows that it outperforms the more standard greedy method. Then they show the impact of this improvement for vaccine design.", "summary_of_the_review": "This is a nice paper with good contribution for the (ML based) pipeline for COVID vaccine design.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "tRPouczD-pt", "reviewer": "Reviewer_csaP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As far as algorithms are concerned, the greedy approach is standard for set-covering type problems, even though it seems that it has not been used for this particular set covering version before. Most of the ILP formulation seems standard as well, however, it is not clear how the objective function may be linearized and this requires additional work and Big-M-constraints.\n\nThe vaccine design process seems sound, building on published work. Experimental results show that the ILP comes close close to the optimum solution. Finally, the resulting vaccine designs are succcessfully compared to designs from the literature.\n\nAs a minor comment, I did not fully understand the pseudo-code for the beam search: Initally, B^0 is empty, so the beam search (outer for-loop) iterates over an empty set and will not build a candidate set. Wouldn't then B^{t+1} be empty as well?", "summary_of_the_paper": "The submission is concerned with vaccine design and proposes to model the task as a combinatorial optimization problem that is essentially a generalization of set cover. The authors describe two algorithms: A marginally greedy algorithm using beam search and a mixed integer linear programming approach.\n\nMore precisely, the combinatorial problem consists in covering weighted elements (the population) with overlays (peptides) while maximizing the total weight of those elements that are covered at least n times. Each overlay may only be used once, but may cover the same element multiple times. In total, no more than k overlays may be chosen.\n\nAdditionally, the submission features a machine learning based tool that predicts the effectiveness of the designed vaccine.", "summary_of_the_review": "The submission is built with a clear application in mind. It provides two reasonable approaches for a well-modeled problem. There are little theoretical contributions, but I found the practical contribution well-executed and convincing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jW6VZepM0w", "reviewer": "Reviewer_Hy3s", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The novelty of the proposed work is limited. A large number of existing approaches have formulated element-based vaccine design as a discrete optimization problem (e.g., [Malone et al., Scientific Reports 2020], [Theiler and Korder, Statistics in Medicine 2018], [Schulber and Kohlbacher, Genome Medicine 2016], [Oyarzun and Kobe, International Journal of Immunogenetics 2015], [Lundegaard et al., Proceedings of the $1^{st}$ ACM International Conference on Bioinformatics and Computational Biology 2010], [Toussaint et al., PLOS Computational Biology 2008]). While the proposed approach may have advantages compared to those formulations, the authors do not provide any context of how their formulation differs from the well-established approaches. So it is difficult to gauge the novelty of the proposed approach with respect to current approaches.\n\nIn terms of technical soundness, the theoretical contributions seem sound. I did not thoroughly verify the proofs of NP-completeness, but the argument seems sound. The greedy algorithm for addressing the optimization problem does not have any associated guarantees, but it also seems reasonable.\n\nIn terms of biology, the formulation is not very meaningful. For example, MHC (HLA in human) I leads to an entirely different immune response than MHC II (cytotoxic/cell killing for MHC I compared to recruiting various other immune cells for MHC II). A good T-cell vaccine should do both. Additionally, some haplotypes are more common than others, and the proposed approach ignores such pair-wise correlations. Thus, while it is clear that the formulated problem lends itself well to a set covering formulation, it is not clear to me that this formulation is meaningful.\n\nConsidering the experimental results, some obvious baselines are missing. For example, a greedy hill climbing with random restarts approach is a typical way to approach such discrete optimization problems, so it would be useful to show how much the proposed margin-based algorithm outperforms that. Further, since the exact solution to the problem can be formulated as an ILP, modern anytime solvers (which also offer guaranteed bounds), such as SCIP [Achterberg, Mathematical Programming Computation 2009] or LMHS [Saikko et al., SAT 2016], should be included in the comparison.\n\nThe paper is generally clear and well written. The references are inconsistently formatted. It would be helpful to increase the font size on the figures.\n\nThe reproducibility and provided resources of this work are in line with the field. An expert would likely be able to take the formulations in the paper and turn them into code.", "summary_of_the_paper": "Update: I have read the author feedback and other reviews. Based on the more detailed comparison to existing methods, I have updated several of my scores.\n\n---\n\nIn this work, the authors propose a variant of the set covering problem which aim to formalize peptide-based vaccine design as an optimization problem. The authors first formulate the problem and then draw connections to other set covering problems; they then show that the problem is NP-complete. They then propose a greedy algorithm to perform the optimization. A set of experiments suggests the proposed approach outperforms the formulations considered by the authors.", "summary_of_the_review": "Considering the lack of theoretical novelty and biological accuracy, it is difficult for me to see the impact of the work as it is currently presented.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Zer4K1Trdb7", "reviewer": "Reviewer_4qAy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The new problem appears to be interesting. I am not aware of a problem with such a structure, although I would not be surprised if there were previous studies on this framework in the area of combinatorial design or also in one of the several variants of group testing.  \nThe experimental evaluation of the approach in on a currently hype area is also valuable. \nThere are a couple of concerns I have: \n- the pseudocode for algorithm 1 is not clear to me. It seems that the two inner for loop will always end up constructing K^t = A.\n- in the empirical study on the toy examples, the weights are not used, which is strange since it is what makes the problem different from the  classical variants of set cover. It is also not clear to me from the description where the weights enter in the evaluations of the design for covid 19. The authors only mention coverage and it is not clear whether that is meant in terms of sum of weights or what else. \nDue to these concerns I am not giving a fully acceptance to the paper but I am willing to receonsider my score on the basis of the authors' reply.\n\nMinor problems: the figures are very small and it is very difficult to appreaciate on paper what they show. ", "summary_of_the_paper": "The paper introduces a variant/generalization of multi set multi cover problem, where the aim is to maximize the weight of the elements covered at least n times by up to k overlays (subsets of a given input familiy of sets over the elements' universe). The authors show that the objective function is not submodular, hence does not admit a classical greedy approach. They show an ILP formulation that provides an optimal solution but not efficiently. They propose a greedy approach based on maiximization of marginal gains endowed with a look-ahead tie breaking that should prevent failure to attain n-coverage because of wrong initial choices guided by the sole marginal gain maximization objective. \nThe problem is meant to model vaccine design and show empirical evaluation on two toy data sets and presenting comparisons between the greedy approach and the ILP approach for a covid 19 vaccine. ", "summary_of_the_review": "Strenght: The paper offers an interesting and apparently unexplored variant of set cover that can model a vaccin design problem. The evaluation seem to show good performance. \nWeaknesses: there seems to be something unclear in the pseudocode of the greedy algorithm that prevents me from fully assess its behaviour; the importance of the weights in the experiments is not clearly discussed (without this, the problem reduces to known Multi-set multi cover)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces the maximum n-times coverage, a new NP-hard (and non-submodular) optimization problem. It is shown that the problem can naturally arise in ML-based vaccine design, and two heuristics are given to solve the problem. The results are used to produce a pan-strain COVID vaccine. 

The reviewers and I think that this is an interesting paper with a compelling application. There were some concerns about theoretical novelty and biological accuracy but these were addressed during the author response period. Given this, I am delighted to recommend acceptance. Please incorporate the feedback in the reviews in the final version of the paper.
Decision: Accept (Poster)