Difference between revisions of "Davidson Missouri W/Mathematical Modeling"
Amshoecraft (talk | contribs) |
Amshoecraft (talk | contribs) |
||
| Line 5: | Line 5: | ||
=Markov Chain Model For Flipping= | =Markov Chain Model For Flipping= | ||
| − | + | '''Does starting orientation matter?''' | |
| + | |||
| + | Question: Will the order in which we place the edges in our E.coli computers affect the probability of us detecting a Hamiltonian Path? | ||
| + | |||
| + | Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip. | ||
| + | |||
| + | Answer: We developed a Markov Chain model that takes every signed permutation of edges as a state and the connections between these states are found and categorized by our Matlab programs by both the number of edges that need to be flipped to move between those states and categorized by which specific edge needed to be flipped. Further, our Matlab programs creates a transition matrix based on the weights a user enters to bias the probabilities of making different kinds of flips. | ||
| + | |||
| + | Once this transition matrix is generated we then compute, for each possible starting state, the probability of that starting state transitioning to any of the solved states after x flips given the biasing of different types of flips. When our Markov Chain model is run for more than 2 edges we always observe a convergence of these probabilities no matter what bias we apply. This shows that starting orientation does not matter since the probability of being solved after a large number of flips is the same for each starting orientation. | ||
| + | |||
| + | This begs the question: what is a large number of flips? Mostly we observe that this convergence occurs in the first 20 flips for three edges and only for very extreme probabilities does this convergence occur after 60 flips. However, as the number of edges increase we can expect this convergence to occur later. This does not appear to be a problem. Our flipping mechanism flips edges very quickly, so quickly that it is hard to measure. Additionally, the diameter of our transition diagrams increases linearly with the number of edges so there is no reason to believe that the number of flips to convergence would increase at more than a linear pace. | ||
| + | |||
MATLAB programs that we developed using Markov Chains | MATLAB programs that we developed using Markov Chains | ||
Revision as of 16:41, 8 August 2007
Markov Chain Model For Flipping
Does starting orientation matter?
Question: Will the order in which we place the edges in our E.coli computers affect the probability of us detecting a Hamiltonian Path?
Our mathematical reasoning relies on the fact that the Hin/HixC DNA recombination system makes a large number of flips and for any one flip there is some element of chance that dictates which Hix sites are chosen to flip.
Answer: We developed a Markov Chain model that takes every signed permutation of edges as a state and the connections between these states are found and categorized by our Matlab programs by both the number of edges that need to be flipped to move between those states and categorized by which specific edge needed to be flipped. Further, our Matlab programs creates a transition matrix based on the weights a user enters to bias the probabilities of making different kinds of flips.
Once this transition matrix is generated we then compute, for each possible starting state, the probability of that starting state transitioning to any of the solved states after x flips given the biasing of different types of flips. When our Markov Chain model is run for more than 2 edges we always observe a convergence of these probabilities no matter what bias we apply. This shows that starting orientation does not matter since the probability of being solved after a large number of flips is the same for each starting orientation.
This begs the question: what is a large number of flips? Mostly we observe that this convergence occurs in the first 20 flips for three edges and only for very extreme probabilities does this convergence occur after 60 flips. However, as the number of edges increase we can expect this convergence to occur later. This does not appear to be a problem. Our flipping mechanism flips edges very quickly, so quickly that it is hard to measure. Additionally, the diameter of our transition diagrams increases linearly with the number of edges so there is no reason to believe that the number of flips to convergence would increase at more than a linear pace.
MATLAB programs that we developed using Markov Chains
True Positives / False Positives
MATLAB programs used to find the false positives:
1. Adelman's False Positives with 12 nodes
2. Adelman's False Positives with 14 nodes
3. Counter Program for Adelman's False Positives
Possion Model For the Number of Plasmids
Using this statistical method we used to make a chart of the probability of finding true positives based on the number of plasmids.
