Institut de la Francophonie pour l’Informatique Optimisation du calcul de la courbure d’ADN MEMOIRE soutenu le. pour l’obtention du DEPA de l'Institut de la Francophonie pour |’Informatique (Spécialité Informatique) par Thanh Phuong NGUYEN Composition du jury FEincadrant : Isabelle DEBLED-RENNESSON Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503 Remerciements Tout d’abord, je souhaite remercier vivement mon responsable de stage, Mme. Isabelle DEBLED-RENNESSON pour m’avoir aidé et guidé tout au long de mon stage, d’avoir évoqué ma passion pour la géométrie discréte et d’avoir me donné des conseils précieux pendant le stage. Je souhaite aussi remercier M.
Fabien FESCHET (LLACD) d’avoir fourni son programme et m’avoir permis de l’utiliser dans mon travail ainsi qu’avoir répondu aux questions concernant son programme. Je voudrais remercier Mme Jocelyne ROUYER (ADAGE) qui me donne son évaluation sur mon travail pendant le stage. Je voudrais remercier M. Jean-Luc REMY (ADAGE) d’avoir lu mon mémoire et d’avoir donné des commentaires prestigieux.
Je tiens 4 remercier tous les professeurs de l’IFI qui m’ont enseigné les connaissances professionnelles pendant mes études de master de recherche. Je tiens 4 remercier aussi tous les membres de l’équipe ADAGE, tout particuliérement Sylvain BLONDEAU qui a fait des remarques sur le programme, pour leur amitié et leurs nombreux conseils. Enfin, je remercie tout spécialement mes parents qui m’ont toujours encouragé dans mes études. Table des matiéres Introduction 1 1 Motivation.
ee 1 2 Présentation du probléme .0000 epee eee eee 1 3 Structure durapport .22 ee ee 2 Chapitre 1 Notions 3 1.2 Segment Houen3ÙD.002022 ee ee 9 15 Courbed’ADN .1 Structure de molécule d’ADN .2 Modéle dela courbe d’ADN. 2220088 e 10 Chapitre 2 Etat de lˆart 11 2.2 Segmentation de la courbe discréte en segments flous. La courbure et la tangente. - HQ HH HH ko 14 2.
co Q ee ee 14 "B5 NN. 15 il ill Chapitre 3 Etude théorique 17 3.1 Etude de l’algorithme de reconnaissance d’un segment flou.2 Les propriếtés de lenveloppe convexe.4 Conception des algorlthmes.Ặ Q Q SH HQ HH Ra 21 3.2 Etude de l’algorithme de calcul de la tangente et dela courbure.1 Algorithme de calcul de la tangente.2 Adaptation de lalgorithme de Melkman .3 Calcul de la courbure en chaque point .1 Calcul de la courbure en chaque point d’une courbe 2D .2 Calcul de la courbure en chaque point d’une courbe 3D .4 Calcul d’un segment flou a4 Pétape suivante .2 Calcul d’un segment flou 4 ’étape suivante. 200202002 ee ee eee 32 3.002 2 eee ee eee 34 Chapitre 4 Expérimentation 36 4.1 Présentation du programme. Ặ HQ HQ HH ko 36 4.1 Les paramétres d’entrée.
- HQ HH Ha 36 4.1 Calcul dun segment Ñou avec une épalsseur donnée.2 Calcul de la courbure en chaque point .3 Calcul de la tangente en chaque point .3 Application aux courbesd’ADN.2020 00220 eee ee ee 42 Conclusion 44 Bibliographie 45 Table des figures 1.1 2 types de connexitéen 2D .000 eee ee ee C2 1.2 3 types de connexitéen 3D .0 2200 eee ee ee nh 1.3 Une droite discréte en 2D : D(3,—-5,-3,2).4 Droites d’appui et points d’appui .--0 20-0022 ee ee ee 1.5 Les droites ont des connexités différentes .6 Une droite discréteen 3D .0002 ee ee CON 1.7 Calcul de lacourbure3D .0002 eee ee eee 1.8 Structure de VADN.9 Modélisation de 1 ADN avec modéle tubulaire (modélisation obtenue a l’aide du logiciel CURVATURE).1 Transformation des cas sommet-sommet vers les cas aréte-sommet .2 Cas ott M;, M2 se trouvent sur le méme demi-plan dont le bord est la hauteur de Yenveloppe convexe pour Sf.3 Calcul de la largeUT. - HQ HQ HQ HH ee ee.4 Calcul dela hauteur .0002 eee ee ee 20 3.9 Calcul de la courbure d’ordre 2 en un point T.6 Segment flou originel .7 Aprés avoir effectué l’étape 2, X coincide avec A;. Dans l’étape 6, on cherche des candidats pour X dans la zone marquée entre A; etR .8 Avant létape 3, X coincide avec A, puis X coincide avec Ơi ; avant létape 4, Y coincide avec Y, puis Y coincide avec By.10 Chercher et trouver les candidats pour X et Y. Aprés l’étape 6, X est assigné a M dans la premiére zone marquée.
Aprés l’étape 7, Y est assigné 4 N dans la deuxiéme zone marquée.11 Avant l’étape 9, X coincide avec M, Y coicide avec Y. Aprés cette étape, Z est assignéaP .1 Les courbures d’extrait d’un cercle 3D dont le rayon est 10.2 Les courbures d’extrait 4 partir d’une courbe en spirale dont le rayon est 10 .3 Les courbures d’extrait 4 partir d’autre courbe en spirale dont le rayon est 10 .4 Segmentation d’une courbe discréte en segments flous.5 Les courbures obtenues en tous les points d’une courbe en 3D .6 Les courbures extraites 4 partir des formes différentes de la courbe d’ADN du virus E-coli. Lépalsseur d'extralt est toujours 3. 1V LISTE DES ALGORITHMES V Liste des Algorithmes Segmentation des courbes 8-connexes en segments flous.
13 Reconnaissance incrémentale d’un segment flou avec ’épaisseurv. 14 WN Algorithme de reconnaissance de la tangente au point central. 16 Calculer la largeur 4 chaque étape .022002 eee 22 FR Calculer la hauteur 4 chaque étape.-0- 20220-0207 | 23 Oo Construire la droite englobante optimale pour un segment flou. 24 Calculer la tangente 4 la courbe H au point P.
25 CoN Déterminer l’enveloppe convexe d’un polygone simple. 26 Lalgorithme adapté de Melkman. Ặ QẶ HQ Q HQ 27 ke © Reconnaissance dˆun segment fÑou 3D d'épalsseUr0. 28 Pre & Calcul la courbure en chaque point de la courbe discrète 3D.
28 or Déterminer le segment Ñou à étape suivanie.Ặ Ặ QẶ Q QẶ 35 Introduction 1 Motivation Avec le développement de l’imagerie informatique et son application dans des contextes de plus en plus diversifiés, la géométrie discréte a des grands progrés dans des années derniéres. Ce domaine, qui est basé sur des connaissances mathématiques, vise 4 étudier des objets discrets. Ces objets se composent d’un ensemble dénombrable des points entiers. Alors, les connaissances de la géométrie euclidienne qui s’adaptent aux objets continus ne peuvent pas s’appliquer sur ces objets.
Normalement, les objets discrets ont peu de propriétés communes par rapport aux leurs homologues continus. Les résultats les plus élémentaires de la géométrie euclidienne ne sont pas vérifiés dans des espaces discrets. En fait, la géométrie discréte reprend des notions familiéres de la géométrie euclidienne en développant des théorémes spécifiques au type d’espace et d’objet discret. La géométrie discréte regroupe des approches théoriques différentes telles que : topologie discréte, géométrie arithmétique, théorie des graphes et combinatoire.
Parmi ces approches, l’approche de géométrie arithmétique qui lie les propriétés des objets discrets a celle des nombres entiers est V’approche principale puisqu’elle s’adapte mieux au calcul informatique. Plusieurs des résultats fondamentaux de ce domaine ont été découverts grace a cette approche. C’est aussi la méthode pour notre travail de stage. 2 Présentation du probléme L’équipe ADAGE(Algorithmique Discréte et ses Applications 4 la GEnomique) du laboratoire LORIA (Laboratoire LOrraine de Recherche en Informatique et ses Applications) étudie l’algo- rithmique discréte et ses applications au traitement des informations génomiques.
Il y a deux thémes principaux de recherche : l’un est le traitement des textes; l'autre théme de recherche est la géométrie discréte. Du cété pratique, le développement des logiciels qui permettent de les traiter est aussi important. Ce stage est effectué dans cette équipe dans le contexte de construction d’une application 4 la génomique dans le domaine de la géométrie discréte. L’objectif du stage est d’optimiser le calcul de la courbure d’ADN.
Ce travail est la continuation des travaux d’Isabelle Debled-Rennesson et al : la segmentation des segment flou de la courbe discréte [7] et [8], le calcul de la courbure et des tangentes de la courbes discréte [4]. Dans ses travaux, le calcul de la courbure et des tangentes de la courbe est basé sur la technique de segmentation des segments flous qui est présenté dans [8]. Récemment, Debled-Rennesson et al. présentent un algorithme optimal [5] pour segmenter des segments flous de la courbe.
Alors, dans le cadre de ce stage, nous visons 4 appliquer cette technique optimale pour le calcul de la courbure et des tangentes de la courbe discréte. Ceci, dans l’optique de travailler avec des courbes d’ADN. Structure du rapport 2 Dans ce stage, nous avons étudié les droites discrétes et le probléme de la segmentation en seg- ments flous d’une courbe discréte. Plusieurs des méthodes existantes sont étudiées.
Par ailleurs, nous avons proposé une nouvelle technique de segmentation des segments flous. Celle-ci peut travailler dans le cas général et est en fait une extension d’un travail [5] de Debled-Rennesson et al. En ce qui concerne ce probléme, nous proposons aussi un algorithme qui permet de calculer le segment flou de la courbe au point suivant avec une meilleure complexité par rapport au cal- cul direct. D’autre part, nous étudions et proposons un algorithme pour calculer la tangente en chaque point d’une courbe discréte.
Enfin, nous nous concentrons sur le calcul de la courbure en appliquant les techniques proposées. 3 Structure du rapport Ce rapport se compose de 4 chapitres. Le chapitre 1 présente des notions de base dans le domaine de la géométrie discréte. Le chapitre 2 donne un état de l’art sur ce probléme.
Les cha- pitre 3 et 4 vont présenter nos contributions 4 la théorie et notre implémentation expérimentale. Enfin, nous allons donner quelques conclusions de notre travail dans la partie de conclusion. Chapitre 1 Notions Dans ce chapitre, nous allons présenter les notions de base dont on a besoin pour résoudre notre probléme.1 Point discret Un point discret est l’objet discret le plus élémentaire de la géométrie discréte. Nous sa- vons qu’un point réel dans la géométrie euclidienne a des coordonnées réelles.
Par contre, les coordonnées d’un point discret sont des nombres entiers.1 Point discret en 2D Un point discret en 2D se compose de 2 coordonnées entiéres qui montrent sa position sur un plan. Il est appelé un pixel. On dit 2 points discrets connectés s’ils sont adjacents. Considérons un point discret comme un carré.
Nous avons alors 2 types de connexité pour définir les point adjacents. 4-connexe : 2 points sont connecté si ils ont un arét commune 8-connexe : 2 points sont connecté si ils ont un arét commune ou un sommet commune (a) 4 (b) & connexe connexe Fic.1 — 2 types de connexité en 2D 1.2 Point discret en 3D Un point discret en 3D contient 3 coordonnées entiéres qui déterminent sa position dans Vespace. Normalement, il est appelé un voxel. I] y a 3 types de connexité pour déterminer 2 points adjacents.
Pour la clarté, nous considérons un voxel comme une cube. Droite discréte 4 6-connexe : 2 points sont connectés si ils ont une face commune 18-connexe : 2 points sont connectés si ils ont une face commune ou une aréte commune 26-connexe : 2 points sont connectés si ils ont une face commune ou une aréte commune ou un sommet commune TT « aw Aw eA ae, aT a, | A aw py y | AT (a) 6-connexe (b) 18- (c) 26- connexe connexe Fic.2 — 3 types de connexité en 3D 1.2 Droite discréte La droite discréte est un résultat principal de la géométrie discréte. A partir de cet objet, plu- sieurs des objets complexes sont construits. D’ailleurs, la reconnaissance des segments de droites a nombreux applications dans les domaines comme le traitement d’images, la reconnaissance des formes, l’algorithmique graphique.
Alors, la droite discréte a intéressé plusieurs chercheurs dans les années derniéres.