Team:Aberdeen Scotland/modeling/pde

From 2009.igem.org

(Difference between revisions)
(Feasibility of developing Numerical Method)
 
(124 intermediate revisions not shown)
Line 8: Line 8:
A PDE model was an excellent “next step” for our modelling effort – and although a physically meaningful model could not be generated; the following describes a concise modelling methodology which would merit implementation outside of iGEM – or indeed, in future iGEM competitions.
A PDE model was an excellent “next step” for our modelling effort – and although a physically meaningful model could not be generated; the following describes a concise modelling methodology which would merit implementation outside of iGEM – or indeed, in future iGEM competitions.
-
The Keller-Segel Chemotaxis system is a set of two coupled Nonlinear PDE’s; Parabolic except for a mixed Hyperbolic-Elliptic term in the cross-diffusive flux.  The terms “Parabolic”, “Hyperbolic” and “Elliptic” refer to the number of boundary conditions the system must satisfy – the dependence on which defines (or “sets”) the behaviour of the system.
+
The Keller-Segel Chemotaxis system is a set of two coupled Nonlinear PDE’s; ostensibly Parabolic except for a mixed Hyperbolic-Elliptic term in the cross-diffusive flux.  The terms “Parabolic”, “Hyperbolic” and “Elliptic” refer to the number of boundary conditions the system must satisfy – the dependence on which defines (or “sets”) the behaviour of the system.
-
The Keller-Segel system was perfect for modelling our PicoPlumber modules, inasmuch as Quorum Sensing and Internal Dynamics could be effectively expressed in its formulation [1].
+
 
 +
[[Image:PDE1.gif|center]]
 +
 
 +
Where [[Image:var34.gif]] is the cross-diffusive flux
 +
 
 +
The Keller-Segel system was perfect for modelling our PicoPlumber modules, inasmuch as Quorum Sensing could be effectively integrated into the formulation<sup><b>[1]</b></sup>.  This allowed the advantage of analysing the dynamical evolution of the system in space & time - and in regard to the Internal Dynamics.
The following is an account of our researches into utilising these powerful Mathematical tools to describe our system.
The following is an account of our researches into utilising these powerful Mathematical tools to describe our system.
Line 18: Line 23:
== One-Dimensional Diffusion Equation ==
== One-Dimensional Diffusion Equation ==
-
As PDE’s are a challenging and actively-researched topic in Mathematics [4],[5]; our modelling effort began by solving a much simpler problem by way of introduction to the field.
+
As PDE’s are a challenging and actively-researched topic in Mathematics<sup><b>[2-3]</b></sup>; our modelling effort began by solving a much simpler problem by way of introduction to the field.
 +
 
 +
The one-dimensional Heat Equation is the classic introduction to Partial Differential Equations.  It was modelled by utilising an Implicit Finite Difference method of our own composition.  This allowed us to attain an aptitude for tackling the more difficult Keller-Segel system to come.
 +
 
 +
The Heat Equation and the Diffusion Equation of our chemo-attractant shared the same mathematical formulation – differing in fact, by the choice of the constant <i>k</i> – and so this introduction still retained a Biological pertinence.
 +
 
 +
 
 +
 
 +
[[Image:PDE_implicit.gif|center]]
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
== Keller-Segel System for Chemotaxis ==
 +
 
 +
As mentioned above, the Keller-Segel System for Chemotaxis is the set of coupled Nonlinear PDE's which describe chemotactic motion. The mixed Hyperbolic-Elliptic term endows the system with rich behaviour – but also renders it insoluble by elementary Numerical Methods<sup><b>[4]</b></sup>.
 +
 
 +
In searching for a more advanced numerical method, <i>Discontinuous Galerkin Finite Elements</i> were found in Systems Biology literature<sup><b>[4]</b></sup>. to have successfully modelled the system and identified parametric instabilities.
 +
 
 +
