perso perso tim anthony manuel exclamation tux pitit Implémentation de l’algorithme de Gillespie : PseudoCodeperso portfolio cisoun tux tux ya kelk1 pitit Implémentation de l’algorithme de Gillespie : PseudoCodeImplémentation de l’algorithme de Gillespie : PseudoCode

Dans le précédent article, j’expliquais les bases de l’algorithme de Gillespie. Je vous propose maintenant une implémentation en pseudo-code. Je reprends volontairement les étapes de la même façon que Gillespie dans son article A general method for Numerically simulating the stochastic time evolution of coupled chemical reactions.

Step 0 Initialisation

Variables :

Fixer le temps : t = 0
Fixer les concentrations initiales des N espèces : X1 X2 X3... XN
Spécifier et stocker les valeurs c1 c2 c3 ... cM pour les M réactions
Calculer les M quantité c1h1 c2h2 c3h3 ... cMhM pour les M réactions

Spécifier et stocker une série de temps auxquels on va générer
 une sortie des concentrations XN.

Fixer un temps maximum tstop.

Step 1

Générer une paire aléatoire Tau et Mu, tel que présenté dans le précédent article.

r2 = uniforme(0,1)
suma = a1 + ... + an
i = 1
sumpart = a1
tant que r2 * a < sumpart :
    incrémente i
    sumpart = sumpart + ai
sinon
    mu = i - 1
r1 = uniforme(0,1)
tau = (1/suma) ln(1/r1)

Step 2

En utilisant les nombres Tau et Mu, on fait avancer t de Tau et on change les valeurs de quantités Xi impliquées dans la réaction Mu.

pour i dans 1, n n nombre de réactants de Rmu
Xi = Xi - ai avec ai le nombre stoechiométrique correspondant
pour i dans 1, m m nombre de produits de Rmu
Xi = Xi + ai
t = t + tau

Step 3

Si t vient de dépasser un des temps auxquels on doit générer une sortie, lire les quantités de toutes les concentrations Xi. Si t est supérieur à tstop ou si tous les h sont nuls (preuve qu’il n’y a plus de réactants), s’interrompre, sinon retourner à l’étape 1.

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 !

  1. Leneurone

    Le sujet est assez imbuvable pour quelqu’un qui n’a pas la moindre notion dans le domaine, mais c’est assez bien écrit !

    La seule remarque que j’ai est que tu n’expliques pas il me semble ce qu’est un évènement…

    Il pourrait être intéressant aussi d’avoir l’algo entier écrit sous forme algorithmique, histoire de formaliser un peu tout ce que tu expliques avant !

    J’aime bien la tournure que prend ton blog :)

    ++
    Leneurone

  2. Florck

    Un évènement a un probabilité donnée de survenir, qui dépend des paramètres du système. En survenant, cet évènement va modifier ces paramètres.

    Dans l’exemple traité par Gillespie, un évènement est une réaction chimique. En fait l’évènement est alors la rencontre des espèces nécessaires et la « disparition » de ces espèces au profit de la création de nouvelles espèces, les produits de la réaction.

  3. Florck’s blog » Blog Archive » Implémentation de l’algorithme de Gillespie : PseudoCode

    [...] le précédent article, j’expliquais les bases de l’algorithme de Gillespie. Je vous propose [...]

android p@sco androtux Utiliser son Google Phone pour appeler en voix over ipandroid libre    fcys14 tux asterix pitit Utiliser son Google Phone pour appeler en voix over ipUtiliser son Google Phone pour appeler en voix over-ip

Installé pour 3 mois aux Pays-Bas, il était simplement inimaginable de payer une fortune par minutes pour appeler vers la France et ne pas être coupé de ma famille et de mes amis.

En bon geek, la solution s’est vite imposée : téléphonie over ip. Il existe une excellenteandroid  Utiliser son Google Phone pour appeler en voix over ip application pour Android nommée Sipdroid.

En attendant l’activation de mon compte OVH, j’ai la chance d’avoir des gentils parents qui m’ont autorisé à utiliser le SIP de leur compte free (ouh le vil squatteur).

Installer SIPdroid

android  Utiliser son Google Phone pour appeler en voix over ipSIPdroid est une application permettant de passer des appels en VOIP depuis son téléphone portable.

Sachez que selon votre contrat vous liant à votre opérateur, il est interdit d’utiliser sur leurs réseaux les services de voix sur IP. Cependant ils n’ont rien à redire et autorisent d’utiliser les service de VOIP en passant par le wifi.

Ainsi pour satisfaire cette clause, la version distribuée sur l’android market de SIPdroid désactive l’utilisation du réseau 3G/2G/… pour la voip n’autorisant que l’utilisation du wifi.

Le QRcode pour l’installer directement du market est

android  Utiliser son Google Phone pour appeler en voix over ip

Vous trouverez sur internet le lien direct vers le site du logiciel (qui est un logiciel au moins open-source, libre peut-être, je n’ai pas vérifié) qui propose la version complète, à utiliser à vos risques et périls et sous risque de rupture de contrat à votre désavantage.
En ce qui me concerne, étant à l’étranger, de toute façon je n’ai de connexion data que connecté à un wifi, donc le problème ne se pose pas !
Une fois le logiciel installé, il faut configurer d’abord son compte free.

Configuration du compte free

