GcatWiki - User contributions [en]

Davidson Missouri W/Mathematical Modeling

2007-08-09T18:45:53Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]]

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Fpospic.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]

true positives = 384
false positives = 1,362

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]

true positives = 10,321,920
false positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W

2007-08-09T15:22:44Z

Amshoecraft: /* Our Project */

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Software|Software]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>
 

[[Image:DMW-1.jpg|300px|center]]

<center>
=The Team=
</center>
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"
|-
! style="color: white; background-color: black;"| The Team
! style="color: white; background-color: black;" | The Faculty
! style="color: white; background-color: black;" | Team Logos
! style="color: white; background-color: black;" | Group Photo
|-

|style="color: black; background-color: red;" align="center"| '''Davidson'''

[[Davidson Missouri W/Oyinade Adefuye|Oyinade Adefuye]]
 
[[Davidson Missouri W/Will DeLoache|Will DeLoache]]
 
[[Davidson Missouri W/Jim Dickson|Jim Dickson]]
 
[[Davidson Missouri W/Andrew Martens|Andrew Martens]]
 
[[Davidson Missouri W/Amber Shoecraft|Amber Shoecraft]]
 
[[Davidson Missouri W/Mike Waters|Mike Waters]]


|style="color: black; background-color: red;" align="center"|

[[Davidson Missouri W/A. Malcolm Campbell|A. Malcom Campbell]]
 
[[Davidson Missouri W/Karmella Haynes|Karmella Haynes]]
 
[[Davidson Missouri W/Laurie Heyer|Laurie Heyer]]


|style="color: black; background-color: white;" align="center"|
[[Image:DavidsonLogo.gif]]

|style="color: black; background-color: white;" align="center"|
[[Image:Team1.jpg|thumb|300px]]

|-

|style="color: black; background-color: gold;" align="center"|'''Missouri Western'''

[[Davidson Missouri W/Jordan Baumgardner|Jordan Baumgardner]]
 
[[Davidson Missouri W/Tom Crowley|Tom Crowley]]
 
[[Davidson Missouri W/Lane H. Heard|Lane H. Heard]]
 
[[Davidson Missouri W/Nickolaus Morton|Nickolaus Morton]]
 
[[Davidson Missouri W/Michelle Ritter|Michelle Ritter]]
 
[[Davidson Missouri W/Jessica Treece|Jessica Treece]]
 
[[Davidson Missouri W/Matthew Unzicker|Matthew Unzicker]]
 
[[Davidson Missouri W/Amanda Valencia|Amanda Valencia]]


|style="color: black; background-color: gold;" align="center"|

[[Davidson Missouri W/Todd Eckdahl|Todd Eckdahl]]
 
[[Davidson Missouri W/Jeff Poet|Jeff Poet]]


|style="color: black; background-color: white;" align="center"|[[Image:MWLogo.gif]]

|style="color: black; background-color: white;" align="center"|
|-

