erwandavidcode/genetic_algorithm-3dna

The aim of this Python project is to circularize a plasmid by optimizing the values of a table calculating the plasmid's 3D trajectory. To achieve this, 2 algorithms are used and compared: simulated annealing and genetic algorithm.

ST2 (Théorie des Jeux) - EI Algorithmique Génétique

Introduction

Présentation

Ce projet Python a pour objectif de circulariser un plasmide en optimisant les valeurs d'une table de calcul de trajectoire 3D du plasmide.

"En microbiologie et en biologie moléculaire, un plasmide est une molécule d'ADN distincte de l'ADN chromosomique."

Pour ce faire, sont utilisés et comparés 2 algoritmhes méta-heuristiques :

• Recuit simulé
• Algoritmhe génétique.

Fontion coût

Bien définir la fonction coût est essentiel pour assurer la convergence des algortihmes méta-heuristiques.

Elle est définit pour minimiser la distance entre le début et la fin de la chaine et minimiser l'angle pour assurer une jonction cohérente :

Les paramètres sont :

• $dist$ : la distance entre le noeud $n-1$ et $0$.
• $dot_1$ : le produit scalaire entre $V_{fin}$ et $V_{milieu}$
• $dot_1$ : le produit scalaire entre $V_{milieu}$ et $V_{début}$

Initialisation

• Créer un environnement virtuel Python

python -m venv venv

• Activer l'environnement

  • Windows

  .\venv\Scripts\activate

  • Linux / macos

  source ./venv/Scripts/activate

• Installer les librairies Python

pip install -r requirements.txt

Recherche d'une solution

• Algorithme du recuit simulé

python 3dna <répertoire du fichier .fasta> recuit

Exemple

python 3dna ./data/plasmid_8k.fasta recuit

• Algorithme génétique

python 3dna <répertoire du fichier .fasta> genetique <stratégie de sélection>

Liste des stratégies de sélection

elitisme (défaut)
roulette
rang
tournoi

Exemple

python 3dna ./data/plasmid_8k.fasta genetique tournoi

Valeur retournée

A la fin de l'exécution d'un algorithme, plusieurs valeurs sont imprimées :

• La table des rotations 3D en format json

• La différence entre les valeurs de Twist et Wedge et leur seuil maximal pour chaque paire de nucléotides (La valeur de Direction est constante)

• La distance entre le centre du dinucléotide du début et celui de fin.

• En notant

  • $p_i$ la position du centre du ième dinucléotide
  • $n$ le nombre de nucléotides dans la séquence
  • $v_{fin} = p_{n - 1} - p_{n - 2}$
  • $v_{milieu} = p_0 - p_{n - 1}$
  • $v_{debut} = p_1 - p_0$

  La similarité cosinus entre les vecteurs $v_{fin}$ et $v_{milieu}$, et $v_{milieu}$ et $v_{debut}$

Configuration des algorithmes

Les valeurs internes utilisées pour l'algorithme peuvent être modifiés dans le fichier 3dna/__main__.py.

• Algorithme de recuit simulé

recuit = Recuit(
    seq=seq,
    k_max=1000,
    e_min=0.1,
    temp_init=300,
    refroidissement=0.99,
    dist_min=0.,
    relier=1
)

argument	type	description
seq	str	La séquence de nucléotides
k_max	int	Le nombre d'itération maximale
e_min	float	Le seuil d'énergie
temp_init	float	La température initiale
refroidissement	float	Le coefficient de refroidissement
dist_min	float	Le seuil de distance
Relier	int	Le nombre de nucléotides reliés entre la fin et le début de la séquence

• Algorithme génétique

genetique = Genetique(
    seq=seq,
    methode_utilisee=args.methode_utilisee,
    nbr_generation_max=150,
    N=50,
    probabilite_mutation_initiale=0.05,
    probabilite_mutation_finale=0.05,
    relier = 1
)

argument	type	description
seq	str	La séquence de nucléotides
methode_utilisee	str	Le nom de la stratégie de sélection
nbr_generation_max	int	Le nombre de génération maximal
N	int	La taille de la population
probabilite_mutation_initiale	float	La probabilité de mutation initiale
probabilite_mutation_finale	float	La probabilité de mutation finale
Relier	int	Le nombre de nucléotides reliés entre la fin et le début de la séquence

Note : La probabilité de mutation évolue de manière linéaire entre la valeur initiale et la valeur finale

Test

Un test a été implémenté grâce à la librairie pytest.

Il peut être exécuté avec

cd 3dna
pytest

Un rapport de couverture sous format html peut être généré avec

python -m pytest --cov=. --cov-report html

Statistiques

Les algorithmes peuvent être testés avec plusieurs centaines d'itérations afin d'obtenir une distribution de la distance entre le centre du premier et du dernier dinucléotide, et du minimum de la similarité cosinus.

python 3dna/stat.py
python 3dna/plot.py