Peptide Vaccine Design by Evolutionary Multi-Objective Optimization

Dan-Xuan Liu, Yi-Heng Xu, Chao Qian

Abstract

Peptide vaccines are growing in significance for fighting diverse diseases. Machine learning has improved the identification of peptides that can trigger immune responses, and the main challenge of peptide vaccine design now lies in selecting an effective subset of peptides due to the allelic diversity among individuals. Previous works mainly formulated this task as a constrained optimization problem, aiming to maximize the expected number of peptide-Major Histocompatibility Complex (peptide-MHC) bindings across a broad range of populations by selecting a subset of diverse peptides with limited size; and employed a greedy algorithm, whose performance, however, may be limited due to the greedy nature. In this paper, we propose a new framework PVD-EMO based on Evolutionary Multi-objective Optimization, which reformulates Peptide Vaccine Design as a bi-objective optimization problem that maximizes the expected number of peptide-MHC bindings and minimizes the number of selected peptides simultaneously, and employs a Multi-Objective Evolutionary Algorithm (MOEA) to solve it. We also incorporate warm-start and repair strategies into MOEAs to improve efficiency and performance. We prove that the warm-start strategy ensures that PVD-EMO maintains the same worst-case approximation guarantee as the previous greedy algorithm, and meanwhile, the EMO framework can help avoid local optima. Experiments on a peptide vaccine design for COVID-19, caused by the SARS-CoV-2 virus, demonstrate the superiority of PVD-EMO.

Introduction

Peptide vaccines trigger the immune system by introducing short amino acid chains that help T-cells recognize pathogens. A critical hurdle in vaccine design is the variability of the Major Histocompatibility Complex (MHC) across the human population. Since MHC molecules present peptides to T-cells, a peptide effective for one individual might be ineffective for another. Consequently, the goal is to select a small, diverse subset of peptides that maximizes immune response coverage across a broad population.

Traditional methods like the Optivax-P algorithm utilize a greedy approach, selecting peptides one by one. While efficient, greedy algorithms often settle for local optima, missing globally superior solutions. This paper introduces PVD-EMO, a framework that leverages Multi-Objective Evolutionary Optimization to overcome these limitations.

The PVD-EMO Framework

PVD-EMO reformulates the selection process as a bi-objective problem: maximizing the expected number of peptide-MHC bindings while simultaneously minimizing the total number of selected peptides. This "multi-objectivization" allows the algorithm to maintain a diverse set of candidate solutions, facilitating the escape from local optima.

To enhance performance, the authors integrated three key strategies:

  1. Warm-Start Strategy: The initial population is seeded with the greedy algorithm's solution, ensuring the evolutionary process starts from a high-quality baseline and theoretically guaranteeing it will not perform worse than the greedy method.
  2. Repair Strategy: To handle pairwise constraints (e.g., avoiding overly similar peptides), a repair mechanism intelligently adjusts infeasible solutions generated during mutation.
  3. Acceleration Strategy: A recursive update method reduces the computational complexity of objective function evaluation from $O(k^3)$ to $O(k)$, significantly speeding up the optimization process.

Experimental Evaluation

The framework was tested on a SARS-CoV-2 dataset containing 1,043 candidate peptides and over a million MHC-I genotypes. Binding probabilities were predicted using NetMHCpan.

Comparison of objective value convergence for various PVD-EMO configurations against the Optivax-P baseline.

As shown in the convergence plots, the PVD-GSEMO-WR variant (incorporating both Warm-start and Repair) quickly surpasses the Optivax-P baseline. The "Repair" strategy proved essential; without it, the algorithm struggled to navigate the complex constraint landscape.

Improvement in objective value over the Optivax-P baseline for different peptide budget sizes ($k$).

Further analysis reveals that the performance gap between PVD-EMO and Optivax-P widens as the peptide budget ($k$) increases. This demonstrates the framework's ability to find increasingly better solutions compared to greedy methods in larger search spaces.

Conclusion

PVD-EMO represents a significant advancement in peptide vaccine design. By combining evolutionary exploration with theoretical guarantees from greedy initialization, it consistently outperforms existing state-of-the-art methods. Future work will focus on further accelerating the search process and applying the framework to other diseases with high allelic diversity, such as HIV and cancer.

Summary updated

Abstract

Peptide vaccines are growing in significance for fighting diverse diseases. Machine learning has improved the identification of peptides that can trigger immune responses, and the main challenge of peptide vaccine design now lies in selecting an effective subset of peptides due to the allelic diversity among individuals. Previous works mainly formulated this task as a constrained optimization problem, aiming to maximize the expected number of peptide-Major Histocompatibility Complex (peptide-MHC) bindings across a broad range of populations by selecting a subset of diverse peptides with limited size; and employed a greedy algorithm, whose performance, however, may be limited due to the greedy nature. In this paper, we propose a new framework PVD-EMO based on Evolutionary Multi-objective Optimization, which reformulates Peptide Vaccine Design as a bi-objective optimization problem that maximizes the expected number of peptide-MHC bindings and minimizes the number of selected peptides simultaneously, and employs a Multi-Objective Evolutionary Algorithm (MOEA) to solve it. We also incorporate warm-start and repair strategies into MOEAs to improve efficiency and performance. We prove that the warm-start strategy ensures that PVD-EMO maintains the same worst-case approximation guarantee as the previous greedy algorithm, and meanwhile, the EMO framework can help avoid local optima. Experiments on a peptide vaccine design for COVID-19, caused by the SARS-CoV-2 virus, demonstrate the superiority of PVD-EMO.
BibTeX
@inproceedings{liu2024peptide,
  author = {Dan-Xuan Liu and Yi-Heng Xu and Chao Qian},
  title = {{Peptide Vaccine Design by Evolutionary Multi-Objective Optimization}},
  booktitle = {AIforCI @ IJCAI},
  year = {2024},
  url = {https://openreview.net/forum?id=Sm5zG3e62I},
}
Figure