Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Random Walk Formula

From OpenWetWare

(Difference between revisions)
Jump to: navigation, search
(→Random Walk Formula)
(→Explicit Expression of Formulae)
Line 93: Line 93:
The explicit expression for the probability of reaching the walker goal (h(t;i)) as a function of the number of steps taken (t) can then be deduced using the general approach and the estimated parameters.
The explicit expression for the probability of reaching the walker goal (h(t;i)) as a function of the number of steps taken (t) can then be deduced using the general approach and the estimated parameters.
-
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>SP10:   h(t;12)= \begin{cases} 0, 0\leqslant t < 12\\
+
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>SP10: h(t;12)= \begin{cases} 0, 0\leqslant t < 12\\
-
  \frac{0.0032}{1.0025^{t+1}} - \frac{0.0097}{1.0226^{t+1}} + \frac{0.0166}{1.0639^{t+1}} - \frac{0.02407}{1.1283^{t+1}} + \frac{0.0323}{1.2189^{t+1}} -\frac{0.0410}{1.3387^{t+1}} +\frac{0.0494}{1.4908^{t+1}} -\frac{0.0556}{1.6753^{t+1}} +\frac{0.0565}{1.8863^{t+1}} -\frac{0.0482}{2.1070^{t+1}} +\frac{0.0301}{2.3071^{t+1}} -\frac{0.0094}{2.4487^{t+1}}           
+
  \frac{0.0032}{1.0025^{t+1}} - \frac{0.0097}{1.0226^{t+1}} + \frac{0.0166}{1.0639^{t+1}} - \frac{0.02407}{1.1283^{t+1}} + \frac{0.0323}{1.2189^{t+1}} -\frac{0.0410}{1.3387^{t+1}} \\ \quad +\frac{0.0494}{1.4908^{t+1}} -\frac{0.0556}{1.6753^{t+1}} +\frac{0.0565}{1.8863^{t+1}} -\frac{0.0482}{2.1070^{t+1}} +\frac{0.0301}{2.3071^{t+1}} -\frac{0.0094}{2.4487^{t+1}}           
-
 
+
,t \geqslant 12\end{cases}</math></div>
,t \geqslant 12\end{cases}</math></div>

Revision as of 07:00, 8 October 2011

Image:DeoxyriboNucleicAwesomeHeader.jpg

Friday, May 24, 2013

Home

Members

Project

Protocols

Progress

Discussion

References


Contents

Random Walk Formula

Modeling Idea

The random walk on DNA origami can be modeled as one dimensional random walk with a reflecting and an absorbing barrier (Figure 1). Tracks in the same column are grouped into rectangles, and each step is defined as walking from one rectangle to an adjacent one. We are interested in expressing the probability of reaching the walker goal as a function of the number of steps taken.


Figure 1. Modeling the random walk on DNA origami as one dimensional random walk. Cyan, markers. Blue, Track 1. Red, Track 2. White, DNA staples only. Five-pointed star, walker goal. Each step is modeled as walking from one rectangle to an adjacent one. SP 10, 22, 34 indicate different starting positions. Note that in the cases of SP22 and SP34, there are no tracks to the left of starting positions.
Figure 1. Modeling the random walk on DNA origami as one dimensional random walk. Cyan, markers. Blue, Track 1. Red, Track 2. White, DNA staples only. Five-pointed star, walker goal. Each step is modeled as walking from one rectangle to an adjacent one. SP 10, 22, 34 indicate different starting positions. Note that in the cases of SP22 and SP34, there are no tracks to the left of starting positions.

Consider a random walk on a line segment with N+1 sites denoted by integers (0,1,2, … , N) (Figure 2). The walker starts random walk at site i, 0 < i ≤ N. Let p be the probability for the walker to move one segment to the left, q be the probability for the walker to move one segment to the right. The probability for the walker to stay at a particular site for the next unit time is thus r = 1 – p – q. When the walker reaches site N, the partially reflecting barrier, it has a probability of β to be reflected back to site N – 1, and a probability of α = 1 – β to stay at site N in the next unit time. When reaching site 0, the absorbing barrier, it stays there for 100% probability and the random walk ends.

Figure 2. A line segment with N+1 distinct sites. The walker starts the random walk at i and is reflected at N with a probability of β. The random walk ends once it reaches site 0.
Figure 2. A line segment with N+1 distinct sites. The walker starts the random walk at i and is reflected at N with a probability of β. The random walk ends once it reaches site 0.

General Approach

Two assumptions are made in our case. 1) The DNA origami is immune to any free floating walkers in solution, meaning that free floating walkers cannot bind to an origami and starts random walking; 2) walkers are immediately absorbed when reaching the rectangles with WGs, despite the presence of two TR2 in the same rectangle.

Let h(t;i)\! be the probability that the walker reaches 0 for the first time after t\! steps given its starting position being i\!. h(t;i)\! obeys the following difference equation

h(t;i) = q·h(t-1;i-1) + r·h(t-1;i) + p·h(t-1; i + 1)\!

for t = 1,2,3,...\! and i = 1,2,3,...,N-1\!. We define h(t;0)= 1\! if\! t = 0\!; h(t;0)= 0\! if\! t > 0\!. Also, h(t;i) = 0\! for\! t < i\!.

When i = N\! we have

h(t;N) = αh(t-1;N)+ βh(t-1; N-1) \!

The generating function for h(t;i)\! can be expressed as

H_i (s) = \sum_{t=0}^\infty h(t;1)s^t,|s| <1 \!

Following Netus (1963), the explicit expression of the generating function is

