Habilitation à diriger des recherches : sciences de l'ingénieur : Nice, Sophia-Antipolis : 2000.

Th. 3e cycle--Méthodes d'approximation et algorithmes en anal. et théor. des nombres--Besançon, 1980. N°: 338.

L'ARN (acide ribonucléique) est une molécule ubiquitaire qui joueplusieurs rôles fondamentaux au sein de la cellule: synthèse desprotéines avec les ARN messagers, activité catalytique ou implicationdans la régulation, les ARN non-codants. Les nouvelles technologies deséquençage à haut- débit permettent de produire des milliards de séquences à moindre coût, posant de manière cruciale la question de l'analyse de ces données.L'objectif de cette thèse est de définir de nouvelles méthodescomputationnelles pour aider à l'analyse de ces séquences dans le casdes ARN non-codants. Dans cette perspective, la "structuresecondaire" d'un ARN, formée par l'ensemble des appariements entrebases, délivre des informations utiles pour étudier la fonction del'ARN. Notre travail se concentre plus particulièrement surl'ensemble des structures potentielles que peut adopter une séquenced'ARN donnée, ensemble que nous appelons "multi-structure". Nousapportons deux contributions: un algorithme pour générersystématiquement toutes les structures localement optimales composantune multi-structure, et un algorithme basé sur la recherche d'unemulti-structure pour identifier un ARN non-codant dans une séquencegénomique. Ces résultats ont été mis en oeuvre dans deux logiciels,Alterna et Regliss, appliqués avec succès à des ensembles de test. / RNA (ribonucleic acid) molecules have various functions in cells. Justas they can store and deliver the DNA message for the proteinsynthesis (messenger RNAs), they can also directly catalyze chemicalreactions or act as a regulator (functional RNAs, also callednon-coding RNAs). Nowadays, recent sequencing technologies yield billions of genomic sequences - DNA, RNA - at a very small cost. However, sequencing isonly the first step: The function of the sequence remains open forinvestigation. The objective of the thesis is to define newcomputational methods to help sequence and structure analysis ofnon-coding RNAs. In this perspective, the "secondary structure" of an RNA,made with base pairs, provides useful hints to further study itsfunction. Our work is focused on sets of all possible RNA structuresfor a given sequence, introducing the concept of "RNAmulti-structures". The thesis details how such sets can be constructed systematically to generate all locally optimal secondary structures, and how they can be used as a pattern to identify non-coding RNAs in genomic sequences.We provide efficient algorithms for these two problems. Thesealgorithms have been implementated in the software tools Alterna andRegliss and tested on real data, providing new insight into RNAstructures.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots.<br /><br />Les algorithmes randomisés ont été un des sujets ``chauds'' de ces dernières années et nous proposons ici des travaux ayant trait à des algorithmes dynamiques ou semi-dynamiques : tout d'abord un schéma général d'algorithmes semi-dynamiques avec des applications aux diagrammes de Voronoï, aux diagrammes de Voronoï d'ordre k aux arrangements, et ensuite deux algorithmes dynamiques (permettant d'insérer et de supprimer des données) pour la triangulation de Delaunay et le calcul d'un arrangement de segments. D'autres résultats concernent des algorithmes statiques, notamment le calcul du squelette d'un polygone simple en temps O(n log* n).<br /><br />La deuxième partie explore différentes modélisations des sphères. On peut en déduire notamment un algorithme en O(tk log n) pour la triangulation de Delaunay de n points appartenant à k plans en 3 dimensions, si t désigne la taille du résultat; dans la cas de deux plans cet algorithme atteint une complexité optimale de O(t+n log n). Nous proposons également un algorithme de complexité O(n^ ceil(d/2) +n log n) pour le calcul de l'enveloppe convexe de n sphères en dimension d, et un algorithme optimal (quadratique) pour le calcul de la surface de Connolly.<br /><br />La dernière partie traite de problèmes spécifiques à la planification de trajectoires, un premier chapitre concerne le cas de plusieurs robots polygonaux en translation dans le plan: certaines configurations appellées double-contacts peuvent jouer un rôle particulier dans certains cas. Ensuite deux résultats à propos de robots à pattes : l'analyse d'un cas simple que nous avons baptisé robot araignée, et l'étude de la stabilité d'un robot un peu plus complexe.

