Systems and methods that utilize machine learning algorithms to facilitate assembly of aids vaccine cocktails

• US 8,478,535 B2
• Filed: 12/30/2005
• Issued: 07/02/2013
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jojic, Nebojsa, Heckerman, David E., Frey, Brendan John, Meek, Christopher A., Jojic, Vladimir
• Primary Examiner(s): SIMS, JASON M
• Application Number:
  US11/324,506
• Publication Number:
  US 20060178861A1
• Time in Patent Office: 2,741 Days
• Field of Search: None
• US Class Current: 702/19
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G16B 10/00 ICT specially adapted for evolutionary bioinformatics, e.g. phylogenetic tree construction or analysis
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/30 Detection of binding sites or motifs
• CPC Class Codes: G16B 20/50 Mutagenesis
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis
• CPC Class Codes: G16B 40/30 Unsupervised data analysis

Abstract

The subject invention provides systems and methods that facilitate AIDS vaccine cocktail assembly via machine learning algorithms such as a cost function, a greedy algorithm, an expectation-maximization (EM) algorithm, etc. Such assembly can be utilized to generate vaccine cocktails for species of pathogens that evolve quickly under immune pressure of the host. For example, the systems and methods of the subject invention can be utilized to facilitate design of T cell vaccines for pathogens such HIV. In addition, the systems and methods of the subject invention can be utilized in connection with other applications, such as, for example, sequence alignment, motif discovery, classification, and recombination hot spot detection. The novel techniques described herein can provide for improvements over traditional approaches to designing vaccines by constructing vaccine cocktails with higher epitope coverage, for example, in comparison with cocktails of consensi, tree nodes and random strains from data.

Claims

1. A system that facilitates determining an epitome that provides a basis for a vaccine cocktail, comprising:

a processing unit;

a system memory coupled to the processing unit;

an input component that receives a plurality of overlapping patches x_S corresponding to a set of subsequences from one or more pathogen sequences in a population; and

a modeling engine that employs one or more machine learning algorithms to determine an epitome based on the plurality of overlapping patches x_S, the epitome providing the basis for the vaccine cocktail, wherein the one or more machine learning algorithms comprises an expectation-maximization (EM) algorithm that includes an initial random guess for the epitome and iteratively reduces a free energy of the epitome converging to a local minimum of free energy, wherein the free energy combines T cell binding energy and HLA binding via a variational mapping distribution of respective ones of the plurality of overlapping patches x_S to the epitome.

2. The system of claim 1, wherein the plurality of overlapping patches are pathogen subsequences assembled to generate representative sequences of a category.

3. The system of claim 2, wherein the category comprises at least one of sequences associated with a specific species, sequences associated with a specific clade, sequences associated with an acute phase of infection, or sequences associated with a chronic phase of infection.

4. The system of claim 2, wherein the category comprises HIV.

5. The system of claim 1, wherein at least one of the pathogen subsequences relates to an epitope.

6. The system of claim 1, wherein at least one of the pathogen subsequences comprises an epitope.

7. The system of claim 1, wherein the plurality of overlapping patches comprise short subsequences, at least one of which contains an unknown epitope having a non-zero probability of being presented on a surface of an infected cell.

8. The system of claim 1, wherein at least one of the one or more machine learning algorithms determines an epitome that minimizes an energy needed to mount an effective immune response as determined by a cost function.

9. The system of claim 8, wherein the cost function determines a minimum total energy for a given length of the epitome.

10. The system of claim 1, wherein at least one of the one or more machine learning algorithms minimizes the length of the epitome, the minimization subject to the constraint that the resulting epitome has a cost less than or equal to a given cost.

11. The system of claim 9, wherein the total energy is based at least in part on the free energy.

12. The system of claim 1, wherein the free energy is calculated according to at least one of:

a frequency of occurrence of one of the plurality of overlapping patches x_S in the population;

a probability that one of the plurality of overlapping patches x_S is found in a single strain of the population;

a probability of occurrence of one of the plurality of overlapping patches x_S in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of one of the plurality of overlapping patches x_S and whether one of the plurality of overlapping patches x_S contains a known epitope;

a probability that one of the plurality of overlapping patches x_S is an epitope;