H_i (s) =\begin{cases} \frac {q^i s^i T_i (s)} {T_0 (s)}, 0\leqslant i < N\\ \frac {\beta q^{N-1} s^N (\lambda_1 - \lambda_2)} {T_0 (s)},i=N\end{cases}\!

where

T_i (s) = (1-\alpha s)(\lambda_1 ^{N-i}-\lambda_2 ^{N-i})-\beta p s^2 (\lambda_1 ^{N-i-1}-\lambda_2 ^{N-i-1})\!

and

\lambda_{1,2} = \frac {1} {2} ( \pm \sqrt{{(1-rs)}^2-4 p q s^2} +1-rs ).\!

The explicit expression of h(t;i)\! can thus be deduced from H_i (s)\! using partial fraction expansion (Feller, 1971).

Assume that T_0 (s)\! has k\! distinct roots s_1,s_2,..., s_k . H_i (s)\! can then be decomposed into partial fractions

H_i (s) = \frac {\rho_1} {s-s_1} + \frac{\rho_2}{s-s_2} +...+ \frac {\rho_k}{s-s_k} \!

where

\rho_k = \frac {-q^i {s_m}^i T_i (S_m)}{{T_0}^' (s_m)}, m\leqslant k \!

It follows that

h(t;i) = \sum_{m=1}^k \frac {\rho_m}{{s_m}^{t+1}} \!

h(t;N)\! can be similarly deduced from H_N (s)\! using the same method.

Parameter Estimation

Possible positions of walkers on the origami can be grouped into two categories, either in the center of rectangles (Figure 1, Line 2) or at the sides (Figure 1, Lines 1&3), and the values of p\!, q\! and r\! are different in each category. Hence there is a need to find out the distribution of walkers in these two categories in order to estimate p\!, q\! and r\!. Due to the nature of our design, each walker has a probability of 50% to stay at its original track after one branch migration. Assuming no reflecting boundaries, when the walker is in the center (Figure 1, Line 2), the probability of staying in Line 2 after one branch migration is \frac {1}{2}+\frac{1}{2} \times \frac{1}{2}=\frac{3}{4}, while the probability of going to Lines 1 or 3 is 1- \frac{3}{4}=\frac{1}{4}. Similarly, when it is in Lines 1 or 3, the probability of staying in the same line after one branch migration is \frac{1}{2}+\frac{1}{2} \times \frac{2}{3}=\frac{5}{6} while the probability of going to Line 2 is 1- \frac{5}{6}=\frac{1}{6}. Here we assume no reflecting barrier in the system. The distribution of relative positions of walkers can be modeled using Markov chain as follows.

Let v(t) = (a, 1–a)\! denote the proportion of walkers in Line 2 (a)\! and Lines 1&3 (1–a)\! after t\! branch migrations. Since all the walkers are initially planted in the center, v(0) = (1, 0)\!. Define the transition matrix

M = \begin{pmatrix} 3/4 & 1/4 \\ 1/6 & 5/6 \end{pmatrix}. \!

It follows that

v(t)=v(0). \underbrace{M.M.M...M}_{t} \!

It was found that \lim_{t \to \infty} v(t)= (0.4,0.6).Hence at the stable state, 40% of the walkers are in Line 2 while 60% are in Lines 1 or 3. Since v(8) = (0.408,0.592)\!, the distribution of relative positions of walkers on the origami stabilizes after approximately 8 branch migrations.

The overall probabilities p, q, r, \alpha,\beta\! can thus be calculated (Table 1).


Table 1. Calculation of overall probabilities used in random walk modeling.
p\!
q\! r\! \alpha\! \beta\!
Walkers at the center (Line 2) (40%) \frac{1}{8} \frac{1}{8} \frac{3}{4} \frac{5}{6} \frac{1}{6}
Walkers at the sides (Lines 1 and 3) (60%) \frac{1}{6} \frac{1}{6} \frac{2}{3} \frac{3}{4} \frac{1}{4}
Overall Probability \frac{3}{20} \frac{3}{20} \frac{7}{10} \frac{47}{60} \frac{13}{60}


Determination of the overall probabilities allow us to derive the explicit probability distribution functions for SP10, 22 and 34.

Explicit Expression of Formulae

The explicit expression for the probability of reaching the walker goal (h(t;i)) as a function of the number of steps taken (t) can then be deduced using the general approach and the estimated parameters.

SP10: h(t;12)= \begin{cases} 0, 0\leqslant t < 12\\ \frac{0.0032}{1.0025^{t+1}} - \frac{0.0097}{1.0226^{t+1}} + \frac{0.0166}{1.0639^{t+1}} - \frac{0.02407}{1.1283^{t+1}} + \frac{0.0323}{1.2189^{t+1}} -\frac{0.0410}{1.3387^{t+1}} \\ \quad +\frac{0.0494}{1.4908^{t+1}} -\frac{0.0556}{1.6753^{t+1}} +\frac{0.0565}{1.8863^{t+1}} -\frac{0.0482}{2.1070^{t+1}} +\frac{0.0301}{2.3071^{t+1}} -\frac{0.0094}{2.4487^{t+1}} ,t \geqslant 12\end{cases}

References

  • Ahmed El-Shehawy (1992). On absorption probabilities for a random walk between two different barriers. Annals De La Faculte Des Sciences De Toulouse, 1(1), 95-103.
  • Feller, W. (1971). An introduction to probability theory and its applications.
  • Netus, M. (1963). Absorption probabilities for a random walk between a reflecting and an absorbing barrier. Bull. Soc. Math. Belgique, 15, 253-258.
Retrieved from "http://openwetware.org/wiki/Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Random_Walk_Formula"
Personal tools