From 2007.igem.org

Markov Chains

One of the first projects we worked on was to develop a mathematical model of graphs for the pancake problem. These graphs were used to find the percent of plasmids that solved problem based on the number of flips. We also developed graphs with biases to see if the length of the flips effect the probability of making the flip. In some of the graphs we saw bouncing because from a starting point you can only get to a solution by an odd number of flips or an even number of flips. If you get to a point on an even number of flips you can never get to an odd number. When the graph shows convergence, regardless whether the number of flips is even or odd you will have a chance to get to one of the solutions. The convergence occurs at .25 because there are 2/8 chances of getting to the solution after a high number of flips which reduces to ¼. We also did graphs using bias wieghts where it takes more flips for the graph to have the bouncing behavior. The biologist suspect that the length of the flips effects the probability of making the flips. Then you would compare mathematical graph to the biologist graph to see the bias.

MATLAB programs that we developed using Markov Chains

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fliplength.m 1.Flip Length]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/pureflip.m 2.Pure Flip]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/biasweighter.m 3.Bias Weighter]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/Poisson.doc Poisson]

Using this statistical method we used to make a chart of the probability of finding true positives based on the number of plasmids.

P(missing all true positives)

We first looked at trying to find the probability of there not being a Hamiltonian Path(HP) and not seeing one.(if they don’t see anything what is the probability that nothing is there.) Knowing that the probability of seeing a HP given that there is not a HP is 0 and the probability of seeing a HP given that there is not one is .99.Since we did not know the probability of not seeing a HP nor do we not know the probability that there is not a HP we decided we need to change the wording of the question to what is the probability of missing all the true positives. We would be able to find this probability if we know the number of cells that can be seen. After talking to the biologist they said if there is a HP there is a 100% probability that they will see it. The answer to our original question of finding the probability for missing all the true positives is 0.

How many orderings of positively oriented edges are 2 flips away from being solved?

We started off stating that n=nodes, e=the number of edges and we needed to arrange n-1 edges. First, we proved that the number of positively orientated edges could not be 1 flip away. Flips are represented by ∧

Example 1

1 2∧ 3 4∧

1 2 -3 -4 New row

Since everything is starts positive we need 2 chunks and they must be in numerical order [1,….,a]….[a+1,…..,n-1]

Example 2

1 2 ∧ _ _ 3 4 ∧

1 2 ∧-4 -3 ∧ _ _

1 2 3 4

Example 3

1 2 3 ∧ _ 4 ∧ _

1 2 3 ∧ -4 ∧ _ _

1 2 3 4 _ _

Next we figured out a formula for how many different ways to have chunks. Number of edges after 1st chunk - number of edges in 2nd chunk

n-1

∑ (e-i) – (n-1-i) = Number of unimportant edges

i=0

n-1

∑ (e-n+1)

i=0

n(e-n+1)

The equation for the number of orderings of positively oriented edges 2 flips away from being solved is:

(e-(n-1) ! × (n(e-n+1))