In their award-winning paper<sup><b>[5]</b></sup>. , Hillen and Painter describe augmentations to the standard Keller-Segel System, hereafter referred to as the "Minimal Model".  These augmentations account for effects such as quorum sensing, nonlinear diffusion and cell-growth & multiplication.  The following documents the theoretical knowledge necessary to create a numerical scheme to solve the system - which may be undertaken on a "Next steps" basis.
 +
 
 +
Comment is made on the extension of the Minimal Model to incorporate quorum sensing and cell-growth & multiplication - so as to be fully representative of the PicoPlumber system - in the final subsection of this page.
 +
 
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
=== Minimal Model ===
 +
 
 +
The Chemotactic Minimal Model is the simplest "chassis" for describing a bacterial population chemotaxing towards a chemoattractant. It is of the form
 +
 
 +
[[Image:PDE1.gif|center]]
 +
 
 +
where [[Image:var3.gif]] is the chemotactic sensitivity, [[Image:var5.gif]] the bacterial density, [[Image:var4.gif]] the concentration of the chemoattractant and [[Image:var1.gif]], [[Image:var2.gif]] their respective time derivatives.
 +
 
 +
In Ephsteyn & Kurganov<sup><b>[4]</b></sup>, the aforementioned <i>Discontinuous Galerkin Finite Element Method</i> is applied to successfully solve the system.  The following will provide an abridged summary of the method, covering all elements necessary to implement it.
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
=== Theoretical Considerations ===
 +
 
 +
The Finite Element Method is a numerical technique for the solution of PDE's by discretising the domain over which the PDE is solved into finite "elements".  The discretised domain is then termed the <i>mesh</i>.  Elements are interpolated by polynomial <i>basis functions</i> which serve to approximate the equation over the element without allowing errors in intermediate calculations to accumulate and render the final output meaningless.
 +
 
 +
<i>Discontinuous Galerkin</i> methods are an augmented family of Finite Element Methods developed by the Russian Engineer, Boris Galerkin.  They are superior to other finite element methods for several reaons, including - but not restricted to - local, element-wise mass conservation and flexibility to choose non- and high order polynomial bases.  Element-wise mass conservation is important, and naturally the bacteria must be able to "exist" computationally through all space & time.
 +
 
 +
To solve the Minimal Model we require a Mesh upon which to discretise the system and a reformulation of the Convection-Reaction-Diffusion to render it soluble by Discontinuous Galerkin methods.
 +
 
 +
The following documents the theoretical considerations necessary to obtain a robust solution. Ephsteyn & Kurganov<sup><b>[4]</b></sup> must be fully credited for their description of the numerical scheme outlined below - which is expanded upon concomitantly with the considerations of Hillen & Painter<sup><b>[1]</b></sup>- in a manner so as to provide clarity and insight to the reader.
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
==== Mesh Generation ====
 +
 
 +
The method begins by defining a Sobolev space [[Image:var14.gif]] over the domain [[Image:var31.gif]] upon which the mesh is specified. A Sobolev space is a Linear Space of polynomial functions - strictly a Banach space of square-integrable functions - endowed with the Sobolev s-norm
 +
 
 +
[[Image:PDE16.gif|center]], [[Image:PDE17.gif|center]]
 +
 
 +
 
 +
For s a labelling-index and [[Image:var16.gif]] an element of the discrete space of discontinuous piecewise polynomials of degree [[Image:var32.gif]] as a function of the nondegenerate quasi-uniform rectangular subdivisions [[Image:var13.gif]]
 +
 
 +
[[Image:PDE15.gif|center]]
 +
 
 +
And for those w in the Sobolev space such that for w evaluated at an arbitary element [[Image:var33.gif]]; w is in the space of polynomials of degree [[Image:var32.gif]] over [[Image:var16.gif]], styled [[Image:var15.gif]]
 +
 
 +
While this may seem mathematically "verbose", the mesh itself and the non-degeneracy of the elements therein can be seen in the diagram of [[Image:var35.gif]] below - whilst the Linear space constructions remain abstract
 +
 
 +
