# Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Random Walk Formula

(Difference between revisions)
 Revision as of 01:49, 3 October 2011 (view source) (→Random Walk Formula)← Previous diff Revision as of 01:56, 3 October 2011 (view source) (→References)Next diff → Line 42: Line 42: ==References== ==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''. *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. *Netus, M. (1963). Absorption probabilities for a random walk between a reflecting and an absorbing barrier. ''Bull. Soc. Math. Belgique, 15'', 253-258. {{Template:DeoxyriboNucleicAwesomeFooter}} {{Template:DeoxyriboNucleicAwesomeFooter}}

## Revision as of 01:56, 3 October 2011

Friday, July 28, 2017

Home

Members

Project

Protocols

Progress

Discussion

References

# Random Walk Formula

## General 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.

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.

## Random Walk Formula

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=1}^∞ 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) \!$

## 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.