A combinatorial approach to the design of vaccines

Luis Martínez, Martin Milanič, Leire Legarreta, Paul Medvedev, Iker Malaina, Ildefonso M. de la Fuente

We present two new problems of combinatorial optimization and discuss their applications to the computational design of vaccines. In the shortest [Formula: see text]-superstring problem, given a family [Formula: see text] of strings over a finite alphabet, a set [Formula: see text] of "target" strings over that alphabet, and an integer [Formula: see text], the task is to find a string of minimum length containing, for each [Formula: see text], at least [Formula: see text] target strings as substrings of [Formula: see text]. In the shortest [Formula: see text]-cover superstring problem, given a collection [Formula: see text] of finite sets of strings over a finite alphabet and an integer [Formula: see text], the task is to find a string of minimum length containing, for each [Formula: see text], at least [Formula: see text] elements of [Formula: see text] as substrings. The two problems are polynomially equivalent, and the shortest [Formula: see text]-cover superstring problem is a common generalization of two well known combinatorial optimization problems, the shortest common superstring problem and the set cover problem. We present two approaches to obtain exact or approximate solutions to the shortest [Formula: see text]-superstring and [Formula: see text]-cover superstring problems: one based on integer programming, and a hill-climbing algorithm. An application is given to the computational design of vaccines and the algorithms are applied to experimental data taken from patients infected by H5N1 and HIV-1.