Algorithms for rational vaccine design

Design of an HIV vaccine has proven to be a difficult challenge. Vaccines designed by the traditional approach based on using a single weakened virus or a portion of a virus have not provided sufficient protection. The large variability of the HIV virus population is believed to be the main cause of failure for the vaccine candidates. In this thesis, I introduce an immunologically motivated vaccine score which accounts for the variability of the target HIV population. The exact optimization of this score is an NP-hard problem. I introduce algorithms, both approximate methods are approximate and exact, for designing a high scoring vaccine. The approximate methods are based on expectation maximization methods and use approximate probabilistic inference. The exact method is based on a branch-and-cut method for the asymmetric orienteering problem. The score and the algorithms for maximizing the score are validated both in-silico and in-vitro. In-silico comparisons are made to other methods aimed at overcoming HIV variability. The in-vitro Elispot experiments demonstrate an expected protection in ∼ 90% of infections.