Les hélitrons constituent un groupe d'éléments transposables découverts récemment dans les génome eucaryotes. A travers une étude bioinformatique, nous avons étudié leur mode d'invasion, la modularité de leur séquence et leurs impacts sur les gènes à leur proximité dans le génome d'Arabidopsis thaliana. Les hélitrons sont les éléments transposables les plus répandus dans ce génome ; néanmoins ils ne sont que partiellement reconnus par des logiciels d'alignement. Nous avons modélisé ces éléments sous la forme d'une grammaire formelle. Cette grammaire est constituée des deux extrémités terminales séparées par une séquence nucléotidique quelconque de taille fixée. Nous avons créé une matrice d'occurrences des modèles associant toutes les combinaisons possibles d'extrémités. La matrice a fait apparaître des associations préférentielles entre certaines extrémités et a permis la découverte de nouvelles familles d'hélitrons chimériques. La détection des ORFs contenant les protéines de transposition a permis de confirmer la relation hélitron autonome non-autonome et de comprendre le mécanisme de création des chimères d'hélitrons. Nous avons proposé une nouvelle nomenclature des hélitrons basée sur leurs extrémités et non sur leur séquence globale. L'étude de la séquence d'une famille d'hélitrons a montré une réorganisation constante des domaines nucléiques entre les différentes copies de cette famille. Pour comprendre cette organisation, nous avons mis au point le logiciel DomainOrganizer qui permet d'observer la composition en domaines des éléments transposables. DomainOrganizer détecte les frontières entre domaines à partir d'un alignement multiple et crée la liste des domaines. A partir de cette liste, il recherche, par un algorithme d'optimisation combinatoire, le nombre minimal de domaines qui recouvrent au maximum l'ensemble des séquences. Enfin, DomainOrganizer visualise et classe les séquences en fonction de leurs domaines. L'analyse par domaines de la famille AtREP21 a permis de comprendre la nature de cette variabilité et de retracer l'histoire évolutive de cette famille à partir de l'identification des domaines. L'étude de la localisation des hélitrons AtREP3 dans ce génome de plante a montré une insertion préférentielle de ceux-ci dans les promoteurs de gènes. Les profils d'expression de ces gènes, nous a permis d'identifier plusieurs clusters. Par ailleurs, les motifs de régulation ont montré une grande variabilité de motifs dans les promoteurs mais pas dans les hélitrons. Ces résultats ont montré que les hélitrons non-autonomes transportent dans leurs séquences internes des motifs de liaisons aux facteurs de transcription. Des analyses complémentaires devront être réalisées pour comprendre l'action régulatrice des hélitrons sur les gènes situés à leur proximité.

Les techniques de planification de mouvement actuelles sont maintenant capables de résoudre des problèmes mettant en jeu des mécanismes complexes plongés au sein d'environnements encombrés. Néanmoins, l'adaptation de ces planificateurs à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données qui sont précalculées pour capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter des problèmes comprenant à la fois obstacles statiques et obstacles mobiles. Ce planificateur hybride combine deux grandes familles de techniques. D'une part les techniques dites PRM, initialement conçues pour résoudre des problèmes à requêtes multiples et que nous avons étendu à des problèmes de scènes dynamiques. D'autre part, de nouvelles techniques de diffusion, alors que celles-ci sont généralement dédiées aux problèmes simple requête ne nécessitant aucune opération de prétraitement. Les principaux développements accompagnant la construction de ce planificateur sont les suivants : - La proposition d'une architecture originale pour le planificateur dédié aux environnements changeants. Cette architecture inclut notamment plusieurs mécanismes dits d' "évaluation paresseuse" qui permettent de minimiser les test de collision et ainsi d'assurer de bonnes performances. - Le développement d'une nouvelle méthode de diffusion permettant de reconnecter localement certaines portions du réseau invalidées par la présence des obstacles mobiles. Cette méthode, appelée RRT à Domaine Dynamique correspond en fait une extension des planificateur bien connus à bases de RRTs. Un des intérêt propre à notre approche est d'équilibrer automatiquement deux comportements propres au planificateur : l'exploration vers des régions encore inconnues et l'affinage du modèle des régions de l'espac e déjà explorées. - Deux méthodes originales de création de réseaux cycliques qui servent à initialiser notre planificateur. La première assume que les obstacles mobiles sont confinés dans une région donnée, pour construire un réseau adapté aux différents types de changements de position possibles. La seconde est une méthode qui construit des réseaux appelés "réseaux de rétraction". A l'aide d'une structure de donnée de faible taille, cette structure parvient à capturer les différentes variétés de chemins de l'espace, à travers notamment chacune des classes d'homotopie de l'espace libre. Toutes ces méthodes sont implémentées au sein de la plate-forme de travail Move3D développée au LAAS-CNRS et sont évaluées sur différents types de systèmes mécaniques plongés au sein d'environnements 3D.