[[Image:fea_mesh2.gif|center]]
 +
 
 +
This rigourously defines the mesh upon with the <i>Discontinuous Galerkin</i> method solves the Keller-Segel system - which is the <u>key component</u> of the algorithm.
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
==== Convection-Reaction-Diffusion Reformulation ====
 +
 
 +
Algebraically manipulating the Minimal Model by defining the vector [[Image:gradc.gif]], we obtain the variation
 +
 
 +
[[Image:PDE7.gif|center]]
 +
 
 +
which is in a form soluble by <i>Discontinous Galerkin</i> methods.  This form of the Minimal Model can in turn be considered as a Convection-Reaction-Diffusion system<sup><b>[4]</b></sup>
 +
 
 +
[[Image:PDE9.gif|center]]
 +
 
 +
where the boldface 3-vectors are [[Image:u_matrix.gif]], [[Image:fu_matrix.gif]], [[Image:gu_matrix.gif]] and [[Image:ru_matrix.gif]].
 +
 
 +
Ephsteyn & Kurganov<sup><b>[4]</b></sup> however, report that such a re-formulation is prone to severe instabilities in the transition from a Hyperbolic region to an Elliptic one - upon implementation of a high-order Numerical Method.  To implement the Discontinuous Galerkin method we therefore rewrite the system as
 +
 
 +
[[Image:chem_system_dg.gif|center]]
 +
 
 +
subject to the boundary conditions [[Image:PDE13.gif]], [[Image:PDE4.gif]].  This may also be considered as a Convection-Reaction-Diffusion system of the form
 +
 
 +
[[Image:PDE14.gif|center]]
 +
 
 +
once again where the boldface 3-vectors in this instance are [[Image:dg_sys_q.gif]] where [[Image:dg_sys_fq.gif]], [[Image:dg_sys_gq.gif]] are the fluxes and [[Image:dg_sys_rq.gif]] is the reaction term. It should similarly be noted that k=1 is a constant and the convective part of the system is requisitely Hyperbolic.
 +
 
 +
This renders the Minimal Model soluble by a <i>Discontinuous Galerkin</i> numerical scheme as proposed by Ephsteyn & Kurganov<sup><b>[4]</b></sup>.
 +
 
 +
Together, the Mesh and the Convection-Reaction-Diffusion equation form the <u>complete theoretical basis</u> upon which the program is to be developed.
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
=== Analytic Form of Solution ===
 +
 
 +
In the nomenclature defined above, a solution to the Keller-Segel System must take the form
 +
 
 +
[[Image:PDE28.gif|center]]
 +
 
 +
for some solution in the direct product space of the respective nondegenerate quasi-linear rectangular subdivisions [[Image:var13.gif]], satisfying the weak formulation of the Minimal Model
 +
 
 +
[[Image:timesolution.gif|center]]
 +
 
 +
where sums of the integrals are over [[Image:var13.gif]] and the set of interior edges [[Image:rho.gif]], which in turn are split up into horizontal & vertical edges - [[Image:rho_hor.gif]] and [[Image:rho_ver.gif]] respectively - of the rectangular boundary [[Image:var6.gif]].
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
== Feasibility of developing Numerical Method ==
 +
 
 +
As seen in the precending section. even the simplest of analytic solutions to the Keller-Segel System using the <i>Discontinuous Galerkin</i> method is distinctly non-trivial - and would require a high degree of technical proficiency and time to implement.  This was outwith the scope of our project, but were it to be attempted, would prove a robust and highly accurate means of collimating the individual PicoPlumber modelling modules.
 +
 
 +
Moreover, comment must be made on extensions to the basic Minimal Model "chassis" to incorporate effects such as quorum sensing and cell-growth & multiplication.  These augmentations are discussed thoroughly in Hillen & Painter<sup><b>[1]</b></sup> but would require a re-derivation of some of the results given on this page - assuming compatibility with the <i>Discontinuous Galerkin</i> methods, that is.
 +
 
 +
 
 +
