Transcript Applications of Game Theory in the Computational Biology Domain

Applications of Game Theory
in the Computational Biology
Domain
Richard Pelikan
April 13, 2008
CS 3110
Overview
• The evolution of populations
• Understanding mechanisms for disease
and regulatory processes
– Models of cancer development
– Competition for limited resources, e.g. protein
site binding
• 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
– 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
• Players have strategies for obtaining the payoffs
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
Strategy and Genetics
• Idea: An organism’s strategy is encoded at
birth by its genetic code
• The fitness of a phenotype is determined
by its frequency in the population
• 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 (EES)
• An EES 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 EES
• Let S be an evolutionary strategy and T be any
alternative strategy. S is an EES 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 EES and Nash
• In a Nash equilibrium,
– Players know the structure of the game and
the potential strategies of opponents.
• In an EES,
– Strategies are genetically encoded, cannot
change, and the structure of the game is
unclear. Opponent strategies are not
exhaustively defined.
Current applications of ESS to
evolutionary theory
• Competition can, in general, be modeled
as a search for an EES
• Hard to explain all of evolution at once
• Step down from the population to the
organism (cellular) level.
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
• Claim: To effectively treat cancer, all
system dynamics responsible for the
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
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, a population of tumor cells is 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 weakest against drug h
• 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
• Drug-specific therapies alone won’t work
• Trajectories of tumor evolution need to be
changed by systemic, outside factors
– Angiogenesis inhibitors, TNF, etc.
Game Theory in Molecular Biology
• Binding game
– Inputs:
• Protein classes (players)
• Sites (other set of players) which compete and coordinate for
proteins
– Players decide which sites to send proteins to, 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 time for site j to bind protein i
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 of time for site j to bind protein i
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 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 time for site j to bind protein i
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
i
Amount of available
protein to site j
Amount of “free
time” that site j has
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
• iuiu
RNA
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