Ce mémoire donne un aperçu de mes travaux de recherche depuis la thèse. La thématique générale est la mécanique statistique, qui a pour but de comprendre le comportement macroscopique d'un système physique dont les interactions sont décrites au niveau microscopique. De nombreux modèles appartiennent à la mécanique statistique; nos résultats se concentrent sur le modèle d'Ising, le modèle de dimères et les arbres couvrants en dimension deux. Ces trois modèles ont la particularité d'être exactement solubles, c'est-à-dire qu'il existe une expression exacte et explicite pour la fonction de partition. Ce mémoire décrit et met en perspective les résultats de mes publications, et donne les étapes principales des démonstrations.

L'objet des travaux de cette thèse est de proposer de nouveaux processus de définition de tests (testabilité), de nouvelles méthodes de tests, ainsi que de nouvelles méthodes d'interprétation des tests (diagnostic). Ces travaux ont été menés dans le cadre de l'aéronautique et ont porté dans un premier temps sur l'identification des besoins en diagnostic des hélicoptères. Les problématiques liées au test et au diagnostic des hélicoptères portaient sur : - La non-détection de certaines défaillances - L'occurrence de nombreuses fausses alarmes - L'ambiguïté de localisation de défaillances Dans un premier temps nous avons réalisé l'état de l'art des recherches en diagnostic, ceci afin de sélectionner les technologies et méthodologies permettant de répondre aux problématiques identifiées. Les technologies candidates ont ensuite été architecturées afin de proposer un traitement intégré permettant de répondre à l'ensemble des besoins identifiés. Ainsi nous avons travaillé sur les méthodologies de définition du test, aux moyens d'outils de simulation de la testabilité. Nous avons aussi défini de nouvelles méthodes de test permettant de déterminer l'état de capteurs analogiques aux moyens d'algorithmes basés sur des évaluateurs de calcul de variation de l'écart type, du facteur de forme et du rapport signal sur bruit. Nous avons ensuite travaillé sur l'amélioration du diagnostic au niveau système à l'aide d'automates temporisés afin de simuler le fonctionnement des arbres de tests élémentaires. Ces travaux ont ensuite conduit à la modélisation et au diagnostic des systèmes complexes à l'aide des diagrammes d'état, des arbres de défaillances dynamiques, ainsi que leur simulation à l'aide des réseaux de Petri. Les modèles utilisés ont été complétés au moyen de nouvelles portes dynamiques. Ces travaux ont été appliqués au monde aéronautique, sur plusieurs hélicoptères et ont fait l'objet de deux brevets.

Dans la majeure partie de cette thèse, nous nous sommes consacrés à l'étude de la forme des arbres phylogénétiques et plus particulièrement à leur déséquilibre. Une phylogénie est dite déséquilibrée, si la plupart des noeuds internes (les ancêtres communs) séparent l'arbre en deux sous-arbres de tailles sensiblement différentes. Les deux modèles de phylogénies aléatoires les plus classiques sont le modèle de Yule qui suppose que toutes les espèces ont la même probabilité de spéciation, et le modèle uniforme qui suppose que toutes les phylogénies de même taille sont équiprobables. Dans ces deux modèles, nous avons pu identifier les distributions limites des mesures de déséquilibre les plus utilisées par les biologistes. Les démonstrations sont inspirées de méthodes apparues récemment dans l'analyse des algorithmes. En génétique des populations, nous avons montré que le déséquilibre des généalogies de gènes est le signal d'un phénomène culturel : l'héritage de la fertilité. Nous avons mis en évidence la présence de ce trait culturel dans les populations de chasseurs-cueilleurs en utilisant le déséquilibre de généalogies reconstruites à partir d'ADN mitochondrial. Dans une dernière partie, la théorie de la coalescence a été appliquée à la génétique spatiale. Trois méthodes d'inférence d'un paramètre de dispersion spatiale ont été proposées. La vitesse de dispersion des ours bruns de Scandinavie a été estimée par une de ces trois méthodes.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