<html>
 +
<table class="nav">
 +
<tr>
 +
<td>
 +
<a href="https://2009.igem.org/Team:Aberdeen_Scotland/hillinput"><img src="https://static.igem.org/mediawiki/2009/e/ed/Aberdeen_Left_arrow.png">&nbsp;&nbsp;Back to Hill Input Functions</a>
 +
</td>
 +
<td align="right">
 +
<a href="https://2009.igem.org/Team:Aberdeen_Scotland/chemotaxis">Continue to Chemotaxis&nbsp;&nbsp;<img src="https://static.igem.org/mediawiki/2009/4/4c/Aberdeen_Right_arrow.png"></a>
 +
</td>
 +
</tr>
 +
</table>
 +
</html>
 +
 
 +
{{:Team:Aberdeen_Scotland/break}}
 +
 
 +
== References ==
 +
 
 +
<b>[1]</b>  Hillen T, Painter KJ, <i>"A user's guide to PDE models for Chemotaxis"</i> J Math Biol. 2009 Jan;58(1-2):183-217. Epub 2008 Jul 15.
-
The one-dimensional Heat Equation is the classic introduction to Partial Differential EquationsIt was modelled by utilising an Implicit Finite Difference method of our own composition. This allowed us to attain an aptitude for the more difficult Keller-Segel system to come.
+
<b>[2]</b> Oxford Centre for Nonlinear PDEhttp://www.maths.ox.ac.uk/groups/oxpde/
-
The Heat Equation and the Diffusion Equation of our chemo-attractant shared the same mathematical formulation – differing in fact, by the choice of the constant k – and so this introduction was still retained a Biological pertinence.
+
<b>[3]</b> The Maxwell Institute: Centre for Analysis and Nonlinear PDE's. http://www.maxwell.ac.uk/PDEs/
-
== Title 3 ==
+
<b>[4]</b> Ephsteyn Y, Kurganov A, <i>New Interior Penalty Discontinuous Galerkin Methods for the Keller–Segel Chemotaxis Model</i>. J. Numer. Anal. Volume 47, Issue 1, pp. 386-408 (2008)
-
== Title 4 ==
+
 +
<b>[5]</b>  Faculty of 1000 Biology.  <i>"A user's guide to PDE models for Chemotaxis"</i> Importance recognition. http://f1000biology.com/article/id/1126950
{{:Team:Aberdeen_Scotland/footer}}
{{:Team:Aberdeen_Scotland/footer}}

Latest revision as of 23:09, 21 October 2009

University of Aberdeen iGEM 2009

Contents

Introduction

It was realised quite soon into the project that upon modelling the Inner Dynamics of the system, the individual modules could be collimated in to a single Partial Differential Equation – hereafter referred to as PDE – which would accurately describe the evolution of the system in space and time.

A PDE model was an excellent “next step” for our modelling effort – and although a physically meaningful model could not be generated; the following describes a concise modelling methodology which would merit implementation outside of iGEM – or indeed, in future iGEM competitions.

The Keller-Segel Chemotaxis system is a set of two coupled Nonlinear PDE’s; ostensibly Parabolic except for a mixed Hyperbolic-Elliptic term in the cross-diffusive flux. The terms “Parabolic”, “Hyperbolic” and “Elliptic” refer to the number of boundary conditions the system must satisfy – the dependence on which defines (or “sets”) the behaviour of the system.


PDE1.gif

Where Var34.gif is the cross-diffusive flux

The Keller-Segel system was perfect for modelling our PicoPlumber modules, inasmuch as Quorum Sensing could be effectively integrated into the formulation[1]. This allowed the advantage of analysing the dynamical evolution of the system in space & time - and in regard to the Internal Dynamics.

The following is an account of our researches into utilising these powerful Mathematical tools to describe our system.

One-Dimensional Diffusion Equation

