Matrix Models of Base Substitutions II: Eigenvalues and Eigenvectors
Exploring matrix models in mathematical modeling, focusing on base substitutions. Reviewing Markov models, understanding characteristic polynomials, eigenvectors, and eigenvalues. Discussing geometric meanings, Lemmas, and base distribution vectors estimation using transition matrices. Assumptions in Markov models and the mathematical implications attached.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MAT 4830 Mathematical Modeling 4.4 Matrix Models of Base Substitutions II http://myhome.spu.edu/lauw
Markov Models Review of Eigenvalues and Eigenvectors An example a Markov model. Specific Markov models for base substitution: Jukes-Cantor Model Kimura Models (Read)
Recall Characteristic polynomial of A Eigenvalues of A Eigenvectors of A
Recall Characteristic polynomial of A ( ) P = det( ) A I Eigenvalues of A P zeros of ( ) Eigenvectors of A = ( ) 0, 0 A I x x
Geometric Meaning n n R R Consider : A = = = = ( ) 0 0 A Ax I x x Ax x scalar multiple of x
Lemma + = n n , for A x x n Z Typically, this type of formula should be proved by Induction.
Recall Use the transition matrix, we can estimate the base distribution vectors of descendent sequences by p = kp k = , 1,2,3,... k S Mp 1 k k An example of Markov model
Markov Models Assumption What happens to the system over a given time step depends only on the state of the system and the transition matrix
Markov Models Assumption What happens to the system over a given time step depends only on the state of the system and the transition matrix In our case, pk only depends on pk-1 and M = p Mp 1 k k
Markov Models Assumption What happens to the system over a given time step depends only on the state of the system and the transition matrix In our case, pk only depends on pk-1 and M Mathematically, it implies ( ( ) 1 1 | k k k k P S s S s = = = = p Mp 1 k k ) ( ) ( ) ( ) = = = = | P S s S s S s S s 1 1 2 2 0 0 k k k k k k
Markov Matrix All entries are non-negative. column sum = 1. P P P P P P | | | | A A AG AC AT G A P P P G G P P P G C P P P | | | | GT = = M P | i j | | | | C A C G C C C T P | | | | T A T G T C T T
Markov Matrix : Theorems Read the two theorems on p.142
Jukes-Cantor Model Additional Assumptions All bases occurs with equal prob. in S0. T 1 4 1 4 1 4 1 4 = p 0
Jukes-Cantor Model Additional Assumptions Base substitutions from one to another are equally likely. P P M P P P P P P P P | | | | A A AG AC AT G G P P P G C P P P | | | | G A GT = = | i j | | | | C A C G C C C T P | | | | T A T G T C T T constant = = , for P i j | i j 3
Jukes-Cantor Model P P P P P P | | | | A A AG AC AT G A P P P G G P P P G C P P P | | | | GT = = M P | i j | | | | C A C G C C C T P | | | | T A T G T C T T constant = = , for P i j | i j 3
Jukes-Cantor Model 1 /3 /3 /3 /3 /3 /3 /3 1 /3 /3 = = M P | i j /3 1 /3 /3 1 constant = = , for P i j | i j 3
Observation #1 = = = 1 prob. of no base sub. in a site for 1 time step prob. of having base sub. in a site for 1 time step rate of base sub. sub. per site per time step 1 /3 /3 /3 /3 /3 /3 /3 /3 /3 1 = = M P | i j /3 1 /3 /3 1
Mutation Rate Mutation rates are difficult to find. Mutation rate may not be constant. If constant, there is said to be a molecular clock More formally, a molecular clock hypothesis states that mutations occur at a constant rate throughout the evolutionary tree.
Observation #2 1 /3 /3 /3 /3 /3 /3 /3 1 /3 /3 = = M P | i j /3 1 /3 /3 1 T 1 4 1 4 1 4 1 4 = p 0 = = ? ? for p p 1 = 1,2,3,... k k
Observation #2 1 4 1 4 1 4 1 4 1 /3 /3 /3 /3 /3 /3 /3 1 /3 /3 = = ? Mp 0 /3 1 /3 /3 1 = = ? ? for p p 1 = 1,2,3,... k k
Observation #2 The proportion of the bases stay constant (equilibrium) What is the relation between p0 and M?
Example 1 What proportion of the sites will have A in the ancestral sequence and a T in the descendent one time step later? 1 /3 /3 /3 /3 /3 /3 T /3 1 /3 /3 1 4 1 4 1 4 1 4 = = = M P p | 0 i j /3 1 /3 /3 1
Example 2 What is the prob. that a base A in the ancestral seq. will have mutated to become a base T in the descendent seq. 100 time steps later?
Example 2 What is the prob. that a base A in the ancestral seq. will have mutated to become a base T in the descendent seq. 100 time steps later? = = p Mp 1 k k 100 100 p M p 0
Example 2 p M = 100 p 100 0 = 100 100 p M p 0
Example 2 p M = 100 p 100 0 = 100 100 p M p 0 = = 100 4,1 ( | ) M "Must be" P S T S A 100 0
Example 2 p M = 100 p 100 0 [ ] = = = 100 ( | ) If M P S i S j 100 0 = 100 then p M p = 100 0 [ ] = 100 If p M p 100 0 100 100 p M p = = = 100 ( | ) then M P S i S j 0 100 0 = = 100 4,1 ( | ) M "Must be" P S T S A 100 0
Example 2 p M = 100 p 100 0 [ ] = = = 100 ( | ) If M P S i S j 100 0 = 100 then p M p = 100 0 [ ] = 100 If p M p 100 0 100 100 p M p = = = 100 ( | ) then M P S i S j 0 100 0 = = 100 4,1 ( | ) M "Must be" P S T S A For general n, can be prove by inductive arguments. 100 0
Homework Problem 1 p M p = 2 2 0 = 2 p M p 2 0 = = = 2 4,1 ( | ) Explain why M P S T S A 2 0
Example 2 (Books Solutions) M p = t tp Find the eigenvalues and the corresponding eigenvectors v for i = 0 i , i 1,2,3,4 = t tp M p 0 = = = ( | ) ? P S T S A 0 t
Example 2 (Books Solutions) M p = t tp Find the eigenvalues and the corresponding eigenvectors v for i = 0 i , i 1,2,3,4 = t tp M p 0 1 0 0 0 t M
Example 2 (Books Solutions) M p = t tp Find the eigenvalues and the corresponding eigenvectors v for i = 0 i , i 1,2,3,4 = = 1 0 0 0 1 4 1 4 1 4 1 4 + + + v v v v 1 2 3 4 t tp M p 0 1 0 0 0 t M
Example 2 (Books Solutions) M p = t tp Find the eigenvalues and the corresponding eigenvectors v for i = 0 i , i 1,2,3,4 = = 1 0 0 0 1 4 1 4 1 4 1 4 + + + v v v v 1 2 3 4 t tp M p Why? 0 1 0 0 0 t M
Example 2 (Books Solutions) M p = t tp = 1 0 0 0 0 1 4 1 4 1 4 1 4 + + + t t t t t M M v M v M v M v 1 2 3 4 = 1 4 1 4 1 4 1 4 = + + + t t t t v v v v 1 1 2 2 3 3 4 4 t 1 4 3 4 3 4 + 1 t t tp M p 1 4 1 4 3 4 1 0 = t 1 4 1 4 3 4 1 0 0 0 1 t M t 1 4 1 4 3 4 1
Example 2 (Books Solutions) t t t t 1 4 3 4 3 4 1 4 1 4 3 4 1 4 1 4 3 4 1 4 1 4 3 4 + 1 1 1 1 t t t t 1 4 1 4 3 4 1 4 3 4 3 4 1 4 1 4 3 4 1 4 1 4 3 4 + 1 1 1 1 = t M t t t t 1 4 1 4 3 4 1 4 1 4 3 4 1 4 3 4 3 4 1 4 1 4 3 4 + 1 1 1 1 t t t t 1 4 1 4 3 4 1 4 1 4 3 4 1 4 1 4 3 4 1 4 3 4 3 4 + 1 1 1 1
Our Solutions Theorem: Suppose corresponding eigenvectors . and the is a symmetric matrix with eigenvalues v = M i i 0 1 2 = Let [ v v ] and P v D 1 2 n 0 n = 1 Then, 1 /3 /3 /3 /3 /3 /3 D P MP /3 1 /3 /3 /3 1 /3 /3 1
Our Solutions t 0 0 0 0 0 0 1 t 0 0 0 = 1 t 2 M P P t 0 0 3 t 0 4 = 1 D P MP
Our Solutions t t t t 1 4 3 4 4 3 1 4 1 4 4 3 1 4 1 4 4 3 1 4 1 4 4 3 + 1 1 1 1 t t t t 1 4 1 4 4 3 1 4 3 4 4 3 1 4 1 4 4 3 1 4 1 4 4 3 + 1 1 1 1 = t M t t t t 1 4 1 4 4 3 1 4 1 4 4 3 1 4 3 4 4 3 1 4 1 4 4 3 + 1 1 1 1 t t t t 1 4 1 4 4 3 1 4 1 4 4 3 1 4 1 4 4 3 1 4 3 4 4 3 + 1 1 1 1
Maple: Vectors M.v
Homework Problem 2 Although the Jukes-Cantor model assumes , a Jukes-Cantor transition matrix could describe mutations even a different . Write a Maple program to investigate the behavior of . T p = 0.25 0.25 0.25 0.25 0 0p kp
Homework Problem 3 Read and understand the Kimura 2- parameters model. Read the Maple Help to learn how to find eigenvalues and eigenvectors. Suppose ? is the transition matrix corresponding to the Kimura 2-parameters model. Find a formula for ?? by doing experiments with Maple. Explain carefully your methodology and give evidences.
Next Download HW from course website Read 4.5