Cette thèse porte sur la Conception Centrée Valeur (CCV) proposé par Gilbert Cockton dans le but d'aller au-delà de l'utilisabilité dans les systèmes interactifs. L'auteur propose un canevas pour la mise en oeuvre de la CCV. Cependant, les opérationnalisations restent partielles et sont réalisées par lui-même, d'où un manque de recul de la communauté vis-à-vis de la méthode. La thèse relate la conception centrée valeur de Cocoon, un système d'information mobile et sensible au contexte. Elle apporte des contributions à la fois sur les plans conceptuel et méthodologique. D'un point de vue conceptuel, elle introduit la taxonomie PIPE (Personnelle, Impersonnelle, Pérenne, Éphémère) pour la caractérisation de l'information. En outre, elle montre que les systèmes existants ne couvrent pas PIPE : ils sont surtout focalisés sur les informations impersonnelles. Alors, la thèse propose le concept d'arbre de vie et Cocoon. D'un point de vue méthodologique, la thèse apporte une compréhension meilleure de la notion de valeur. En outre, elle fournit un retour d'expérience sur la CCV accompagné de remarques et recommandations pour des mises en oeuvres futures plus performantes. Enfin, elle propose un canevas pour la construction des cartes de valeur et une stratégie pour l'estimation de la valeur. / The thesis deals with Worth Centered Design (WCD) introduced by Gilbert Cockton. The author also introduced a framework aimed to support the WCD operationalization. However, this framework has been operationalized only partially until now and by Gilbert Cockton himself. The thesis relates our WCD experience with Cocoon, a mobile and context-aware information system. The thesis contributions are both conceptual and methodological. From a conceptual point of view, we introduce the PIPE (Personal, Impersonal, Perennial, Ephemeral) taxonomy for information characterization and show that existing systems only partially covers the PIPE information space: they focus on impersonal information. This notice motivated us to propose the life tree concept and Cocoon. From a methodological point of view, we offer a feedback to the community on an interesting concept method as well as recommendations for more efficient operationalizations. In addition, we introduce a framework for worth maps construction and a strategy for worth assessment.

Advances in data collection methods, storage and processing technology are providing a unique challenge and opportunity for automated data learning techniques which aim at producing high-level information, or models, from data. A Typical knowledge discovery process consists of data selection, data preparation, data transformation, data mining and interpretation/validation of the results. Thus, we develop automatic learning techniques which contribute to the data preparation, transformation and mining tasks of knowledge discovery. In doing so, we try to improve the prediction accuracy of the overall learning process. Our work focuses on decision tree based learning and thus, we introduce various preprocessing and transformation techniques such as discretization, fuzzy partitioning and dimensionality reduction to improve this type of learning. However, these techniques can be used in other learning methods e.g. discretization can also be used for naive-bayes classifiers. The data preparation step represents almost 80 percent of the problem and is both time consuming and critical for the quality of modeling. Discretization of continuous features is an important problem that has effects on accuracy, complexity, variance and understandability of the induction models. In this thesis, we propose and develop resampling based aggregation techniques that improve the quality of discretization. Later, we validate by comparing with other discretization techniques and with an optimal partitioning method on 10 benchmark data sets.The second part of our thesis concerns with automatic fuzzy partitioning for soft decision tree induction. Soft or fuzzy decision tree is an extension of the classical crisp tree induction such that fuzzy logic is embedded into the induction process with the effect of more accurate models and reduced variance, but still interpretable and autonomous. We modify the above resampling based partitioning method to generate fuzzy partitions. In addition we propose, develop and validate another fuzzy partitioning method that improves the accuracy of the decision tree.Finally, we adopt a topological learning scheme and perform non-linear dimensionality reduction. We modify an existing manifold learning based technique and see whether it can enhance the predictive power and interpretability of classification. / La recherche avancée dans les méthodes d'acquisition de données ainsi que les méthodes de stockage et les technologies d'apprentissage, s'attaquent défi d'automatiser de manière systématique les techniques d'apprentissage de données en vue d'extraire des connaissances valides et utilisables.La procédure de découverte de connaissances s'effectue selon les étapes suivants: la sélection des données, la préparation de ces données, leurs transformation, le fouille de données et finalement l'interprétation et validation des résultats trouvés. Dans ce travail de thèse, nous avons développé des techniques qui contribuent à la préparation et la transformation des données ainsi qu'a des méthodes de fouille des données pour extraire les connaissances. A travers ces travaux, on a essayé d'améliorer l'exactitude de la prédiction durant tout le processus d'apprentissage. Les travaux de cette thèse se basent sur les arbres de décision. On a alors introduit plusieurs approches de prétraitement et des techniques de transformation; comme le discrétisation, le partitionnement flou et la réduction des dimensions afin d'améliorer les performances des arbres de décision. Cependant, ces techniques peuvent être utilisées dans d'autres méthodes d'apprentissage comme la discrétisation qui peut être utilisées pour la classification bayesienne.Dans le processus de fouille de données, la phase de préparation de données occupe généralement 80 percent du temps. En autre, elle est critique pour la qualité de la modélisation. La discrétisation des attributs continus demeure ainsi un problème très important qui affecte la précision, la complexité, la variance et la compréhension des modèles d'induction. Dans cette thèse, nous avons proposes et développé des techniques qui ce basent sur le ré-échantillonnage. Nous avons également étudié d'autres alternatives comme le partitionnement flou pour une induction floue des arbres de décision. Ainsi la logique floue est incorporée dans le processus d'induction pour augmenter la précision des modèles et réduire la variance, en maintenant l'interprétabilité.Finalement, nous adoptons un schéma d'apprentissage topologique qui vise à effectuer une réduction de dimensions non-linéaire. Nous modifions une technique d'apprentissage à base de variété topologiques `manifolds' pour savoir si on peut augmenter la précision et l'interprétabilité de la classification.