|}

 
[[Image:Team_graph.jpg|center|thumb|500px|A Human Representation of Adleman's Graph (see below)]]
 

<center>

=Our Project=
</center>

{| border="1" cellpadding="5" cellspacing="0" align="center" width="90%"
|-
! style="color: black; background-color: red;" width="20%"| In Depth
! colspan="3" style="color: black; background-color: red;" width="60%"| Overview
|-
|style="color: black; background-color: black;" align="center"|
[[Davidson Missouri W/Background Information|Background Information]]
 
[[Davidson Missouri W/Solving the HPP in vivo|Current Project: Solving the Hamiltonian Path Problem ''in vivo'']]
 
[[Davidson Missouri W/Mathematical Modeling|Mathematical Modeling]]
 
[[Davidson Missouri W/Gene splitting|Gene Splitting]]
 
[[Davidson Missouri W/Controlling Expression|Controlling Expression]]
 
[[Davidson Missouri W/Traveling Salesperson Problem|Traveling Salesperson Problem]]
 
[[Davidson Missouri W/Backwards Promotion and read-through transcription|Backwards Promotion and Read-Through Transcription]]
 
[[Davidson Missouri W/Resources and Citations|Resources and Citations]]
 
|Hamiltonian Path Problem
As a part of iGEM2006, a combined team from Davidson College and Missouri Western State University reconstituted a hin/hix DNA recombination mechanism which exists in nature in Salmonella as standard biobricks for use in ''E. coli''. The purpose of the 2006 combined team was to provide a proof of concept for a bacterial computer in using this mechanism to solve a variation of The Pancake Problem from Computer Science. This task utilized both biology and mathematics students and faculty from the two institutions.

For 2007, we continue our collaboration and our efforts to manipulate ''E. coli'' into mathematics problem solvers as we refine our efforts with the hin/hix mechanism to explore another mathematics problem, the Hamiltonian Path Problem. This problem was the subject of a groundbreaking paper by Adelman in 1994 (citation below) where a unique Hamiltonian path was found in vitro for a particular directed graph on seven nodes. We propose to make progress toward solving the particular problem in vivo.

 

[[Image:AdelmanGraph.JPG|thumb|300px|center|The Adleman graph.]]
 
[[Image:HamiltonianGraph.PNG|thumb|700px|center|A graph implemented on a plasmid.]]

|}

Davidson Missouri W/Resources and Citations

2007-08-09T15:21:38Z

Amshoecraft:

Davidson Missouri W/Backwards promotion and read-through transcription

2007-08-09T15:20:49Z

Amshoecraft:

Davidson Missouri W/Traveling Salesperson Problem

2007-08-09T15:20:08Z

Amshoecraft:

Davidson Missouri W/Controlling Expression

2007-08-09T15:19:22Z

Amshoecraft:

Davidson Missouri W/Gene splitting

2007-08-09T15:18:25Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>
<hr>

We have selected 4 genes to split. We will use our [http://gcat.davidson.edu/iGEM07/genesplitter.html online] gene splitting [[Davidson Missouri W/Web tool| web tool]] to choose the PCR primers. Davidson will produce these 4 split genes and test each one.

# [[Davidson Missouri W/Gene splitting#Kanamycin|Kanamycin Nucleotidyltransferase]]
# [[Davidson Missouri W/Gene splitting#RFP|Red Fluorescent Protein]]
# [[Davidson Missouri W/Gene splitting#CAT|Chloramphenicol Acetyltransferase]]
# [[Davidson Missouri W/Gene splitting#Cre|Cre Recombinase]]
 
[[Davidson Missouri W|Return to DMW main page]]
 
=The Genes=
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"
|-
!style="color: red; background-color: black;" width="5%"| Gene
!style="color: red; background-color: black;" width="65%"| Description
!style="color: red; background-color: black;" width="30%"| Graphic
|-

|style="color: black; background-color: red;" align="center"|Kanamycin Nucleotidyltransferase
|
One gene our team will be using as a node in our Hamiltonian Path problem is Kanamycin resistance translated in the form of Kanamycin nucleotidyltransferase (KNTase). The antibiotic Kanamycin, once in the cytosol of E.Coli, inhibits protein synthesis by interacting with the “decoding” region in the small ribosomal subunit RNA.(Sambrook and Russel, 2001) The KNTase enzyme, as a member of the aminoglycoside phosphotransferase (APH) enzyme family, blocks Kanamycin’s ability to inhibit protein synthesis by transferring a nucleoside monophosphate (adenyl) group from Mg2+-ATP to the 4’ hydroxyl group of Kanamycin, inhibiting its ability to bind to the srRNA.
[http://www.ingentaconnect.com/content/els/00452068/1999/00000027/00000005/art91144 1]

Our goal was to insert a hix site (a polar molecule) in an area of KNTase protein that would not interfere with its ability to inhibit Kanamycin. We looked at mutational analysis of KNTase and other aminoglycoside phosphotransferase enzymes to determine which aspects of KNTase’s structure were integral to its function and therefore not an ideal site for hix site insertion. KNTase is a dimer consisting of 253 amino acids in the molecule [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 3]. In looking at conserved structures in the APH family we took into consideration that:

-Substitution of AA 190 caused 650-fold decrease in enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]

-AA 190 is involved in catalysis [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]

-AA 195 and 208 are involved in Mg2+ binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htmv 5]

-Mutant Enzymes 190, 205, 210 all showed changes in mg+2 binding from the WT [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]

-Substitution of AA 210 (conserved) reduced enzyme activity [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]

-AA 166 serves to catalyze reactions involving ATP [http://www.bioscience.org/1999/v4/d/perlin/fulltext.htm 2]

-AA 44 is involved in ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]

-AA 60 is involved in orientation of AA 44 and ATP binding [http://www.bioscience.org/1999/v4/d/wright/fulltext.htm 5]

-We did not consider any Amino Acids near the N or C terminus

-We did not consider any residues near ß-sheets or ∂-helices close to the active site because hydrogen bonding plays an active role in substrate stabilization and the polarity of our hix site could disrupt the secondary structure and therefore the hydrogen bonding ability of KNTase)

|align="center"| [[Image:KNTase_hix_cut.png]] The yellow bands at the top and bottom of the molecule denotes hix site insertion

We decided to insert our hix sites at the 125 AA of each monomer due to their distance from each other, active site secondary structure, N or C terminus, and lack of any previous mutational analysis proving its function as integral.
|-

|style="color: black; background-color: red;" align="center"|DsRed - Red Fluorescent Protein

|
We use genes to represent the nodes on our Hamiltonian path. One of the essential features of these genes is that they can tolerate the insertion of a Hix site. It has been previously demonstrated that GFP fluoresces despite a Hix insertion. Another glowing protein, [http://parts.mit.edu/registry/index.php/Part:BBa_E1010 RFP] (from [http://www.ncbi.nlm.nih.gov/Taxonomy/Browser/wwwtax.cgi?id=86600 ''Discosoma sp.'']), is a candidate for use in our path. Although its DNA sequence is markedly different from GFP's, it has some amino acid similarity and a remarkable structural similarity. Both proteins have a Beta-barrel structure which surrounds an internal chromophore.

Inserting 13 amino acids into a protein can potentially disrupt its ability to function. It is thus essential to find an insertion point that does not interfere with the protein's function. Fortunately, the similarity between GFP and RFP allows us to make a highly educated guess for where to insert. RFP's amino acid position 154 is homologous to GFP's amino acid position 157, which is where GFP was split. This is therefore our best guess for where to insert the Hix site.

|align="center"|[[Image:Rfp_hix_insertion_point.jpg|200px]]
|-

|style="color: black; background-color: red;" align="center"|Chloramphenicol Acetyltransferase
|[http://parts.mit.edu/registry/index.php/Part:BBa_P1004 Chloramphenicol Acetyltransferase] was one of the genes we chose as a node for our Hamiltonian Path. It is a bacterial gene that neutralizes the effect of an antibiotic, Chloramphenicol, by transferring acetyl groups to Chloramphenicol and changes its shape into a harmless form.

The specific Chloramphenicol Acetyltransferase gene we are using comes from the plasmid PSV2CAT whose original source is an ''E. coli'' transposable element Tn9 (Sambrook, 2001) Its PDB ID# is [http://www.pdb.org/pdb/explore/explore.do?structureId=1PD5 1PD5].

I have chosen to insert my hixC site between amino acid 52 and 53. I chose this point because it is away from the active site of the protein, the point that contains the catalytic binding sites and allow the recognition and binding of the substrate. It is important for the insertion point to be away from the active site because we do not want the overall function and structure of the protein to be destroyed in the process of splitting. We want to split at a point where the two halves of the protein cannot work as single units, but once a hixC site has been inserted, and the two halves are brought back together, the protein displays its original function.

|align="center"|[[Image: Chlor.jpg|200px]] The structure of a type I Chloramphenicol Acetyltransferase used in the BioBrick Registry.
|-

|style="color: black; background-color: red;" align="center"|Cre Recombinase
|We will also attempt to insert a hixC site into the Cre Recombinase gene. Cre Recombinase binds as a dimer to a specific sequence of DNA called a ''loxP'' site. If two ''loxP'' sites are facing in opposite orientations, then Cre Recombinase will flip the section of DNA in between. If two ''loxP'' sites are facing in the same orientation, then Cre Recombinase will excise the DNA in between, creating a new plasmid.

In researching Cre Recombinase, we found that the gene had already been split by another lab. [http://www3.interscience.wiley.com/cgi-bin/abstract/104558885/ABSTRACT] In the study done by Casanova et al, two independent but overlapping sections of the Cre Recombinase gene were placed in separate locations along an E. Coli chromosome. When translated, the two overlapping halves of the Cre Recombinase protein bound together and formed a functional Cre Recombinase protein.

In order for Casanova et al's split protein to be functional, the overlapping section of the bound protein at the split site presumably could not significantly hinder the protein’s ability to bind to ''loxP'' sites or recombine DNA segments. With that in mind, we investigated the same region split by Casanova et al. as the prime candidate for the insertion of a hixC site.

The site that was eventually chosen reflects both the protein structure shown to the right and the previous research done in the Casanova lab. We believe that amino acids 190-191 along the Cre Recombinase protein are unlikely to play a significant role in the functioning of the protein, thus we decided on this location for the insertion of our hixC site.

Figure 1 on the right depicts a monomer of Cre Recombinase bound to a DNA strand that it is about the cut. Our split site is highlighted in yellow and can be seen far away from the active site of the molecule.

Figure 2 on the right depicts two dimers of Cre Recombinase coming come together to cut DNA at two ''loxP'' sites. The site of our hixC insertion is highlighted in yellow on each molecule and can be seen far away from the active site.

|align="center"|[[Image:Cre_recombinase_monomer1.png|200px]] 
Figure 1

[[Image:Cre_recombinase_tetramer1.png|200px]] 
Figure 2

Davidson Missouri W/Solving the HPP in vivo

2007-08-09T15:17:34Z

Amshoecraft:

Davidson Missouri W/Background Information

2007-08-09T15:16:49Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

In 1994 Adleman developed a system to solve the Hamiltonian Path problem using DNA ''in vitro''. We have implemented a bacterial system to solve Hamiltonian Path problems ''in vivo''. Our bacterial computer works by taking advantage of the Hin Recombinase protein and ''HixC'' sites to perform a "flipping" operation. By strategically placing ''HixC'' sites on a plasmid, along with reporter genes, we can simulate paths on a graph through flipping.

=The Hin Recombinase/''HixC'' System Revisited=
''Salmonella typhimurium'' is a bacterium which moves using flagella. Depending on its environment, it expresses different sets of surface proteins on its flagella. It is able to change this expression through the use of Hin Recombinase and ''HixC'' sites. The Hin Recombinase enzyme catalyzes the inversion of DNA that lies between a pair of ''HixC'' sites. By flipping DNA segments between ''HixC'' sites ''S. typhimurium'' can express alternate flagellar surface proteins.

# Given a segment of DNA, flanked by ''HixC'' sites (blue arrow): [[Image:hinhix1.png|thumb|none|800px|Figure 1.]]
# Two dimers of Hin Recombinase protein attach to a pair of ''HixC'' sites around the DNA segment. [[Image:hinhix2.png|thumb|none|800px|Figure 2.]]
# The DNA segment between the pair of ''HixC'' sites is inverted. Note that the green arrow is unaffected. [[Image:hinhix3.png|thumb|none|800px|Figure 3.]]

=Flipping Pancakes=
In the 2006 iGEM competition, [http://parts.mit.edu/wiki/index.php/Davidson_2006 Davidson] and [http://parts.mit.edu/wiki/index.php/Missouri_Western_State_University_2006 Missouri Western] used Hix Recombinase and ''HixC'' to model a mathematical problem, called the Pancake Flipping problem. The problem is the following: given a stack of pancakes which are burnt on one side and golden on the other, and two spatulas, what is the minimum number of flips required to sort the stack by pancake size and with all burnt sides facing downwards?

[[Image:pancake_sorting.gif|frame|none|How many flips does this take?]]

Using mathematical models it is possible to compute these estimates for small stacks. However, adding pancakes to a stack increases the number of possible permutations non-linearly. The number of possible stacks of ''n'' pancakes is equal to: 2^n (n!). Thus traditional computers are not well-suited for computations involving large pancake stacks.

However, it is possible to model pancake flipping using bacteria. If each pancake is given an identification number, along with a sign designating its orientation, then this can be stated equivalently using genes. Thus the following images show equivalent notations for pancake stacks:

[[Image:pancakes_compare.gif|frame|none|A stack of pancakes.]]

[[Image:DNA_arrows.gif|frame|none|Genes on a plasmid.]]

By taking advantage of this notation it is possible to use bacteria as computers to solve pancake-flipping problems.

=Why Use Bacteria?=

Although we have demonstrated how it is possible to solve mathematical problems using bacteria, it may not be obvious why this is helpful. Due to the exponential increase in problem size that arises from a linear increase in pancake stack size, traditional computers are not good at solving large pancake problems. However, bacterial computers are not affected as much by this problem. If each bacterium contains several plasmids, each plasmid is a computer, and a single flask of bacteria contains millions of bacteria, then it is trivial to produce millions of computers. Each computer will be acting in parallel with the others, drastically reducing the amount of time required to reach a solution. The use of bacterial computers is thus a way to allow us to solve computational problems which traditional computers cannot.

Davidson Missouri W/Mathematical Modeling

2007-08-09T15:13:59Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Fpospic.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]

true positives = 384
false positives = 1,362

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]

true positives = 10,321,920
false positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

File:Fpospic.jpg

2007-08-09T15:12:04Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-09T15:09:08Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]

true positives = 384
false positives = 1,362

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]

true positives = 10,321,920
false positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W/Mathematical Modeling

2007-08-09T15:08:24Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpVTgraph.m 1. False positives for the 8 edge / 5 node graph shown above]

true positives = 384
false positives = 1,362

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/davidson85Iweighter.m 2. Counter Program for the 8 edge / 5 node graph]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/adelman147.m 2. Adelman's false positives with 14 edges / 7 nodes]

