Transcript Applications of Game Theory in the Computational Biology Domain

Applications of Game Theory
in the Computational Biology
Domain
Richard Pelikan
April 16, 2008
CS 3110
Overview
• The evolution of populations
• Understanding mechanisms for disease
and regulatory processes
– Models of cancer development
– Protein and drug interactions, resource
competition
• Many biological processes can be tied to
game theory
Evolution
• Difficult process to describe
• Game theory seen as a way of formally
modeling natural selection
Evolutionary Game Theory
• Evolution revolves around a fitness
function
– Fitness function is often unknown
– Frequency based, success is measured
primitively by number present.
– Strategies exist because of this function
– Difficult to define the entire game with just the
strategy.
Prisoner’s Dilemma
• Earlier in the course, we knew just about
everything about the game
Prisoner A
Prisoner B
Cooperate
Defect
Cooperate
Defect
3/3
5/0
0/5
1/1
• But we are so lucky to know this information!
Crocodile’s Dilemma
• V: The value of a resource
• C: The cost to fight for a resource, C > V >0
Crocodile B
Crocodile A
Share
Share
Fight
V
2
/
V
2
V/0
Fight
0/V
V C
2
V C
/ 2
• Negative payoff results in death
– But who defines V and C? These variables are unclear for reallife competitions.
Population’s Dilemma
• Population members play against each
other
• Natural selection favors the better
strategists at the game
• Key: strategies are really genetically
encoded and do not change
Evolutionary algorithm
• 1) Obtain strategy (at birth)
• 2) Play strategy against environmental
opponents.
• 3) Evaluate fitness based on value obtained
through strategy
• 4) Convert fitness to replication, preserving the
phenotype
• The genetic code of a player can’t change, but
their offspring can have mutated genes (and
therefore a different strategy).
Population’s Dilemma
• Consider 2 scenarios from crocodile’s
dilemma:
– A population of purely aggressive crocodiles
– A population of purely docile crocodiles
• In both scenarios, a mutation results in an
“invasion” of better strategists.
Evolutionarily Stable Strategy (ESS)
• An ESS is a strategy used by a population
of players
• Once established, it is not overtaken by
rare (or “mutant”) strategies
• These are similar but not equivalent to
Nash equilibria
Formal Definition of ESS
• Let S be an evolutionary strategy and T be any
alternative strategy. S is an ESS if either of these
conditions hold:
• Payoff(S,S) > Payoff(T,S) or
• Payoff(S,S) = Payoff(T,S) and
Payoff(S,T) > Payoff(T,T)
• T is a neutral strategy against S, but S always
maintains an advantage over T.
Difference between ESS and Nash
• In a Nash equilibrium,
– Players know the structure of the game and
the potential strategies of opponents.
• In an ESS,
– Strategies are not exhaustively defined
– Payoffs are uncertain
– Strategies can’t change
– Everyone adopts the same strategy
Current applications of ESS to
evolutionary theory
• Competition can, in general, be modeled as a
search for an ESS
• ES strategies used to explain altruism, animal
conflict, market competition, etc.
• Modeling evolution entirely through EES is hard.
– On the smaller scale of cell populations, it’s easier to
see the practical applications.
Mechanisms of Disease
• In an organism, cells compete for various
resources in their environment.
• Mutations occasionally occur in cell
division due to various reasons
• Cancer is a disease where mutated
(tumor) cells oust normal cells in a local
population
Applied Game Theory for Cancer
Therapeutics
• Paper:
– Gatenby and Vincent, Application of quantitative models from
population biology and evolutionary game theory to tumor
therapeutic strategies, Mol. Cancer Therapy, 2003; 2:919-927
• Claim: To effectively treat cancer, all system dynamics
responsible for the tumor invasion must be controlled
• The problems:
– Heterogeneity of cancer (i.e. different strategies)
– Unfeasability of controlling all system dynamics
Modeling competition between tumor
and normal cells
• Assume tumor and normal cells are players in a
game
• Create equations which define a competition
between normal and a certain type of tumor cells
• These equations incorporate system dynamics
variables which can favor either normal or tumor
cells
Lotka-Volterra Equations
• Used to model population competition
dx
 x(a  y )