As PDE’s are a challenging and actively-researched topic in Mathematics[2-3]; our modelling effort began by solving a much simpler problem by way of introduction to the field.

The one-dimensional Heat Equation is the classic introduction to Partial Differential Equations. It was modelled by utilising an Implicit Finite Difference method of our own composition. This allowed us to attain an aptitude for tackling the more difficult Keller-Segel system to come.

The Heat Equation and the Diffusion Equation of our chemo-attractant shared the same mathematical formulation – differing in fact, by the choice of the constant k – and so this introduction still retained a Biological pertinence.


PDE implicit.gif

Keller-Segel System for Chemotaxis

As mentioned above, the Keller-Segel System for Chemotaxis is the set of coupled Nonlinear PDE's which describe chemotactic motion. The mixed Hyperbolic-Elliptic term endows the system with rich behaviour – but also renders it insoluble by elementary Numerical Methods[4].

In searching for a more advanced numerical method, Discontinuous Galerkin Finite Elements were found in Systems Biology literature[4]. to have successfully modelled the system and identified parametric instabilities.

In their award-winning paper[5]. , Hillen and Painter describe augmentations to the standard Keller-Segel System, hereafter referred to as the "Minimal Model". These augmentations account for effects such as quorum sensing, nonlinear diffusion and cell-growth & multiplication. The following documents the theoretical knowledge necessary to create a numerical scheme to solve the system - which may be undertaken on a "Next steps" basis.

Comment is made on the extension of the Minimal Model to incorporate quorum sensing and cell-growth & multiplication - so as to be fully representative of the PicoPlumber system - in the final subsection of this page.


Minimal Model

The Chemotactic Minimal Model is the simplest "chassis" for describing a bacterial population chemotaxing towards a chemoattractant. It is of the form

PDE1.gif

where Var3.gif is the chemotactic sensitivity, Var5.gif the bacterial density, Var4.gif the concentration of the chemoattractant and Var1.gif, Var2.gif their respective time derivatives.

In Ephsteyn & Kurganov[4], the aforementioned Discontinuous Galerkin Finite Element Method is applied to successfully solve the system. The following will provide an abridged summary of the method, covering all elements necessary to implement it.

Theoretical Considerations

The Finite Element Method is a numerical technique for the solution of PDE's by discretising the domain over which the PDE is solved into finite "elements". The discretised domain is then termed the mesh. Elements are interpolated by polynomial basis functions which serve to approximate the equation over the element without allowing errors in intermediate calculations to accumulate and render the final output meaningless.

Discontinuous Galerkin methods are an augmented family of Finite Element Methods developed by the Russian Engineer, Boris Galerkin. They are superior to other finite element methods for several reaons, including - but not restricted to - local, element-wise mass conservation and flexibility to choose non- and high order polynomial bases. Element-wise mass conservation is important, and naturally the bacteria must be able to "exist" computationally through all space & time.

To solve the Minimal Model we require a Mesh upon which to discretise the system and a reformulation of the Convection-Reaction-Diffusion to render it soluble by Discontinuous Galerkin methods.

The following documents the theoretical considerations necessary to obtain a robust solution. Ephsteyn & Kurganov[4] must be fully credited for their description of the numerical scheme outlined below - which is expanded upon concomitantly with the considerations of Hillen & Painter[1]- in a manner so as to provide clarity and insight to the reader.

Mesh Generation

The method begins by defining a Sobolev space Var14.gif over the domain Var31.gif upon which the mesh is specified. A Sobolev space is a Linear Space of polynomial functions - strictly a Banach space of square-integrable functions - endowed with the Sobolev s-norm

PDE16.gif
,
PDE17.gif


For s a labelling-index and Var16.gif an element of the discrete space of discontinuous piecewise polynomials of degree Var32.gif as a function of the nondegenerate quasi-uniform rectangular subdivisions Var13.gif

PDE15.gif