True Positives = 10,321,920
False Positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W

2007-08-09T14:43:46Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Software|Software]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>
 

[[Image:DMW-1.jpg|300px|center]]

<center>
=The Team=
</center>
{| border="1" cellpadding="5" cellspacing="0" align="center" width="100%"
|-
! style="color: white; background-color: black;"| The Team
! style="color: white; background-color: black;" | The Faculty
! style="color: white; background-color: black;" | Team Logos
! style="color: white; background-color: black;" | Group Photo
|-

|style="color: black; background-color: red;" align="center"| '''Davidson'''

[[Davidson Missouri W/Oyinade Adefuye|Oyinade Adefuye]]
 
[[Davidson Missouri W/Will DeLoache|Will DeLoache]]
 
[[Davidson Missouri W/Jim Dickson|Jim Dickson]]
 
[[Davidson Missouri W/Andrew Martens|Andrew Martens]]
 
[[Davidson Missouri W/Amber Shoecraft|Amber Shoecraft]]
 
[[Davidson Missouri W/Mike Waters|Mike Waters]]


|style="color: black; background-color: red;" align="center"|

[[Davidson Missouri W/A. Malcolm Campbell|A. Malcom Campbell]]
 
[[Davidson Missouri W/Karmella Haynes|Karmella Haynes]]
 
[[Davidson Missouri W/Laurie Heyer|Laurie Heyer]]


|style="color: black; background-color: white;" align="center"|
[[Image:DavidsonLogo.gif]]

|style="color: black; background-color: white;" align="center"|
[[Image:Team1.jpg|thumb|300px]]

|-

|style="color: black; background-color: gold;" align="center"|'''Missouri Western'''

[[Davidson Missouri W/Jordan Baumgardner|Jordan Baumgardner]]
 
[[Davidson Missouri W/Tom Crowley|Tom Crowley]]
 
[[Davidson Missouri W/Lane H. Heard|Lane H. Heard]]
 
[[Davidson Missouri W/Nickolaus Morton|Nickolaus Morton]]
 
[[Davidson Missouri W/Michelle Ritter|Michelle Ritter]]
 
[[Davidson Missouri W/Jessica Treece|Jessica Treece]]
 
[[Davidson Missouri W/Matthew Unzicker|Matthew Unzicker]]
 
[[Davidson Missouri W/Amanda Valencia|Amanda Valencia]]


|style="color: black; background-color: gold;" align="center"|

[[Davidson Missouri W/Todd Eckdahl|Todd Eckdahl]]
 
[[Davidson Missouri W/Jeff Poet|Jeff Poet]]


|style="color: black; background-color: white;" align="center"|[[Image:MWLogo.gif]]

|style="color: black; background-color: white;" align="center"|
|-

|}

 
[[Image:Team_graph.jpg|center|thumb|500px|A Human Representation of Adleman's Graph (see below)]]
 

<center>

=Our Project=
</center>

{| border="1" cellpadding="5" cellspacing="0" align="center" width="90%"
|-
! style="color: black; background-color: red;" width="20%"| In Depth
! colspan="3" style="color: black; background-color: red;" width="60%"| Overview
|-
|style="color: black; background-color: black;" align="center"|
[[Davidson Missouri W/Background Information|Background Information]]
 
[[Davidson Missouri W/Solving the HPP in vivo|Current Project: Solving the Hamiltonian Path Problem ''in vivo'']]
 
[[Davidson Missouri W/Probability and Statistics|Probability and Statistics]]
 
[[Davidson Missouri W/Gene splitting|Gene Splitting]]
 
[[Davidson Missouri W/Controlling Expression|Controlling Expression]]
 
[[Davidson Missouri W/Traveling Salesperson Problem|Traveling Salesperson Problem]]
 
[[Davidson Missouri W/Backwards Promotion and read-through transcription|Backwards Promotion and Read-Through Transcription]]
 
[[Davidson Missouri W/Resources and Citations|Resources and Citations]]
 
|Hamiltonian Path Problem
As a part of iGEM2006, a combined team from Davidson College and Missouri Western State University reconstituted a hin/hix DNA recombination mechanism which exists in nature in Salmonella as standard biobricks for use in ''E. coli''. The purpose of the 2006 combined team was to provide a proof of concept for a bacterial computer in using this mechanism to solve a variation of The Pancake Problem from Computer Science. This task utilized both biology and mathematics students and faculty from the two institutions.

For 2007, we continue our collaboration and our efforts to manipulate ''E. coli'' into mathematics problem solvers as we refine our efforts with the hin/hix mechanism to explore another mathematics problem, the Hamiltonian Path Problem. This problem was the subject of a groundbreaking paper by Adelman in 1994 (citation below) where a unique Hamiltonian path was found in vitro for a particular directed graph on seven nodes. We propose to make progress toward solving the particular problem in vivo.

 

[[Image:AdelmanGraph.JPG|thumb|300px|center|The Adleman graph.]]
 
[[Image:HamiltonianGraph.PNG|thumb|700px|center|A graph implemented on a plasmid.]]

|}

Davidson Missouri W/Mathematical Modeling

2007-08-09T14:42:57Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Mathematical Modeling| Mathematical Modeling]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

True Positives = 46,080
False Positives = 298,174

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

True Positives = 10,321,920
False Positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W/Mathematical Modeling

2007-08-09T14:41:48Z

Amshoecraft: Davidson Missouri W/Probability and Statistics moved to Davidson Missouri W/Mathematical Modeling

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

True Positives = 46,080
False Positives = 298,174

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

True Positives = 10,321,920
False Positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W/Probability and Statistics

2007-08-09T14:41:48Z

Amshoecraft: Davidson Missouri W/Probability and Statistics moved to Davidson Missouri W/Mathematical Modeling

#redirect [[Davidson Missouri W/Mathematical Modeling]]

Davidson Missouri W/Mathematical Modeling

2007-08-09T14:23:34Z

Amshoecraft: /* True Positives / False Positives */

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a "teleport" which causes this path to be a false positive. Teleporting occurs when an edge entering a node is followed by an edge leaving from a different node. Below you can see an extra edge that is highlighted, representing the teleport. In this example, the edge from 4 to 3 is followed by the edge from 4 to 5.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

True Positives = 46,080
False Positives = 298,174

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

True Positives = 10,321,920
False Positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W/Mathematical Modeling

2007-08-09T14:03:08Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a teleport which causes this path to be a false positive. Also, below you can see with in the PCR Fragment Length there is an extra edge that is highlighted that represents the teleport.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

True Positives = 46,080
False Positives = 298,174

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

True Positives = 10,321,920
False Positives = 168,006,848

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

Davidson Missouri W/Mathematical Modeling

2007-08-09T13:59:29Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

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

[[Image:MarkovChaingraph4nod3edg.jpg]]

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]

 
= True Positives / False Positives =