dt
dy
 y (  x)
dt
• Parameters:
– x: number of prey
(normal cells)
– y: number of predators (tumor cells)
–  ,  ,  ,  : parameters representing interaction btwn
species, open to design by user of model
– Equations represent population growth rates over time
Lotka-Volterra Equations
• Used to model population competition
• Basically,
Rate of growth = # in population * (environmental help to
population – rate of destruction by opponent)
• Parameters:
– x: number of prey
(normal cells)
– y: number of predators (tumor cells)
–  ,  ,  ,  : parameters representing interaction btwn species,
open to design by user of model
– Equations represent population growth rates over time
In the tumor vs. normal setting
• Lotka-Volterra equations formed as follows:
 x  y 
dx

 x 1 
dt
kN 

•
 y  x 
dy

 y 1 
dt
kT 

If the populations play a pair of strategies, the possible outcomes at the
stable state (where dx/dt = dy/dt = 0) are:
– x, y = 0
• Trivial, non-relevant result
– x = kN, y = 0
• All normal cells, tumor completely recessed
– x = (kN - βkT)/(1 - βδ), y = (kT - δkN)/(1 - βδ)
• Normal and tumor cells living in equilibrium (benign tumor)
– x=0, y = kT
• All tumor cells, invasive cancer
Finding Equilibria
Recession
Benign
Invasive
Defining the multi-strategy case
• Until now, the tumor population had a constant
strategy (mutation requires a different set of
parameters)
• The new question is, where can the equilibria be
when the strategy space is exhausted?
• In practice, tumor cells from many different
populations are already present; can the
progress be reversed?
Heterogeneity of Cancer
• Parameter changes can
affect the equilibria
reached. This suggests
an easy cure for cancer,
just by changing
parameters.
• In reality, the tumor
population mutates
quickly and changes
strategy, making it
independent from the
previous system of
equations
Heterogeneity of Cancer
• Basic idea: Assume n different populations of tumor
cells can arise
– Each population gets its own fitness function (i.e. own set of
Lotka-Volterra functions)
Ni  Ni H i (u, N)
i
n
H i (u, N)   i 
 (ui , u j ) N j

j 1
k (ui )
• Parameters:
–
–
–
–
αi:
maximum rate of proliferation for ith population
ui :
strategy of ith population
β(ui,uj): competitive effect of ui versus uj
k(ui): maximum size of ith population
Tumor Evolution
• A strategy evolves according to:
H (u, N )
ui   i
|v ui
v
• σi= chance for mutation in ith population
• v = auxillary variable over strategy space
• The strategy for normal cells has σi= 0
Tumor Evolution vs. Normal
• Normal cells don’t
evolve (bottom) and
continue to die, being
pressured by tumor
cells (top)
• The tumor cells
appear to reach a
steady state. Can
they be treated at this
point with a cellspecific drug?
Augmenting system with specific drug
targets
• Extend fitness functions with a Gaussian, drugspecific term
2

 v u  
i
n
 
H i (u, N)   i 
 (ui , u j ) N j  d h exp 

j 1
k (ui )
 2 h  
