The aim of this habilitation is to exhibit my contributions in several area of Bio-Algorithmics. Rather than an exhaustive presentation of my works, I have made the choice of presenting results we obtained with collaborators on a representative subset of the problems I have been involved in since 2005. For ease of readability, I will regroup the results obtained according to the biological problems: i) RNA structures comparison, ii) Genomes comparison and iii) Pattern matching in biological networks and their respective combinatorial objects: i) Arc-annotated sequences, ii) Permutations and Sequences and iii) Graphs. More precisely, The first part will be devoted to the Arc-Annotated Sequences that are used in RNA structure comparison. We will focus on five problems that we investigated: LAPCS, APS, MAPCS, EDIT and ALIGN. In the second part, we will consider the two main research area related to comparative genomics we were involved in: gene clusters detection and (dis)similarity measures computation -- which rely on permutation and string representations. Finally, we will present some results that were obtained mainly during the PhD of Florian Sikora that I co-supervised.

La variabilité des vitesses d'évolution entre sites est un phénomène très répandu au sein des séquences génétiques. Celui-ci est généralement modélisé par une loi gamma dont le paramètre de forme doit être estimé. Nous proposons ici une méthode visant à déterminer la valeur efficace de ce paramètre, c'est-à-dire la valeur la plus adaptée à l'estimation de topologies d'arbres. Nous montrons que (1)les valeurs efficaces conduisent généralement à sous-estimer la variabilité des vitesses et (2), celles-ci offrent une amélioration significative en termes de précision topologique comparé aux cas ou l'inférence d'arbre est réalisée à partir des vraies valeurs (inconnues) du paramètre. Outre la paramétrisation adéquate des modèles de substitution, l'exploration de l'espace des topologies d'arbres est un point sensible pour bon nombre de méthodes d'inférences de phylogénies. Nous proposons ici une nouvelle méthode pour l'estimation d'arbres de vraisemblances maximales, basée sur la modification simultanée de la topologie de l'arbre et de ses longueurs de branches. Nous montrons que cette approche autorise la construction de topologies particulièrement fiables à partir de l'analyse de plusieurs centaines de séquences.

Un embryon, initialement composé de cellules identiques, se transforme progressivement en une structure spatialement organisée de tissus distincts aux frontières clairement démarquées. Ce processus de formation de motifs est étudié dans le domaine de la biologie du développement. Les interactions cellulaires jouent un rôle clé dans la formation de motifs, et l'effet de communauté est un exemple d'une telle interaction. Une population de cellules dans un embryon présente un effet de communauté quand elle forme une communauté de cellules ayant une identité commune obtenue grâce à l'échange de molécules de signalisation qui diffusent dans le milieu (i.e. des morphogènes). Cet effet permet aux cellules de la communauté de maintenir un profil d'expression génétique commun pendant une période prolongée, et pour se différencier finalement de manière coordonnée dans un tissu fonctionnel, comme le muscle. Les processus auto-organisés tels que l'effet de communauté sont difficiles à comprendre intuitivement. Une description satisfaisante peut être obtenue sous la forme d'un modèle formel. Quelques modèles computationnels des effets de la communauté ont été donnés dans la littérature. Cependant, la notion d'espace n'ayant pas été explicitement incluse dans ces modèles, il est difficile de comprendre comment l'effet de communauté participe à la formation de motifs. Dans ce travail, nous étudions le comportement de l'effet de communauté dans l'espace et étudions ses rôles dans d'autres processus de formation de motif, en utilisant la modélisation computationnelle. Les contributions principales de cette thèse sont les suivantes: * Une méthode de réduction de modèle est développée pour l'analyse stochastique. Par cette méthode nous avons pu démontrer que le modèle de l'effet de communauté dans Xenopus est influencé par un bruit stochastique. * En utilisant un modèle spatial simple d'effet de communauté, nous montrons que celui-ci doit finalement se propager dans l'ensemble de la population de cellules qui réagissent au morphogène. Cela est confirmé par un modèle plus détaillé. * Deux modèles montrant comment cette expansion peut être contrôlée sont présentés. Tout d'abord, si l'effet de communauté est augmenté d'un mécanisme de rétroaction négative, il forme un système de réaction-diffusion qui s'auto-organise et forme une zone d'activation stable et localisée. En second lieu, quand un circuit simple de repression génétique est associé au circuit produisant l'effet de communauté, un motif d'expression de gène avec une frontière bien démarquée apparaît en réponse à un gradient de morphogène transitoire. Le motif reste stable y compris après disparition du gradient, ce qui indique que le réseau de gènes garde en mémoire la dynamique du morphogène.