a probability that one of the plurality of overlapping patches x_S will be presented by a cell;

or

a probability that an individual vaccinated with one of the plurality of overlapping patches x_S will mount an immune response.

13. The system of claim 11, wherein the free energy is calculated according to at least one of:

a frequency of occurrence of one of the plurality of overlapping patches x_S in the population;

a probability that one of the plurality of overlapping patches x_S is found in a single strain of the population;

a probability of occurrence of one of the plurality of overlapping patches x_S in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of one of the plurality of overlapping patches x_S and whether one of the plurality of overlapping patches x_S contains a known epitope;

a probability that one of the plurality of overlapping patches x_S is an epitope;

a probability that one of the plurality of overlapping patches x_S will be presented by a cell;

or

a probability that an individual vaccinated with one of the plurality of overlapping patches x_S will mount an immune response.

14. The system of claim 8, wherein the cost function measures an inverse similarity of the plurality of overlapping patches with an estimate of the epitome.

15. The system of claim 9, wherein the cost function measures an inverse similarity of the plurality of overlapping patches with an estimate of the epitome.

16. The system of claim 10, wherein the cost function measures an inverse similarity of the plurality of overlapping patches with an estimate of the epitome.

17. The system of claim 8, wherein the cost function is determined according to a hamming distance of less than a fixed integer.

18. The system of claim 8, wherein the cost function is determined according to a probability of one of the plurality of overlapping patches x_S given a patch e_T of the epitome.

19. The system of claim 8, wherein the cost function is determined according to a probability density function of one of the plurality of overlapping patches x_S given a patch e_T of the epitome.

20. The system of claim 8, wherein the cost function comprises an expected fraction of the plurality of overlapping patches relating to one or more strains of the population and wherein expectation is taken over the probability that a patch contains an epitope.

21. The system of claim 9, wherein the cost function comprises an expected fraction of the plurality of overlapping patches relating to one or more strains of the population and wherein expectation is taken over the probability that a patch contains an epitope.

22. The system of claim 8, wherein the cost function between one of the plurality of overlapping patches x_S and a patch e_T of the epitome is an exponential of a binding energy reflecting the binding of a T-cell primed with one peptide to another peptide.

23. The system of claim 1, the plurality of overlapping patches comprising variable length peptides.

24. The system of claim 1, further comprising an intelligence component to optimize the epitome based on inferences.

25. The system of claim 1, wherein the one or more machine learning algorithms model sequence diversity for the pathogen sequences in the population.

26. The system of claim 1, wherein the epitome is an AIDS vaccine cocktail.

27. The system of claim 1, wherein the one or more machine learning algorithms optimize the epitome by maximizing a number of short subsequences that are present in the plurality of overlapping patches.

28. The system of claim 1, wherein the pathogen sequences are peptides and a length of at least one patch is about 8-11 amino acids.

29. The system of claim 1, wherein the free energy is a negative log-probability of an event.

42. The system of claim 9, wherein the cost function measures an inverse similarity of the plurality of overlapping patches x_S with an estimate of the epitome.

44. The system of claim 1, wherein the free energy is calculated according to:

a frequency of occurrence of one of the plurality of overlapping patches x_S in the population;

a probability that one of the plurality of overlapping patches x_S is found in a single strain of the population;

a probability of occurrence of one of the plurality of patches x_S in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of one of the plurality of overlapping patches x_S and whether one of the plurality of patches x_S contains a known epitope;

a probability that one of the plurality of overlapping patches x_S is an epitope;

a probability that one of the plurality of overlapping patches x_S will be presented by a cell; and

a probability that an individual vaccinated with one of the plurality of overlapping patches x_S will mount an immune response.

45. The system of claim 11, wherein the free energy is calculated according to:

a frequency of occurrence of one of the plurality of overlapping patches x_S in the population;

a probability that one of the plurality of overlapping patches x_S is found in a single strain of the population;

a probability of occurrence of one of the plurality of overlapping patches x_S in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of one of the plurality of overlapping patches x_S and whether one of the plurality of overlapping patches x_S contains a known epitope;

a probability that one of the plurality of overlapping patches x_S is an epitope;

a probability that one of the plurality of overlapping patches x_S will be presented by a cell; and