Les problèmes de robustesse liés à la substitution du calcul exact sur les réels par le calcul flottant approché sont souvent un obstacle à l'implantation pratique des algorithmes géométriques. Si l'adoption du paradigme exact apporte une solution satisfaisante à ce type de problèmes pour les algorithmes ayant un résultat purement combinatoire, cette solution ne permet cependant pas de résoudre en pratique le cas des algorithmes qui réutilisent voire cascadent la construction de nouveaux objets géométriques. Cette thèse aborde le problème de l'arrondi sur la grille entière du résultat d'opérations booléennes sur des régions polygonales et propose plusieurs notions d'arrondi permettant de garantir certaines propriétés métriques et topologiques intéressantes entre le résultat exact et sa version arrondie telles que la garantie de relations d'inclusion et la préservation de la convexité du résultat. Nos méthodes sont basées sur l'utilisation de constructeurs élémentaires arrondis pour lesquels nous présentons également plusieurs algorithmes efficaces. Nous proposons enfin des tests rapides permettant la détection robuste d'intersection entre plusieurs types d'objets convexes dans le plan et dans l'espace. L'ensemble de ces solutions trouvent une application directe en CAO et en graphisme.

Reproduction de : Thèse de doctorat : Mécanique et informatique : Reims : 2005. / Titre provenant de l'écran titre. Bibliogr. f. 191-199.

Th. doct.--Phys.--Rouen, 1996. / 1996 d'après la déclaration de dépôt légal. Bibliogr. p. 151-155. Résumé en français et en anglais.

La recherche de motifs approchée consiste à identifier les occurrences d’un motif modulo une certaine distance au sein d’un texte. Ce problème trouve de nombreuses applications en bio-informatique pour l’analyse de séquences biologiques. Par exemple, les microARN sont des petits ARN qui régulent l’expression des gènes par reconnaissance d’un motif similaire. Comprendre le mode d’action des microARN demande de pouvoir localiser de courts motifs, environ 21 nucléotides, comprenant jusqu’à 3 ou 4 erreurs dans un texte de l’ordre de 108 à 109 nucléotides, représentant un génome. Dans cette thèse, nous proposons un algorithme efficace pour la recherche de motifs approchée, qui se base sur la définition d’un nouveau type de graines avec erreurs, les graines 01*0, et qui exploite une structure d’index compressée, le FM-index. Cet algorithme a été mis en œuvre dans un logiciel librement disponible, appelé Bwolo. Nous démontrons expérimentalement l’avantage de cette approche en nous comparant à l’état de l’art des outils existants. Nous montrons également comment utiliser Bwolo pour mettre en place une analyse originale sur l’étude de la distribution des cibles potentielles de miARN dans deux génomes de plantes, Arabidopsis thaliana et Arabidopsis lyrata. / Approximate string matching consists in identifying the occurrences of a motif within a text, modulo a given distance. This problem has many applications in bioinformatics for the analysis of biological sequences. For instance, microRNAs are short RNA molecules regulating the expression of genes by specific recognition of their sequence motif on the target gene. Understanding the mode of action of microRNAs requires the ability to identify short motifs, around 21 nucleotides in size, comprising up to 3-4 errors in a text whose size is in the order of 108-109 , representing a genome. In this thesis, I have proposed an efficient algorithm for the approximate search of short motifs. This algorithm is based on a new type of seeds containing errors, the 01*0 seeds, and uses a compressed index structure, the FM-index. I have implemented this algorithm in a freely available software, Bwolo. I demonstrate experimentally the advantage of this approach and compare it to the state of the art of existing tools. I also show how Bwolo can be used and have set up an original study on the distribution of potential miRNA target sites in two plant genomes, Arabidopsis thaliana and Arabidopsis lyrata.

La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens l'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à compresser le volume au maximum, et l'élaboration de structures théoriques compactes qui minimisent la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter de<br />façon compacte les triangulations. Pour ce faire, deux issues sont explorées : modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des indices sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'exécution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des micro-triangulations, et de représenter la triangulation comme un ensemble de ces micro-triangulations. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont <br />prometteurs, sachant que le temps d'exécution n'est pas dramatiquement altéré par la modification des méthodes d'accés aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage de l'information géométrique des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.