[[Image:5_node-wiki.jpg]] Figure 1

True positives are the Hamiltonian Path represented in the above graph with solid red arrows and below as the PCR Fragment Length where the edges after the Hamiltonian path can be arranged in any order.

[[Image:True_positive.jpg]]

A false positive is represented in the graph above with the solid red arrows and the dotted red arrow showing a teleport which causes this path to be a false positive. Also, below you can see with in the PCR Fragment Length there is an extra edge that is highlighted that represents the teleport.

[[Image:Falsep.jpg]]

[[Image:Pcrlength.jpg]]

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]

Below are two graphs that show how quickly graphs can be complex so it makes the Hamiltonian Path harder to detect. Also, from these graphs you can tell that even though the graphs are very complex that there is still a 5% change of detecting a Hamiltonian Path or a true positive.

[[Image:Positivenodedg.jpg]] [[Image:Truetotalpos.jpg]]

=Possion Model For the Number of Plasmids=

'''How many E.coli computers?'''

Question: If a Hamiltonian Path exists in the graph, how many E.coli computers do we need to have working on the problem to be highly confident that at least k of our computers will find it?

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. Note: This has now been shown to be true but it needs to be stated that our math relies on it.

If this is the case then our E.coli computers will be equally likely to have flipped into each possible signed ordering of edges by the time we screen our results. For more details on this see our section answering the question does starting orientation matter?