a probability that an individual vaccinated with one of the plurality of overlapping patches x_S will mount an immune response.

47. The system of claim 1, wherein the free energy F is defined as:

30. Computer-executable instructions for performing a computer-implemented method to determine an epitome to facilitate vaccine design, the computer-executable instructions stored on computer-readable media, the computer-implemented method comprising:

receiving a plurality of patches to one or more learning algorithms;

determining an epitome based on the plurality of patches by employing an expectation-maximization (EM) algorithm that includes an initial sequence for the epitome and iteratively reduces a free energy of the epitome converging to a local minimum of free energy, wherein the free energy combines T cell binding energy and HLA binding via a variational mapping distribution of respective ones of the plurality of patches to the epitome;

matching a portion of the epitome to at least one region of at least one patch by moving a window over the epitome and matching the portion of the epitome included in the window to the at least one region of the at least one patch; and

utilizing the epitome to design a vaccine.

31. The method of claim 30, wherein the vaccine is an AIDS vaccine.

32. The method of claim 30 , further comprising parsing at least one of the patches into shorter sequences of epitope length and creating a mosaic sequence that is longer than any of the shorter sequences.

33. The method of claim 30, wherein the epitome is a mosaic sequence with a length greater than a length of any individual patch, but less than a sum of all patch lengths.

34. The method of claim 30, wherein the EM algorithm is initialized with a large variability estimate for binding energy parameters relative to the binding energy parameters after several iterations of the EM algorithm.

35. The method of claim 30, further comprising packing patches of a defined length into the epitome.

36. The method of claim 31, wherein the epitome is an HIV vaccine cocktail.

37. The method of claim 30, further comprising optimizing the epitome by maximizing a number of short subsequences that are present in the plurality of patches.

43. The method of claim 30, wherein the free energy is calculated according to at least one of:

a frequency of occurrence of a patch in the population;

a probability that patch is found in a single strain of the population;

a probability of occurrence of patch in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of patch and whether patch contains a known epitope;

a probability that patch is an epitope;

a probability that patch will be presented by a cell;

or

a probability that an individual vaccinated with patch will mount an immune response.

46. The method of claim 30, wherein the free energy is calculated according to:

a frequency of occurrence of a patch in the population;

a probability that patch is found in a single strain of the population;

a probability of occurrence of patch in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of patch and whether patch contains a known epitope;

a probability that patch is an epitope;

a probability that patch will be presented by a cell; and

a probability that an individual vaccinated with patch will mount an immune response.

38. A system that facilitates identifying an epitome for generating AIDS vaccine cocktails, comprising:

a processing unit;

a system memory coupled to the processing unit;

an input component configured to receive a plurality of overlapping patches having sequences and store at least a subset of the plurality of overlapping patches in the system memory; and

a machine learning component configured to employ machine learning to model sequence diversity for identifying an epitome to facilitate AIDS vaccine cocktail assembly, wherein the machine learning component comprises;

a cost function that accounts for acts that are needed to mount an effective immune response; and

an expectation-maximization (EM) algorithm that includes an initial random guess for the epitome and iteratively reduces a free energy of the epitome converging to a local minimum of free energy, wherein the free energy combines T cell binding energy and HLA binding via a variational mapping distribution of respective ones of the plurality of overlapping patches to the epitome.

39. The system of claim 38, wherein the EM algorithm is initialized with a large variability estimate for binding energy parameters relative to the binding energy parameters after several iterations of the EM algorithm.

40. The system of claim 38, wherein the cost function is determined according to a hamming distance of less than a fixed integer.

41. The system of claim 38, wherein the free energy is calculated according to at least one of:

a frequency of occurrence of one of the plurality of overlapping patches in the population;

a probability that one of the plurality of overlapping patches is found in a single strain of the population;

a probability of occurrence of one of the plurality of overlapping patches in a population wherein the sequencing data is ambiguous;

a value that reflects both the frequency of one of the plurality of overlapping patches and whether one of the plurality of overlapping patches contains a known epitope;

a probability that one of the plurality of overlapping patches is an epitope;

a probability that one of the plurality of overlapping patches will be presented by a cell;

or

a probability that an individual vaccinated with one of the plurality of overlapping patches will mount an immune response.