Lors de cette thèse, je me suis intéressée aux modèles et aux algorithmes pour étudier l'histoire évolutive commune des hôtes et des symbiotes. Le premier objectif était d'analyser la robustesse des méthodes de réconciliation des arbres phylogénétiques, qui sont très utilisées dans ce type d'étude. Celles-ci associent (ou lient) un arbre, d'habitude celui des symbiotes, à l'autre, en utilisant un modèle dit basé sur des évènements. Les évènements les plus utilisés sont la cospéciation, la duplication, le saut et la perte. Les phylogénies des hôtes et des symbiotes sont généralement considérés comme donnés, et sans aucune erreur. L'objectif était de comprendre les forces et les faiblesses du modèle parcimonieux utilisé et comprendre comment les résultats finaux peuvent être influencés en présence de petites perturbations ou d'erreurs dans les données en entrée. Ici deux cas sont considérés, le premier est le choix erroné d'une association entre les feuilles des hôtes et des symbiotes dans le cas où plusieurs existent, le deuxième est lié au mauvais choix de l'enracinement de l'arbre des symbiotes. Nos résultats montrent que le choix des associations entre feuilles et le choix de l'enracinement peuvent avoir un fort impact sur la variabilité de la réconciliation obtenue. Nous avons également remarqué que l'evènement appelé “saut” joue un rôle important dans l'étude de la robustesse, surtout pour le problème de l'enracinement. Le deuxième objectif de cette thèse était d'introduire certains evènements peu ou pas formellement considérés dans la littérature. L'un d'entre eux est la “propagation”, qui correspond à l'invasion de différents hôtes par un même symbiote. Dans ce cas, lorsque les propagations ne sont pas considérés, les réconciliations optimales sont obtenues en tenant compte seulement des coûts des évènements classiques (cospeciation, duplication, saut, perte). La nécessité de développer des méthodes statistiques pour assigner les coûts les plus appropriés est toujours d'actualité. Deux types de propagations sont introduites : verticaux et horizontaux. Le premier type correspond à ce qu'on pourrait appeler aussi un gel, à savoir que l'évolution du symbiote s'arrête et “gèle” alors que le symbiote continue d'être associé à un hôte et aux nouvelles espèces qui descendent de cet hôte. Le second comprend à la fois une invasion, du symbiote qui reste associé à l'hôte initial, mais qui en même temps s'associe (“envahit”) un autre hôte incomparable avec le premier, et un gel par rapport à l'évolution des deux l'hôtes, celui auquel il était associé au début et celui qu'il a envahi. Nos résultats montrent que l'introduction de ces evènements rend le modèle plus réaliste, mais aussi que désormais il est possible d'utiliser directement des jeux de données avec un symbiote qui est associé plusieurs hôtes au même temps, ce qui n'était pas faisable auparavant / In this Ph.D. work, we proposed models and algorithms to study the common evolutionary history of hosts and symbionts. The first goal was to analyse the robustness of the methods of phylogenetic tree reconciliations, which are a common way of performing such study. This involves mapping one tree, most often the symbiont’s, to the other using a so-called event-based model. The events considered in general are cospeciation, duplication, host switch, and loss. The host and the symbiont phylogenies are usually considered as given and without any errors. The objective here was to understand the strengths and weaknesses of the parsimonious model used in such mappings of one tree to another, and how the final results may be influenced when small errors are present, or are introduced in the input datasets. This may correspond either to a wrong choice of present-day symbiont-host associations in the case where multiple ones exist, or to small errors related to a wrong rooting of the symbiont tree. Our results show that the choice of leaf associations and of root placement may have a strong impact on the variability of the reconciliation output. We also noticed that the host switch event has an important role in particular for the rooting problem. The second goal of this Ph.D. was to introduce some events that are little or not formally considered in the literature. One of them is the spread, which corresponds to the invasion of different hosts by a same symbiont. In this case, as when spreads are not considered, the optimal reconciliations obtained will depend on the choice made for the costs of the events. The need to develop statistical methods to assign the most appropriate ones therefore remains of actuality. Two types of spread are introduced: vertical and horizontal. The first case corresponds to what could be called also a freeze in the sense that the evolution of the symbiont “freezes” while the symbiont continues to be associated with a host and with the new species that descend from this host. The second includes both an invasion, of the symbiont which remains with the initial host but at the same time gets associated with (“invades”) another one incomparable with the first, and a freeze, actually a double freeze as the evolution of the symbiont “freezes” in relation to the evolution of the host to which it was initially associated and in relation to the evolution of the second one it “invaded”. Our results show that the introduction of these events makes the model more realistic, but also that it is now possible to directly use datasets with a symbiont that is associated with more than one host at the same time, which was not feasible before