And for those w in the Sobolev space such that for w evaluated at an arbitary element Var33.gif; w is in the space of polynomials of degree Var32.gif over Var16.gif, styled Var15.gif

While this may seem mathematically "verbose", the mesh itself and the non-degeneracy of the elements therein can be seen in the diagram of Var35.gif below - whilst the Linear space constructions remain abstract

Fea mesh2.gif

This rigourously defines the mesh upon with the Discontinuous Galerkin method solves the Keller-Segel system - which is the key component of the algorithm.

Convection-Reaction-Diffusion Reformulation

Algebraically manipulating the Minimal Model by defining the vector Gradc.gif, we obtain the variation

PDE7.gif

which is in a form soluble by Discontinous Galerkin methods. This form of the Minimal Model can in turn be considered as a Convection-Reaction-Diffusion system[4]

PDE9.gif

where the boldface 3-vectors are U matrix.gif, Fu matrix.gif, Gu matrix.gif and Ru matrix.gif.

Ephsteyn & Kurganov[4] however, report that such a re-formulation is prone to severe instabilities in the transition from a Hyperbolic region to an Elliptic one - upon implementation of a high-order Numerical Method. To implement the Discontinuous Galerkin method we therefore rewrite the system as

Chem system dg.gif

subject to the boundary conditions PDE13.gif, PDE4.gif. This may also be considered as a Convection-Reaction-Diffusion system of the form

PDE14.gif

once again where the boldface 3-vectors in this instance are Dg sys q.gif where Dg sys fq.gif, Dg sys gq.gif are the fluxes and Dg sys rq.gif is the reaction term. It should similarly be noted that k=1 is a constant and the convective part of the system is requisitely Hyperbolic.

This renders the Minimal Model soluble by a Discontinuous Galerkin numerical scheme as proposed by Ephsteyn & Kurganov[4].

Together, the Mesh and the Convection-Reaction-Diffusion equation form the complete theoretical basis upon which the program is to be developed.

Analytic Form of Solution

In the nomenclature defined above, a solution to the Keller-Segel System must take the form

PDE28.gif

for some solution in the direct product space of the respective nondegenerate quasi-linear rectangular subdivisions Var13.gif, satisfying the weak formulation of the Minimal Model

Timesolution.gif

where sums of the integrals are over Var13.gif and the set of interior edges Rho.gif, which in turn are split up into horizontal & vertical edges - Rho hor.gif and Rho ver.gif respectively - of the rectangular boundary Var6.gif.

Feasibility of developing Numerical Method

As seen in the precending section. even the simplest of analytic solutions to the Keller-Segel System using the Discontinuous Galerkin method is distinctly non-trivial - and would require a high degree of technical proficiency and time to implement. This was outwith the scope of our project, but were it to be attempted, would prove a robust and highly accurate means of collimating the individual PicoPlumber modelling modules.

Moreover, comment must be made on extensions to the basic Minimal Model "chassis" to incorporate effects such as quorum sensing and cell-growth & multiplication. These augmentations are discussed thoroughly in Hillen & Painter[1] but would require a re-derivation of some of the results given on this page - assuming compatibility with the Discontinuous Galerkin methods, that is.


References

[1] Hillen T, Painter KJ, "A user's guide to PDE models for Chemotaxis" J Math Biol. 2009 Jan;58(1-2):183-217. Epub 2008 Jul 15.

[2] Oxford Centre for Nonlinear PDE. http://www.maths.ox.ac.uk/groups/oxpde/

[3] The Maxwell Institute: Centre for Analysis and Nonlinear PDE's. http://www.maxwell.ac.uk/PDEs/

[4] Ephsteyn Y, Kurganov A, New Interior Penalty Discontinuous Galerkin Methods for the Keller–Segel Chemotaxis Model. J. Numer. Anal. Volume 47, Issue 1, pp. 386-408 (2008)

[5] Faculty of 1000 Biology. "A user's guide to PDE models for Chemotaxis" Importance recognition. http://f1000biology.com/article/id/1126950