(Les images sont directement issues de la faq de free : http://www.free.fr/assistance/268-freebox-le-service-sip-activer-le-service-sip.html)

Avant tout, sachez que le service SIP est automatiquement inclus dans votre forfait free et que l’activer ne réinitialise pas votre durée d’engagement.

Pour activer SIP, il est important de se connecter en utilisant la connexion internet de la ligne free elle-même (donc de chez vous).

Rendez-vous sur la page de connexion à votre compte : http://subscribe.free.fr/login/

Tâchez de vous souvenir de vos identifiants… Oui je sais c’est dûr ! En théorie, votre numéro de téléphone fixe et un mot de passe de peu de caractères.

android Gestion sip Utiliser son Google Phone pour appeler en voix over ipEnsuite, sous Téléphone, sélectionnez gestion de mon compte SIP.

Dans la page qui s’est ouverte, vous pouvez paramétrer votre compte SIP.

Il vous est demandé de renseigner un mot de passe de 10 caractères. Notez le bien pour vous en souvenir, attention comme toujours à la casse !

Ensuite cochez Activer.

Pour l’autre option, c’est à vous de choisir : voulez vous recevoir sur votre téléphone portable les appels à destination de votre compte free ?

android Gestion sip param Utiliser son Google Phone pour appeler en voix over ipSi oui, cochez la case « Redirigez les appels entrant vers le compte SIP », alors dès qu’un ordinateur, ou un téléphone sera connecté sur le compte, ce sera lui qui recevra les appels. Attention, selon mes diverses constatations sur internet, cette option est relativement aléatoire.
Si vous cochez non, vous pouvez émettre les appels, mais lorsqu’on vous appelle, ce sera toujours sur le téléphone branché à votre freebox que ça sonnera.
Vérifiez que « Service activé » est coché puis Enregistrez.
Maintenant la fonction SIP est disponible, il faut configurer SIPdroid.

SIPdroid

android sipdroid1 Utiliser son Google Phone pour appeler en voix over ipDans l’interface de configuration, il va falloir renseigner trois choses :

Le nom d’utilisateur : il s’agit du numéro en 09…

Le password que vous avez choisi tout à l’heure.

Le serveur : freephonie.net

Le port est à laisser à sa valeur par défaut 5060.

Maintenant un petit point de couleur devrait apparaître dans la barre de notifications, en haut. S’il est vert, vous avez gagné.

Attention : Vous appelez sous les conditions de votre fournisseur free : ainsi, les appels vers les fixes sont gratuits dans la mesure où c’est un comportement de bon père de famille, les appels vers les mobiles eux sont payant, ils vous sont facturés au tarif en vigueur. Donc n’appelez pas les portables, utilisez votre forfait habituel pour ça android icon wink Utiliser son Google Phone pour appeler en voix over ip .

Mots-clefs :, , , | Classé dans : Android, Libre
Pas de commentaire

humeurs humeur brunocb tux terre g1 et sa lune pitit Vie virtuelle dune cellule non moins virtuellehumeurs portfolio cisoun tux tux ya kelk1 pitit Vie virtuelle dune cellule non moins virtuelleVie virtuelle d’une cellule non moins virtuelle

Plus d’un an après, c’est le blog revival !

À quelle occasion ? Celle du début de mon stage en hollande dans un laboratoire de biologie et bioinformatique.

Accueilli pour mon stage de fin de 4ème année, ma mission est simple : implémenter un algorithme de Gillespie, pour tester la cellule virtuelle.

La cellule virtuelle

Le but est de créer une cellule minimale par une méthode d’algorithme génétique. (Un article suivra pour expliquer le principe de cet algorithme).

L’algorithme génétique étant un algorithme évolutif, il est important de définir si la cellule est plus ou moins viable, fait plus ou moins ce qu’elle doit. On parle de fitness.

Pour une cellule, les scientifiques ayant développé et cherché une cellule virtuelle sont parti du principe qu’une des choses essentielles pour une cellule est d’être capable de maintenir son homéostasie, c’est à dire à maintenir son équilibre en dépit des variations qu’elle peut subir.

La cellule est celle défini par Alex A Neyfakh dans son article publié le 17 Août 2006 dans Biology Direct.

On considère deux types de petites molécules. A et X. A est disponible dans le milieu et X est une molécule porteuse d’énergie.  Il existe aussi des protéines de différent type : des enzymes catalysant le métabolisme d’A en X et des enzymes catalysant l’anabolisme de A et X en déchet; des pompes qui permettent de faire entrer A dans la cellule, des facteurs de transcription, recevant un ligand et pouvant se lier à un opérateur (une séquence sur le code génétique).

Ces protéines sont codées par des gènes. Dans l’article, pas de codage du gène nécessitant une traduction. On stocke juste des paramètres, un numéro de séquence opérateur, etc…

Ces protéines peuvent être créées, dégradées.

Dans l’article, le métabolisme de la cellule, c’est à dire l’évolution des concentrations des petites et grosses molécules est suivi par simulation des équations différentielles, une méthode dite déterministe.

Algorithme de Gillespie

Une autre voie serait de simuler cette évolution par une méthode stochastique. C’est le principe de l’algorithme de Gillespie.

Je vous expliquerai bientôt en quoi consiste cet algorithme et quelles modifications je dois lui apporter pour l’adapter au problème et les raisons de ces modifications et enfin, le modèle que j’ai choisi d’adopter.

Il est l’heure d’aller dormir !

Mots-clefs :, , , | Classé dans : Humeurs, Portfolio
Pas de commentaire