• Parameters:
– dh: dosage of drug h
– σh: variance in effectiveness of drug h
– u : strategy (cell type) weakest against drug h
A Bleak Outcome
• Cell-specific treatment is effective at first, but evolving
cells become resistant and invade
In Summary
• Population fitness functions can be
designed using the Lotka-Volterra
functions
• Paper claims:
– Targeted drug therapies alone won’t work
– Trajectories of tumor evolution need to be
changed by systemic, outside factors
– Angiogenesis inhibitors, TNF, etc.
Following this,
• Lots of interest regarding drug interactions and
how they affect cells
• Usually dependent on how much of, or for how
long, a drug molecule is in contact (binds) with a
cell structure
• Computational approaches can be used to
conduct drug simulations in silico
– Paper: Perez-Breva et. al, Game theoretic algorithms
for protein-DNA binding, NIPS 2006
Game Theory in Molecular Biology
• Binding game
– Inputs:
• Protein classes (players)
• Sites (other set of players) which compete and coordinate for
proteins
– Players decide how much protein is allocated to each
site, based on:
• How occupied sites are
• Availability of proteins
• Chemical equilibrium (sites have affinities for particular
proteins up to a certain constant)
– Output: allocation of proteins to sites
Formal definition of binding game
•
•
•
•
•
fj = concentration of protein i
pij= amount of protein i allocated to site j
sij = amount of protein I bound to site j
Eij = affinity of protein i to site j
Utility of protein assignment is defined as:
ui ( pi , s)   pij Eij (1   sij )  H ( pi )
j
i'
Formal definition of binding game
•
•
•
•
•
fj = concentration of protein i
pij= amount of protein i allocated to site j
sij = amount protein i bound to site j
Eij = affinity of protein i to site j
Utility of protein assignment to set of sites s:
ui ( pi , s)   pij Eij (1   sij )  H ( pi )
j
i'
Amount of time that
site j is available for
protein i
Controls the mixing
proportions of
bound proteins
Formal definition of binding game
•
•
•
•
•
•
fj = concentration of protein i
pij= amount of protein i allocated to site j
sij = amount of protein i bound to site j
Eij = affinity of protein i to site j
Kij = chemical equilibrium constant between protein i and site j
Utility of site player j binding to a set of proteins p


u ( s j , p)    sij  K ij ( pij f i  sij )(1   sij ) 
i 
i'

s
j
Amount of protein i
bound to site j
Proportion of protein
i that’s just floating
around
Finding the equilibrium
• It turns out, finding the equilibrium between
protein and site player’s utilities reduces to finding
site occupancies αj
 j   sij (a)
i
• The equilibrium condition is expressed in terms of
just αj, so that overall occupancy is determined by
which proteins are currently bound elsewhere
Algorithm
• Start with all sites empty (αj =0; j = 1…n)
• Repeat until convergence:
– pick one site
– maximize its occupancy time in the context of
available proteins and sites
• algorithm is monotone and guaranteed to
find equilibrium
Simulation model for λ-phage virus
Virus genes are embedded in a
cell’s DNA
gene CI2
Switch Sites
gene CRo
Simulation model for λ-phage virus
During normal function, cell requires
RNA to transcribe genes to proteins
RNA
gene CI2
Switch Sites
gene CRo
Simulation model for λ-phage virus
RNA unknowingly transcribes viral
genes, producing virus proteins
RNA
gene CI2
Switch Sites
gene CRo
Simulation model for λ-phage virus
Virus proteins are
produced by first gene
RNA
gene CI2
gene CRo
Simulation model for λ-phage virus
Virus proteins bind to
available sites
RNA
gene CI2
gene CRo
Simulation model for λ-phage virus
Virus proteins prevent
transcription of later genes,
keeping virus dormant.
gene CI2
gene CRo
Simulation model for λ-phage virus
Virus proteins bind and
block transcription
gene CI2
gene CRo
Simulation model for λ-phage virus
Stress
changes the
affinities of
binding sites
gene CI2
gene CRo
Simulation model for λ-phage virus
RNA is free to
bind to later
genes
gene CI2
gene CRo
Simulation model for λ-phage virus
“clearing”
virus proteins
are produced
gene CI2
gene CRo
Simulation model for λ-phage virus
Clearing proteins release
viral proteins from the
switches
gene CI2
gene CRo
Simulation model for λ-phage virus
Replicated
virus
At this stage, cell breaks
open and releases the
replicated virus
gene CI2
gene CRo
Validation of simulated model
• Increasing concentration at different receptors
leads to different equilibrium
• validated using studied concentrations in
literature (shaded region)
Summary
• Many potential applications of game
theory to biological domain
• Most methods include intuitive and
simplistic reasoning about how biological
entities compete
• Despite simplicity, the models often
explain initial beliefs about behavior