perso perso tim anthony manuel exclamation tux pitit Algorithme de Gillespieperso portfolio cisoun tux tux ya kelk1 pitit Algorithme de GillespieAlgorithme de Gillespie

Qu’est ce qu’un algorithme de Gillespie ?

C’est une méthode stochastique (ça signifie aléatoire) pour simuler l’évolution d’un système. Dans ce système un certain nombre d’évènements et chacun de ces évènements a une probabilité donnée d’arriver. Le but est d’en choisir un aléatoirement, en tenant compte de cette probabilité. En « arrivant », un évènement va modifier la probabilité d’autres évènements.

Daniel T. GILLESPIE (Américain, 1977 – ) a développé son algorithme pour simuler numériquement l’évolution de réactions chimiques couplées. Sa méthode est développée dans un article paru en 1976. (JOURNAL OF COMPUTATIONAL PHYSICS 22, 403-434). Son système est composé de molécules et il est intéressé par l’évolution du nombre de ces molécules en fonction de réactions (les évènements), au cours du temps.

Réactions chimiques

Dans le système, on note perso  Algorithme de Gillespie l’espèce i et perso  Algorithme de Gillespie le nombre de molécules de cette espèce chimique.

Gillespie s’intéresse aux réactions de création par source externe,
perso  Algorithme de Gillespie

Les autres réactions possibles ne mettent pas en jeu plus de trois molécules, qui peuvent être identiques ou différentes.

Chacune de ces réactions est caractérisée par un paramètre de réaction perso  Algorithme de Gillespie. Ce paramètre est intimement lié à la constante de Michaëlis-Menten.

Relation entre le paramètre perso  Algorithme de Gillespie et la constante de Michaëlis-Menten

La constante de Michaëlis-Menten est une constante dépendant des concentrations, tandis que perso  Algorithme de Gillespie dépend des quantités en molécules. Ainsi, on obtient la relation suivante :

perso  Algorithme de Gillespie

Où i est le cardinal de chaque réactant et perso  Algorithme de Gillespie le nombre stœchiométrique de ce réactant et N le nombre total de réactants différents.

Probabilité de rencontre

Afin de définir la fonction de densité de probabilité de réaction, Gillespie fait aussi appel à la probabilité de rencontres des molécules.

perso  Algorithme de Gillespie  est le nombre de combinaisons distinctes de molécules réactante pour la réaction perso  Algorithme de Gillespie, présentes dans le volume V au temps t .

perso  Algorithme de Gillespie

Densité de probabilité de réaction

Cette fonction de densité de probabilité est définie de la façon suivante : avec perso  Algorithme de Gillespie la réaction et perso  Algorithme de Gillespie la durée de cette réaction,

perso  Algorithme de Gillespie

Algorithme

L’algorithme en lui-même est relativement simple, il s’agit de tirer au hasard un perso  Algorithme de Gillespie et un perso  Algorithme de Gillespie d’après les fonctions de densité de probabilité. Ensuite on recalcule les fonctions, on tire au hasard un nouveau couple etc…

On interrompt le processus lorsque les quantités de molécules atteignent toutes 0 ou qu’un temps maximum définit est dépassé.

Méthode pour tirer perso  Algorithme de Gillespie et perso  Algorithme de Gillespie

Gillespie propose dans son article deux méthodes, une méthode dite directe et une méthode dite de la première réaction. Je ne développe que la méthode directe, réputée pour être plus efficace dès que le nombre d’événements dépasse 3.

Dans la méthode directe, on considère un nombre a, somme du produits des probabilité de rencontre et paramètre de réaction pour chacune des réactions.

perso  Algorithme de Gillespie

Pour calculer le paramètre perso  Algorithme de Gillespie on tire un nombre perso  Algorithme de Gillespie à partir d’une distribution uniforme sur l’intervalle unité.

perso  Algorithme de Gillespie

Le tirage de perso  Algorithme de Gillespie est a little bit more tricky comme dit ma tutrice de stage. On tire un nouveau réel perso  Algorithme de Gillespie dans l’intervalle unité à partir d’une distribution uniforme.

perso  Algorithme de Gillespie est tel que
perso  Algorithme de Gillespie

Les valeurs successives de a sont additionnées jusqu’à ce que la somme soit supérieure ou égale à perso  Algorithme de Gillespie, alors perso  Algorithme de Gillespie est la dernière valeur pour laquelle c’était inférieur.

perso  Algorithme de Gillespie est considéré comme le temps que dure la réaction plus le temps où rien ne se passe.

Conclusion

On obtient un algorithme facilement implémentable en beaucoup de langages. La performance comme souvent en simulation étant de rigueur, un langage compilé sera toutefois préférable !

L’article de Gillespie écrit il y a un certain nombre d’année présente une implémentation en FORTRAN particulièrement efficace, je serais curieux de pouvoir comparer la rapidité de simulation de ses tests en 1976 sur les machines puissantes qu’il évoque par rapport à ceux que l’on produit aujourd’hui sur le plus simple des ordinateurs personnels.

Il est maintenant plus que temps de rentrer à la maison, une bonne demi-heure de vélo sous le soleil m’attend !