Le maintien de ressources génétiques suffisamment larges est nécessaire pour assurer la viabilité et le potentiel évolutif des populations naturelles. Cette thèse a le principal objectif de caractériser la diversité et la variabilité génétique chez le genre Virola (Myristicaceae) pour décrire les processus évolutifs qui en sont à l'origine. Premièrement,une étude de la régénération d'un échantillonnage exhaustif de V. michelii a été menée dans une parcelle du dispositif expérimental de Paracou ayant subi une exploitation forestière de faible intensité et comparée à une parcelle témoin. La diversité génétique mesurée à partir de marqueurs AFLP (Amplified Fragment-Length Polymorphism, N=229) en zones perturbées s'est révélée être plis grande qu'en zone non-perturbées. Puis, l'adaptation locale a été étudiée à travers ces mêmes individus et certains loci (AFLP) montrent une sélection divergente pour des environnements contrastés, indiquant un signe d'adaptation. Enfin, l'étude des niveaux de divergence génétique chez trois espèces de Virola du bouclier guyanais (V. michelii, V. surinamensis et V. kwatae) montrent que deux d'entre elles (V. surinamensis et V. kwatae) montrent de fortes similarités génétiques malgré leur distribution sur des environnements contrastés. des Flux de gènes intersécifiques ont été mis en évidence chez ces deux espèces-soeurs et l'hypothèse d'une spéciation écologique est avancée. Ce travail a permis d'aborder différents processus évolutifs à l'origine de la diversité génétique actuelle chez ces espèces forestières tropicales et peut fournir une contribution pour appréhender le devenir des populations. / Genetic diversity is an essential component of biodiversity. The maintenance of sufficient genetic resources is needed to ensure the adaptive potential and the viability of natural populations. In the current context of global changes, the study of adaptation in living organisms is a key task, particularly for tropical forest trees that are dominant components (in terms of biomass and as ecological drivers) of some of the most diverse ecosystems on Earth. The main objective of this thesis is to characterize genetic diversity and genetic variability to understand the evolutionary processes that act on them. This ecological-genetic study was carried out at the interspecific and intraspecific level in the Virola genus.If overall high levels of genetic diversity are a guarantee of prosperity for the future of the species, it seems essential to perform studies on the impact of environmental disturbance on genetic diversity. In the first section, the genetic consequences of regeneration dynamics were studied in an exhaustive sample of V. michelii in a low-intensity logging plot and in a control plot at the Paracou experimental site. A greater genetic diversity, measured from AFLP markers (Amplified Fragment Length Polymorphism, N = 229), was found in perturbed areas. Because studying genetic diversity within species may be useful for understanding species adaptation to environmental changes, in the second section. I studied local adaptation in a population of V. michelii on the Paracou experimental site. A genome scan approach with AFLPs (N = 229) was conducted on 77 adult individuals and 401 juveniles to identify genetic differences between populations associated to contrasting conditions for an array of environmental variables. Some loci (N = 2) were found to be subject to divergent selection, indicating adaptation to contrasting habitats.In the third section, the study of levels of genetic divergence in three Virola species of the Guiana Shield (V. michelii, V. surinamensis and V. kwatae) was investigated for nuclear and chloroplast molecular markers. V. surinamensis and V. kwatae showed strong genetic similarities despite their contrasting habitats preferences. Coalescent analyses have revealed, on one hand, a recent divergence between these two species suggesting an ecological speciation, and one the other hand that interspecific gene flow occurs between these sister-species.This work focuses on understanding evolutionary processes shaping genetic diversity and provides a useful contribution for biodiversity conservation programs.