Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Random Walk Formula
From OpenWetWare
Tuesday, September 23, 2014

Random Walk FormulaModeling IdeaThe 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.
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. General ApproachTwo 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 be the probability that the walker reaches 0 for the first time after steps given its starting position being . obeys the following difference equation for and . We define ; . Also, . When we have The generating function for can be expressed as Following Netus (1963), the explicit expression of the generating function is where and The explicit expression of can thus be deduced from using partial fraction expansion (Feller, 1971). Assume that has distinct roots can then be decomposed into partial fractions where It follows that can be similarly deduced from using the same method. Parameter EstimationPossible 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 , and 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 , and . 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 , while the probability of going to Lines 1 or 3 is . Similarly, when it is in Lines 1 or 3, the probability of staying in the same line after one branch migration is while the probability of going to Line 2 is . 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 denote the proportion of walkers in Line 2 (a) and Lines 1&3 (1 − a) after branch migrations. Since all the walkers are initially planted in the center, . Define the transition matrix It follows that It was found that Hence at the stable state, 40% of the walkers are in Line 2 while 60% are in Lines 1 or 3. Since , the distribution of relative positions of walkers on the origami stabilizes after approximately 4 branch migrations. The overall probabilities can thus be calculated (Table 1).
Explicit Expression of FormulaeThe 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.
Cumulative FunctionThe cumulative density function of can be computed and used to fit with SPEX experimental data. A plot of verses can be used as a good model to fit the experimental data (Figure 3), where C(t;i) is the proportion of walkers that reach the walker goal and is the number of steps needed. It can be found that the number of steps needed for half of the walkers to reach WG decreases as we move SP nearer to the WG. Number of Branch Migrations per StepTo further study the validity of this model, the number of branch migrations per step was calculated in order to obtain the average rate of branch migration. Let denote the probability of walking to the adjacent column after branch migrations. For walkers at the center line(Line 2),
It follows that the expected number of branch migrations per step is and for walkers at the center and sides, respectively. Taking into account that 40% of walkers are References
