title: A combinatorial approach to the design of vaccines.
abstract: We present two new problems of combinatorial optimization and discuss their applications to the computational design of vaccines. In the shortest λ-superstring problem, given a family S1,...,S(k) of strings over a finite alphabet, a set Τ of "target" strings over that alphabet, and an integer λ, the task is to find a string of minimum length containing, for each i, at least λ target strings as substrings of S(i). In the shortest λ-cover superstring problem, given a collection X1,...,X(n) of finite sets of strings over a finite alphabet and an integer λ, the task is to find a string of minimum length containing, for each i, at least λ elements of X(i) as substrings. The two problems are polynomially equivalent, and the shortest λ-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 λ-superstring and λ-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.
authors.affiliation: Department of Mathematics, University of the Basque Country UPV/EHU, 48080 , Bilbao, Spain, luis.martinez@ehu.es.
authors.forename: Luis
authors.initials: L
authors.lastname: Martínez
authors.forename: Martin
authors.initials: M
authors.lastname: Milanič
authors.forename: Leire
authors.initials: L
authors.lastname: Legarreta
authors.forename: Paul
authors.initials: P
authors.lastname: Medvedev
authors.forename: Iker
authors.initials: I
authors.lastname: Malaina
authors.forename: Ildefonso M
authors.initials: IM
authors.lastname: de la Fuente
mesh_terms: D016915:AIDS Vaccines / Q000737:chemistry / Q000235:genetics / Q000276:immunology; D000465:Algorithms; D000595:Amino Acid Sequence; D020650:Combinatorial Chemistry Techniques; D019295:Computational Biology; D015195:Drug Design; D000939:Epitopes / Q000235:genetics; D015497:HIV-1 / Q000235:genetics / Q000276:immunology; D006801:Humans; D053124:Influenza A Virus, H5N1 Subtype / Q000235:genetics / Q000276:immunology; D007252:Influenza Vaccines / Q000737:chemistry / Q000235:genetics / Q000276:immunology; D055641:Mathematical Concepts; D018448:Models, Immunological; D008969:Molecular Sequence Data; D014765:Viral Vaccines / Q000737:chemistry* / Q000235:genetics / Q000276:immunology
chemical_list: D016915:AIDS Vaccines; D000939:Epitopes; D007252:Influenza Vaccines; D014765:Viral Vaccines