We can use a cumulative Poisson distribution to answer this question.

Answer: The Poisson distribution gives the probability of k occurrences when the expected number of occurrences is λ as (e^-λ)*(λ^k)/(k!). By taking 1 minus the sum of the Poisson probabilities from 0 to k-1 we get the cumulative probability of at least k occurrences.

For example examine the Adleman graph. It has 14 edges and 7 nodes. This means that a Hamiltonian Path is represented in our plasmids by 6 edges in the proper order and orientation followed by 8 edges in any order and in any orientation.

Thus there are 8!*2^8 orderings that are true positives and 14!*2^14 possible orderings. The probability of any one plasmid holding a true positive is then 8!*2^8 / 14!*2^14. If we have m plasmids, λ= m*8!*2^8 / 14!*2^14.

Now if we want to know the probability of at least one true positive in m plasmids, we use k =1 and the expression becomes 1-(e^-(m*8!*2^8/14!*2^14)) as the summand collapses to the case where k=0 and (λ^0)/(0!) then equals 1.

We can then solve for m depending on how confident we want to be. If we use
m=1 billion plasmids then we expect to find the Hamiltonian Path when one exists 99.92% of the time.

1 billion E.coli computers fit conveniently into 1 mL of culture.

Using this statistical method we made a chart showing the probability of finding true positives based on the number of plasmids.

