Algorithme Génétique et

Gestion de ProjetB. Batut, M. Chevalier, E. Girard et N. Parisot

Objectif

•A partir d’un graphe aléatoire,

•Obtenir un graphe biologiquement réaliste

•via l’utilisation d’un Algorithme Génétique

Première Etape : Graphes

•Choisir un type de graphe biologique à imiter

•Graphe de réactions métaboliques

•http://pbil.univ-lyon1.fr/software/motus

•Motif Search in Metabolic Networks

•Récupération des 76 graphes disponibles au format XML

Première Etape : Graphes

•Sélection des graphes entre 100 et 500 noeuds (± 10%)

•48 Graphes

•Calcul des caractéristiques de ces graphes

•Réseau métabolique moyen

Première Etape : Graphes

•Réseau Métabolique Moyen

•Degré moyen d’un noeud : 4.05 ± 0.93

•Coefficient de clustering : 0.37 ± 0.06

•Nombre de cliques (normalisé par nombre de noeuds) : 0.7 ± 0.05

•Mean Free Path : 5.78 ± 1.52

Deuxième Etape : Algo Gen

•Développement du logiciel

•Interface Graphique

•CAPTURE

Deuxième Etape : Algo Gen

• Définition de la fitness

• Adéquation de la distribution des degrés à une loi de puissance de paramètre 2.2 (Valeur trouvée dans la littérature)

• Test de Kolmogorov-Smirnov

• p-value doit être < 1e-6

• Nombre de cliques

• Doit être compris entre

• Coefficient de clustering

• Doit être compris entre

• Connexité

• Egale à 1 obligatoirement

• Mean Free Path

• Doit être compris entre

Deuxième Etape : Algo Gen

•Pondération de la fonction de fitness

•Additif

•Test vs

Tests

Résultats