Inhoudsopgave
HC1 - Stochastic processes and Markov chains (part I) ..................................................................................... 3
Markov proces .................................................................................................................................................... 3
Maximum likelihood estimation ......................................................................................................................... 5
Parameter estimation ........................................................................................................................................ 6
Example – Sequence discrimination ................................................................................................................... 7
HC2 - Stochastic processes and Markov chains (part II) .................................................................................... 8
Example – evolution of cancer............................................................................................................................ 8
Stationary distribution ........................................................................................................................................ 9
Processes back in time ...................................................................................................................................... 11
HC3 – Reconstruction of phylogenetic trees ................................................................................................... 12
Intermezzo on graphs ....................................................................................................................................... 12
A model for DNA evolution ............................................................................................................................... 13
The likelihood: a simple example...................................................................................................................... 16
The Pully principle............................................................................................................................................. 19
Example – Laurasiatherians ............................................................................................................................. 19
Assumptions ..................................................................................................................................................... 20
HC4 – Hidden Markov models ........................................................................................................................ 22
Likelihood ......................................................................................................................................................... 24
HMM vs. Markov Chain .................................................................................................................................... 25
Canonical HMM problems ................................................................................................................................ 26
The Viterbi algorithm ....................................................................................................................................... 28
The Baum-Welch algorithm.............................................................................................................................. 29
Example – Sequence alignment ........................................................................................................................ 29
Example – Array CGH ....................................................................................................................................... 30
Hidden semi-Markov model ............................................................................................................................. 31
Example: array CGH (revisited)......................................................................................................................... 32
HC5 – Undirected network reconstruction – part 1 ........................................................................................ 33
(Conditional) independence graph (CIG) .......................................................................................................... 34
Covariance and correlation .............................................................................................................................. 38
Multivariate normal distribution ...................................................................................................................... 40
HC6 – Undirected network reconstruction – part 2 ........................................................................................ 45
HC7 – Undirected network reconstruction – part 3 ........................................................................................ 57
Partial correlation............................................................................................................................................. 58
Partial correlation vs. regression ...................................................................................................................... 63
All nice … but to what end? .............................................................................................................................. 65
Interpretation pitfall revisited (or: the case for integration) ............................................................................ 67
Further topics ................................................................................................................................................... 69
2
,HC1 - Stochastic processes and Markov chains (part I)
Stochastische processen – voorbeelden:
• Intensiteit van de zon
o Xt (dagen), met 0 t T
o Xt geeft waarde R+ (alleen positieve waarden)
• DNA sequenties
o A, C, G of T
o Xi met i = 1, …, 11 (gegeven uit voorbeeld)
• Hartslag van patiënt
o Gemeten op continu interval [0, T]
o Xt = 0 (no heartbeat) en 1 (heartbeat)
• Hersenactiviteit bij experimenten
o Gemeten op continu interval [0, T]
o Xt geeft waarde R
State space S = collectie van waarden die een random variabele van een stochastisch proces kan
aannemen.
• Als S = {E1, E2, …, Es}, dan is Xt een discreet stochastische variabele
• Als S = [0, ), dan is Xt een continu stochastische variabele
• Tijd kan zowel discreet als continu zijn
Voorbeeld:
• First passage time van een bepaalde state Ei in S is de tijd t waarbij Xt = Ei voor de eerste keer
sinds de start van het proces.
• Absorbing state is de state Ei waarbij geldt: zodra Xt = Ei, dan geldt Xs = Ei voor alle s t. Het
proces verlaat de state Ei niet meer.
• Time of absorption van een absorbing state is de first passage time van die state.
• Een stochastisch proces wordt beschreven door een collectie van tijdpunten, de state space
en de verdeling van de variabelen Xt en hun afhankelijkheid
o Poisson proces: alle variabelen zijn identiek en onafhankelijk verdeeld
o Markov proces: de variabelen zijn afhankelijk op een makkelijke manier
Markov proces
• 1e orde Markov proces: hangt alleen af van de vorige variabele,
o 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 |𝑋𝑡 = 𝑥𝑡 , … , 𝑋1 = 𝑥1 ) = 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 |𝑋𝑡 = 𝑥𝑡 )
3
, o Betekent niet onafhankelijkheid tussen Xt-1 en Xt+1
• 0e orde Markov proces: variabelen zijn onafhankelijk van elkaar
o 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 |𝑋𝑡 = 𝑥𝑡 , … , 𝑋1 = 𝑥1 ) = 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 )
o 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 , 𝑋𝑡 = 𝑥𝑡 ) = 𝑃(𝑋𝑡+1 = 𝑥𝑡+1 ) ∗ 𝑃(𝑋𝑡 = 𝑥𝑡)
o Voorbeelden: kop-of-munt en een dobbelsteen
• m-orde Markov proces: hangt af van het aantal m voor de bepalende variabele
o m=9? De verdeling van de t+1e base hangt af van de 9 voorafgaande basen.
• een Markov proces heet een Markov chain als de state space S discreet is.
• een Markov proces heeft tijd homogeen als de transitie kansen onafhankelijk zijn van t.
• Gebruik een transitiematrix P (voorbeeld van DNA basen): let op – hierbij tellen alle kansen
op de rijen op tot 1.
• Initial distribution = (1, …, s) geeft de probabilities van de initiële state. Ook deze initiële
kansen tellen samen op tot 1.
• De initial distribution en de transitiematrix P bepalen de kansverdeling van het Markov
proces.
• Gebruik de total probability law:
𝑃(𝐴, 𝐵)
𝑃(𝐴, 𝐵) = × 𝑃(𝐵) = 𝑃(𝐴|𝐵) × 𝑃(𝐵)
𝑃(𝐵)
• Hoe bepalen (, P) de probability distribution (transition probabilities) bij tijdsstappen groter
dan 1?
o P(n) = Pn: de transitie matrix voor n-stappen is de 1-staps transitie matrix tot de macht
‘n’.
o Kolmogorov-Chapman vergelijking: (𝑃𝑛+𝑚 )𝑖𝑗 = ∑𝑆𝑘=1(𝑃𝑛 )𝑖𝑘 (𝑃𝑚 )𝑘𝑗
4
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper wjj96. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,49. Je zit daarna nergens aan vast.