| Titre : | Optimisation par algorithme génétique pour la résolution du problème d’assemblage de fragments d’ADN |
| Auteurs : | Nouara Boudouh, Auteur ; Leila Djerou, Directeur de thèse |
| Type de document : | Monographie imprimée |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2019 |
| Format : | 1 vol. (60 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Le problème d'assemblage de fragments consiste à construire une séquence d'ADN à partir de plusieurs centaines (voire des milliers) de fragments obtenus par les biologistes du laboratoire. Il s'agit donc d'un problème d'optimisation combinatoire, connu comme étant NP-difficile. Pour résoudre ce problème, nous avons adopté l’algorithme génétique (AG). Pour améliorer la recherche de bonne solution, nous avons intégré l’algorithme PALS (Problem Aware Local search) comme un opérateur de recherche additionnel dans l’AG. Une étude expérimentale a montré que l’hybridation de l’AG avec PALS a donné de bons résultats par rapport à ceux de l’AG. |
| Sommaire : |
Introduction générale 01 Chapitre1 : Problème d’assemblage de fragments d’ADN 03 1. Introduction ………………………………………………………… 04 2. Analyse de l’ADN …………………………………………………. 04 2.1 Structure de l’ADN ……………………………………………………….. 05 2.2 Les étapes d’analyse de l‘ADN ……………………………………………. 06 3. Séquençage de fragments d’ADN …………………………………. 07 3.1 Les méthodes de séquençage ………………………………………………. 08 3.2 Le séquençage de Shotgun ………………………………………………… 09 4. L’assemblage de fragments d’ADN ……………………………..... 11 4.1 Assemblage par cartographie (maping)…………………………………….. 11 4.2 Assemblage de novo ……………………………………………………….. 11 4.3 L’approche OLC (Overlap-Layote-Consensus) ……………………………. 12 5. Les problèmes d’assemblage ………………………………………. 13 6. Conclusion …………………………………………………………. 14 Chapitre 2 : Méta-heuristique d’optimisation 15 1. Introduction ………………………………………………………… 16 2. Problème d’optimisation …………………………………………… 16 3. Méthodes de résolution …………………………………………….. 18 3.1 Méthodes de résolutions exactes …………………………………………… 19 3.2 Méthodes de résolution approchées ……………………………………….. 19 4. Algorithmes génétiques (AG) ……………………………………… 21 4.1 Le codage des données …………………………………………………….. 23 4.2 Génération de la population initiale ………………………………………... 24 4.3 L’évaluation ………………………………………………………………... 24 4.4 Sélection ……………………………………………………………………. 24 4.5 Croisement …………………………………………………………………. 26 4.6 Mutation ……………………………………………………………………. 29 4.7 Remplacement ……………………………………………………………... 31 5. Conclusion …………………………………………………………. 31 Chapitre 3 : Conception 32 1. Introduction …………………………………………………………………….. 33 2. Hybridation de l’AG avec PALS ………………………………………………. 33 3. Description détaillée de l’AGPALS …………………………………………… 34 3.1 Génération de la population initiale ……………………………………….. 35 3.2 Evaluation de la population ………………………………………………... 35 3.3 Sélection ……………………………………………………………………. 37 3.4 Croisement …………………………………………………………………. 37 3.5 Mutation ……………………………………………………………………. 38 Table des matières 3.6 Algorithme PALS ………………………………………………………….. 38 3.7 Critère d’arrêt ………………………………………………………………. 40 4. Conclusion ……………………………………………………………………... 41 Chapire 4 : Implémentation 42 1. Introduction ………………………………………………………… 43 2. Environnement et outils de travail ……………………………………………... 43 2.1 Environnement de développement ………………………………………… 43 2.2 Outils utilisés ………………………………………………………………. 44 2.3 Les structures utilisées ……………………………………………………... 45 2.4 Les algorithmes …………………………………………………………….. 46 3. Présentation détaillé de l’algorithme AGPALS ………………………………... 48 3.1 Génération d’une population initiale ………………………………………. 48 3.2 Sélection ……………………………………………………………………. 52 3.3 Croisement …………………………………………………………………. 52 3.4 Mutation ……………………………………………………………………. 54 3.5 Appliquer algorithme PALS…………………………………………........... 54 3.6 Remplacement ……………………………………………………………... 56 4. Expérimentation et résultats ……………………………………………………. 56 5. Conclusion ……………………………………………………………………... 59 Conclusion générale 60 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/438 | Mémoire master | bibliothèque sciences exactes | Consultable |
