PaulaTataru
1 like150 views
This document discusses methods for calculating conditional expectations of sufficient statistics for continuous time Markov chains. It presents three methods - eigenvalue decomposition, uniformization, and exponentiation - and evaluates their accuracy and speed for different models and time points. For accuracy, it finds that exponentiation is most accurate. For speed, exponentiation is slowest while eigenvalue decomposition and uniformization trade off accuracy and speed depending on the model and time points. Uniformization has potential to be improved through better cutoff points or adaptive uniformization techniques.
PaulaTataru
- 1. Paula Tataru Conditional expectations of sufficient statistics for continuous time Markov chains Joint work with Asger Hobolth November 28, 2012
- 2. Motivation Methods Results Paula Tataru 2/30 Conditional expectations of sufficient statistics for CTMCs Continuous-time Markov chains A stochastic process {X(t) | t 0} that fulfills the Markov property
- 3. Motivation Methods Results Paula Tataru 3/30 Conditional expectations of sufficient statistics for CTMCs Continuous-time Markov chains Credit risk States: different types of ratings Chemical reactions States: different states of a molecule DNA data States: Nucleotides Amino acids Codons
- 4. Motivation Methods Results Paula Tataru 4/30 Conditional expectations of sufficient statistics for CTMCs Modeling DNA data 1st 2nd base 3rd base T C A G base T TTT Phe TCT Ser TAT Tyr TGT Cys T TTC TCC TAC TGC C TTA Leu TCA TAA Stop TGA Stop A TTG TCG TAG Stop TGG Trp G C CTT CCT Pro CAT His CGT Arg T CTC CCC CAC CGC C CTA CCA CAA Gln CGA A CTG CCG CAG CGG G A ATT Ile ACT Thr AAT Asn AGT Ser T ATC ACC AAC AGC C ATA ACA AAA Lys AGA Arg A ATG Met ACG AAG AGG G G GTT Val GCT Ala GAT Asp GGT Gly T GTC GCC GAC GGC C GTA GCA GAA Glu GGA A GTG GCG GAG GGG G
- 5. Motivation Methods Results Paula Tataru 5/30 Conditional expectations of sufficient statistics for CTMCs Modeling DNA data Nucleotides (n = 4) Amino acids (n = 20) Codons (n = 64)
- 6. Motivation Methods Results Paula Tataru 6/30 Conditional expectations of sufficient statistics for CTMCs Continuous-time Markov chains Characterized by a rate matrix with properties
- 7. Motivation Methods Results Paula Tataru 7/30 Conditional expectations of sufficient statistics for CTMCs Modeling DNA data Nucleotides (n = 4) Jukes Cantor (JC)
- 8. Motivation Methods Results Paula Tataru 8/30 Conditional expectations of sufficient statistics for CTMCs Continuous-time Markov chains Waiting time is exponentially distributed Jumps are discretely distributed
- 10. Motivation Methods Results Paula Tataru 10/30 Conditional expectations of sufficient statistics for CTMCs General EM Full log likelihood E-step M-step
- 11. Motivation Methods Results Paula Tataru 11/30 Conditional expectations of sufficient statistics for CTMCs EM for Jukes Cantor Full log likelihood M-step
- 12. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 12/30 Calculating expectations
- 13. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 13/30 Linear combinations
- 14. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 14/30 Linear combinations
- 15. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 15/30 Linear combinations
- 16. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 16/30 Methods In Hobolth&Jensen (2010), three methods are presented to evaluate the necessary statistics Eigenvalue decomposition (EVD) Uniformization (UNI) Exponentiation (EXPM) Extend efficiently to linear combinations Which method is more accurate? Which method is faster?
- 17. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 17/30 Eigenvalue decomposition
- 19. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 19/30 Uniformization Choose truncation point s(亮t) Bound error using the tail of Pois(m+1; 亮t) s(亮t) = 4 + 6 亮t + 亮t
- 21. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 21/30 Algorithms EVD UNI EXPM* 1 A Order 2 J(t) Order 3 (C; t)裡 (C; t)裡 (C; t)裡 Order Influenced by Q , U, U -1 亮, s(亮t), R O(n3 ) O(n2 ) O(n2 ) Rm eAt O(n2 ) O(s(亮t)n3 ) O(n3 ) O(n3 ) O(s(亮t)n2 ) O(n2 ) 亮t * expm package in R
- 22. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 22/30 Accuracy Use two models for which (C; t) is available in analytical form JC, varying n HKY, varying t Measure accuracy as the normalized difference: approximation / true - 1 as a function of n as a function of t
- 24. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 24/30 Speed EVD UNI EXPM* 1 A Order 2 J(t) Order 3 (C; t)裡 (C; t)裡 (C; t)裡 Order Influenced by Q , U, U -1 亮, s(亮t), R O(n3 ) O(n2 ) O(n2 ) Rm eAt O(n2 ) O(s(亮t)n3 ) O(n3 ) O(n3 ) O(s(亮t)n2 ) O(n2 ) 亮t
- 25. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 25/30 Speed Partition of computation Precomputation EVD UNI Main computation Use three models and different time points to asses the speed GY, n = 61 GTR, n = 4 UNR, n = 4
- 26. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 26/30 Speed 10 equidistant time points
- 28. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 28/30 Results Accuracy Similar accuracy EXPM is the most accurate one Speed EXPM is the slowest EVD vs UNI
- 29. Motivation Methods Results Paula Tataru Conditional expectations of sufficient statistics for CTMCs 29/30 Results UNI has potential Better cut off point s(亮t) Ameliorate effect of 亮t by Adaptive uniformization On-the-fly variant of adaptive uniformization
- 30. Thank you! Comparison of methods for calculating conditional expectations of sufficient statistics for continuous time Markov chains BMC Bioinformatics 12(1):465, 2011