[[Image:Plasmidsneeded.jpg]]

File:Truetotalpos.jpg

2007-08-09T13:24:21Z

Amshoecraft:

File:Positivenodedg.jpg

2007-08-09T13:22:33Z

Amshoecraft:

File:Pcrfrag.jpg

2007-08-09T13:21:33Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T20:48:02Z

Amshoecraft:

File:Falsep.jpg

2007-08-08T20:43:05Z

Amshoecraft:

File:Pcrlength.jpg

2007-08-08T20:41:46Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T20:35:10Z

Amshoecraft:

File:True positive.jpg

2007-08-08T20:15:23Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T19:48:21Z

Amshoecraft:

File:Plasmidsneeded.jpg

2007-08-08T19:39:54Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T19:26:42Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:55:56Z

Amshoecraft:

File:MarkovChaingraph4nod3edg.jpg

2007-08-08T16:51:41Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:48:36Z

Amshoecraft:

File:5 node-wiki.jpg

2007-08-08T16:44:34Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:41:04Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:37:58Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:29:04Z

Amshoecraft:

Davidson Missouri W/Mathematical Modeling

2007-08-08T16:17:04Z

Amshoecraft:

<center>[[Davidson Missouri W| Home]] | [[Davidson Missouri W/Background Information| Background Information]] | [[Davidson Missouri W/Solving the HPP in vivo| Current Project: Solving the Hamiltonian Path Problem ''in vivo'']] | [[Davidson Missouri W/Probability and Statistics| Probability and Statistics]] | [[Davidson Missouri W/Gene splitting| Gene Splitting ]] | [[Davidson Missouri W/Controlling Expression| Controlling Expression ]] | [[Davidson Missouri W/Traveling Salesperson Problem| Traveling Salesperson Problem ]] | [[Davidson Missouri W/Backwards promotion and read-through transcription| Backwards Promotion and Read-Through Transcription]] | [[Davidson Missouri W/Resources and Citations|Resources and Citations]]</center>