Les modèles de Markov cachés (MMC) - par exemple ceux de la librairie Pfam - sont des outils très populaires pour l'annotation des domaines protéiques. Cependaqnt, ils ne sont pas toujours adaptés aux protéines les plus divergentes. C'est notamment le cas avec Plasmodium falciparum (principal agent du paludisme chez l'Homme), où les MMC de Pfam identifient peu de familles distinctes de domaines, et couvrent moins de 50% des protéines de l'organisme. L'objectif de cette thèse est d'apporter des méthodes nouvelles pour affiner la détection de domaines dans les protéines divergentes. Le premier axe développé est une approche d'identification de domaines utilisant leurs propriétés de co- occurrence. Différentes études ont montré que la majorité des domaines apparaissent dans les protéines avec un ensemble très réduits d'autres domaines favoris. Notre méthode exploite cette propriété pour détecter des domaines trop divergents pour être identifiés par l'approche classique. Cette détection s'accompagne d'une estimation du taux d'erreur par une procédure de ré-échantillonnage. Chez P. falciparum, elle permet d'identifier, avec un taux d'erreur estimé inférieur à 20%, 585 nouveaux domaines - dont 159 familles étaient inédites dans cet organisme -, ce qui représente 16% du nombre de domaines connus. Le second axe de mes recherches présente plusieurs méthodes de corrections statistiques et évolutives des MMC pour l'annotation d'organismes divergents. Deux types d'approches ont été proposées. D'un côté, nous intégrons aux alignements d'apprentissage des MMC les séquences précédemment identifiés dans l'organisme cible ou ses proches relatifs. La limitation de cette solution est que seules des familles de domaines déjà connues dans le taxon peuvent ainsi être identifiées. Le deuxième type d'approches contourne cette limitation en corrigeant tous les modèles par une prise en compte de l'évolution des séquences d'apprentissage. Pour cela, nous faisons appel à des techniques classiques de la bioinformatique et de l'apprentissage statistique. Les résultats obtenus offrent un ensemble de prédictions complémentaires totalisant 663 nouveaux domaines supplémentaires - dont 504 familles inédites -, soit une augmentation de 18% à ajouter aux précédents résultats.

A l'heure de l'acquisition de données à haut débit concernant le métabolisme cellulaire et son évolution, il est absolument nécessaire de disposer de modèles permettant d'intégrer ces données en un ensemble cohérent, d'en interpréter les variations métaboliques révélatrice, les étapes clefs où peuvent s'exercer des régulations, voire même d'en révéler des contradictions apparentes mettant en cause les bases sur lesquelles le modèle lui-même est construit. C'est ce type de travail que j'ai entrepris à propos de données expérimentales obtenues dans le laboratoire biologique sur le métabolisme de cellules tumorales en réponse à un traitement anti-cancéreux. Je me suis attachée à la modélisation d'un point particulier de ce métabolisme. Il concerne le métabolisme des glycérophospholipides qui sont de bons marqueurs de la prolifération cellulaire. Les phospholipides constituent l'essentiel des membranes d'une cellule et l'étude de leur synthèse (en particulier chez les cellules de mammifères) est de ce fait un sujet important. Ici, nous avons pris le parti de mettre en place un modèle mathématique par équations différentielles ordinaires, qui est essentiellement basé sur des équations hyperboliques (Michaelis-Menten), mais aussi sur des cinétiques type loi d'action de masse et diffusion. Le modèle, composé de 8 équations différentielles, donc de 8 substrats d'intérêt, comporte naturellement des paramètres inconnus in vivo, et certains dépendents des conditions cellulaires (différentiations de cellules, pathologies, . . .). Le modèle sépare la structure du réseau métabolique, l' ́écriture de la matrice de stoechiométrie, celles des équations de vitesse et enfin des équations différentielles. Le modèle choisi est le modèle murin (souris/rat), parce qu'il est lui-même un modèle de l'homme. Plusieurs conditions sont successivement considérées pour l'identification des paramètres, afin d'étudier les liens entre la synthèse de phospholipides et le cancer : - le foie sain du rat, - le mélanome B16 et le carcinome de la lign ́ee 3LL chez la souris, respectivement sans traitement, en cours de traitement 'a la Chloroéthyl-nitrosourée et après traitement, - enfin le mélanome B16 chez la souris sous stress de privation de méthionine. En résumé, ce travail fourni une interprétation nouvelle des données expérimentales en montrant le rôle essentiel de la PEMT et la nature superstable de l'état sta- tionnaire de fonctionnement du réseau métabolique des phospholipides lors de la cancérogènèse et du traitement des cancers. Il montre bien l'avantage de l'utilisation d'un modèle mathématique dans l'interprétation de données métaboliques complexes.

In this thesis, we presented three main types of analyses of metabolism, most of which involved symbiosis: metabolic dialogue between a trypanosomatid and its symbiont, comparative analyses of metabolic networks and exploration of metabolomics data. All of them were essentially based on genomics data where metabolic capabilities were predicted from the annotated genes of the target organism, and were further refined with other types of data depending on the aim and scope of each investigation. The metabolic dialogue between a trypanosomatid and its symbiont was explored with functional and evolutionary goals which included analysing the classically defined pathways for the synthesis of essential amino acids and vitamins, exploring the genome-scale metabolic networks and searching for potential horizontal gene transfers from bacteria to the trypanosomatids. The comparative analyses performed focused on the common metabolic capabilities of different lifestyle groups of bacteria and we proposed a method to automatically establish the common and the group-specific activities. The application of our method on metabolic stories enumeration to the yeast response to cadmium exposure was a validation of this approach on a well-studied biological response to stress. We showed that the method captured well the underlying knowledge as it extracted stories allowing for further interpretations of the metabolomics data mapped into the genome-scale metabolic model of yeast

La métagénomique vise à étudier le contenu génétique et génomique d'un échantillon provenant d'un environnement naturel. Cette discipline récente s'attache à étudier les génomes de différents organismes provenant d'un même milieu. La métagénomique pose de nouvelles questions, tant d'un point de vue biologique qu'informatique. Les masses de données générées par les études métagénomiques et la complexité des milieux étudiés nécessitent de développer de nouvelles structures de données et de nouveaux algorithmes dédiés. Parmi les différentes approches existantes en métagénomique, la métagénomique comparative consiste à comparer plusieurs métagénomes afin d'en connaitre les divers degrés de similarité. Lorsque cette comparaison se base uniquement sur le contenu brut des échantillons, sans faire appel à des connaissances externes, on parle de métagénomique comparative de novo. L'objectif des travaux que nous proposons est de développer une méthode permettant d'extraire les séquences similaires entre deux jeux de données métagénomiques, où chaque jeu peut être composé de centaines de millions de courtes séquences d'adn. La comparaison proposée consiste à identifier les séquences d'un premier jeu similaires à au moins une séquence d'un second jeu. Afin d'être rapide et économe en mémoire, l'implémentation de notre méthode a nécessité la conception d'une nouvelle structure d'indexation, basée sur le filtre de bloom. Le logiciel final, nommé Compareads, a une consommation mémoire faible (de l'ordre de quelques go) et peut calculer l'intersection de deux échantillons de 100 millions de séquences chacun en une dizaine d'heures. Notre méthode est une heuristique qui génère un faible taux de faux positifs. Le logiciel Compareads est dédié à l'analyse de grands jeux de données métagénomiques. À l'heure actuelle, il est le seul outil capable de comparer de tels jeux. Compareads a été appliqué sur plusieurs projets métagénomiques. Notre outil produit des résultats robustes, biologiquement exploitables et en accord avec diverses méthodes fondamentalement différentes. Il est actuellement utilisé de manière intensive sur les échantillons provenant de l'expédition tara oceans. Sur ce projet, notre méthode a permis de mettre en évidence que les grands systèmes océaniques influent sur la répartition globale des microorganismes marins.

<p>This thesis presents a comprehensive set of results, obtained through an innovative experimental methodology, that have important and extensive implications for the fields of integrative biology and complex systems. The main objective of the thesis is to study the inter-individual interactions involved during the initiation and coordination of movement in gregarious vertebrates, and in particular in the sheep Merinos d’Arles (Ovis aries). Key questions are, when an individual initiates a movement, what information is taken into account by conspecifics, how is this information spread across the group, and what mechanisms underlie the collective decision processes? To answer these questions, we created an experimental paradigm to trigger, in a standardized way, the movement of trained individuals that were then placed in a group of naïve conspecifics. Using two types of stimuli, a sound (public) and a vibration (private), we could evaluate the individual response of followers, and the effect of the behavioural state on this response. An additional set of experiments also provided recordings of spontaneous initiations of movement.<p>Our results suggest that every individual in a group can initiate a collective movement. Our quantitative analysis then showed that, in Mérinos sheep, the individual decision to follow depends on a double mimetic effect; individuals take into account both the number of already departed individuals and the number of individuals which have not yet departed. A comparison between three experimental situations reveals that the decision rule is unique and that the behavioural state of potential followers only slightly affects the collective dynamics.<p>Our approach, a combination of experimentation and modelling, provides original results that contribute to the understanding of individual and collective decision-making processes, and of the mechanisms involved during collective movement. The experimental paradigm that was proposed here, and the mathematical tools that were used, open interesting perspectives for new experimental studies and for the generalization of the behavioural rules exposed in this thesis.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Lors de cette thèse, nous avons présenté trois principaux types d'analyses du métabolisme, dont la plupart impliquaient la symbiose : dialogue métabolique entre un trypanosomatide et son symbiote, analyses comparatives de réseaux métaboliques et exploration de données métabolomiques. Tous ont été essentiellement basés sur des données de génomique où les capacités métaboliques ont été prédites à partir des gènes annotés de l'organisme cible, et ont été affinées avec d'autres types de données en fonction de l'objectif et de la portée de chaque analyse. Le dialogue métabolique entre un trypanosomatide et son symbiote a été exploré avec des objectifs fonctionnels et évolutifs qui comprennaient une analyse des voies de synthèse des acides aminés essentiels et des vitamines telles que ces voies sont classiquement définies, une exploration de réseaux complets métaboliques et une recherche de potentiels transferts horizontaux de gènes des bactéries vers les trypanosomatides. Les analyses comparatives effectuées ont mis l'accent sur les capacités métaboliques communes de bactéries appartenant à différents groupes de vie, et nous avons proposé une méthode pour établir automatiquement les activités métaboliques communes ou spécifiques à chaque groupe. En plus de la génomique, la dernière étude présentée dans cette thèse a porté sur des données métabolomiques. Nous avons appliqué notre méthode d'énumération d'histoires métaboliques à la réponse de la levure à une exposition au cadmium comme une validation de cette approche sur une réaction au stress bien étudiée. Nous avons montré que la méthode a bien capté la connaissance que nous avons de cette réponse en plus de permettre de nouvelles interprétations des données métabolomiques mappées sur le réseau métabolique complet de la levure.

Cette thèse est une étude des travaux d’Ervin Laszlo sur cinquante ans. Elle met en valeur ses idées les plus importantes, les événements et les moments charnières de l’évolution de sa pensée qui l’ont conduit à sa position philosophique actuelle ; elle passe en revue les étapes du voyage philosophique de Laszlo à la découverte et vers la compréhension de « la manière dont les choses sont » et de « la manière dont les choses deviennent » en termes d’évolution des systèmes complexes, ainsi que du but et de la signification de la vie humaine. / A study of fifty years of philosophical work by Ervin Laszlo, highlighting the most important ideas, events and turning points in the thinking that led to his present-day philosophical position. This thesis reviews Laszlo’s philosophical voyage towards his uncovering and understanding of how things are and how things are becoming in terms of the evolution of complex systems as well as the purpose and meaning of human life.