<hr>

=Markov Chain Model For Flipping=

The false positive programs will tell how many false positives there are in Adelman’s graph without two edges (12) and the other is for the original graph with 14 edges. To develop the program we first made a list of all the different ways to make each number represented in the path and numbered them. We also, numbered each of the edges. we took the numbered edges and made vectors of the ways that each number can be represented at the top of the program.

First we made a loop to make sure that MATLAB picks up at least one representation of each number. Then the perms function is used to arrange all the representations of each number except the promoter in all the different ways and call it matrix g.Then you want to find all the rows where the last number of each row of the matrix ends with the number that represents the terminator. Then using the ord function all the different ways of putting the two promoters in the front of each row is developed. Now the program changes the label of the numbers from there number representation number to there edge number where the label goes from 1 to 2 and transposes them. The way that the program lays out the numbers need to be transposed again so we called that matrix sl. Now an if statements were made for the total number of repeats for each row equal to the number of repeats next to each other. The counter is used to find the total number of repeats that are next to each other. For all the number of edges left after all of the repeats are taken out we replaced those with zeros. Now we had to make a vector of ones that will be from 1 to the length of sl. What we call usl is where we get rid of one of the repeated numbers that’s next to each other because one number shows the back half and front half of the gene. Now the new usl is relabeled and includes the numbers for the edges with the promoter at the beginning of each and the terminator at the end of each with the zeros replacing the edges that are after the terminator.

If there is a row in matrix g that does not end with a terminator then we use the command elseif and add a terminator to each of those rows. Since there are two terminators then the program goes through the process one time with the first terminator and another time with the other terminator making these rows longer than if they originally had a terminator at the end. After this whole process all the rows start with a promoter and end with a terminator and have zeros after the terminator is represented.

At the end of the program we print out the total number of arrangements of false positives before the zeros after the terminator are replaced with the extra edges. Also, the rows that are not repeated are printed out. Now the program finds all the rows that have terminators starting in column 8 to 12. We found how many ways we can arrange the remaining edges depending on where the terminator is and take that number and multiply by the amount of times the terminator is in each spot and add them together for each column number. This number gives the number of false positives for a Hamiltonian path.

MATLAB programs used to find the false positives:

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpalmostadelman.m 1. Adelman's False Positives with 12 nodes]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpadelman.m 2. Adelman's False Positives with 14 nodes]

[http://gcat.davidson.edu/iGEM07/For_Missouri_Western/fpweighter.m 3. Counter Program for Adelman's False Positives]
 
= True Positives / False Positives =

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

=Possion Model For 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))

Davidson Missouri W/Amber Shoecraft

2007-07-13T19:35:51Z

Amshoecraft:

I graduated in Spring of 2007 from Johnson C. Smith University in Charlotte,NC, with a Bachlors of Science with a concentration in Mathematics. In fall of 2007, I will start graduate school at the Ohio State University in Columbus,Ohio where I will major in Statistics. My goal is to get a PhD in Statistics and then become a professor or be a statistician for a company.

[[Image:Amber2.jpg]]Amber Shoecraft