Les protéines transmembranaires canaux-β (TMBs) se trouvent dans les membranes externes des bactéries à Gram négatif, des mitochondries ainsi que des chloroplastes. Elles traversent entièrement la membrane cellulaire et exercent différentes fonctions importantes. Vu qu'il y a un petit nombre des structures des TMBs déterminées, en raison des difficultés avec les méthodes expérimentales, il est douteux que ces approches puis- sent bien trouver et prédire les TMBs qui ne sont pas homologues avec celles connues. Nous construisons un modèle de graphe pour la classification et la prédiction de structures super-secondaires permutées des TMBs à partir de leur séquence d'acides aminés, en se basant sur la minimisation d'énergie. Le modèle ne dépend essentiellement pas de l'apprentissage. Les algorithmes sont rapides, robustes avec des performances com- parables à celles des meilleures méthodes actuelles qui utilisent l'apprentissage. Cette méthode peut être donc utile pour le screening des génomes. Outre la performance de prédiction et de classification, cette étude donne une vue plus profonde de la structure des TMBs en tenant compte des contraintes physicochimiques des membranes biologiques. Les structures permutées prédites peuvent aussi aider à mieux comprendre le mécanisme du repliement des TMBs.

Les protéines transmembranaires canaux-β (TMBs) se trouvent dans les membranes externes des bactéries à Gram négatif, des mitochondries ainsi que des chloroplastes. Elles traversent entièrement la membrane cellulaire et exercent différentes fonctions importantes. Vu qu'il y a un petit nombre des structures des TMBs déterminées, en raison des difficultés avec les méthodes expérimentales, il est douteux que ces approches puis- sent bien trouver et prédire les TMBs qui ne sont pas homologues avec celles connues. Nous construisons un modèle de graphe pour la classification et la prédiction de structures super-secondaires permutées des TMBs à partir de leur séquence d'acides aminés, en se basant sur la minimisation d'énergie. Le modèle ne dépend essentiellement pas de l'apprentissage. Les algorithmes sont rapides, robustes avec des performances com- parables à celles des meilleures méthodes actuelles qui utilisent l'apprentissage. Cette méthode peut être donc utile pour le screening des génomes. Outre la performance de prédiction et de classification, cette étude donne une vue plus profonde de la structure des TMBs en tenant compte des contraintes physicochimiques des membranes biologiques. Les structures permutées prédites peuvent aussi aider à mieux comprendre le mécanisme du repliement des TMBs.

La compréhension des pathologies humaines et du mode d'action des médicaments passe par la prise en compte des réseaux d'interactions entre biomolécules. Les recherches récentes sur les systèmes biologiques produisent de plus en plus de données sur ces réseaux qui gouvernent les processus cellulaires. L'hétérogénéité et la multiplicité de ces données rendent difficile leur intégration dans les raisonnements des utilisateurs. Je propose ici des approches intégratives mettant en œuvre des techniques de gestion de données, de visualisation de graphes et de fouille de données, pour tenter de répondre au problème de l'exploitation insuffisante des données sur les réseaux dans la compréhension des phénotypes associés aux maladies génétiques ou des effets secondaires des médicaments. La gestion des données sur les protéines et leurs propriétés est assurée par un système d'entrepôt de données générique, NetworkDB, personnalisable et actualisable de façon semi-automatique. Des techniques de visualisation de graphes ont été couplées à NetworkDB pour utiliser les données sur les réseaux biologiques dans l'étude de l'étiologie des maladies génétiques entrainant une déficience intellectuelle. Des sous-réseaux de gènes impliqués ont ainsi pu être identifiés et caractérisés. Des profils combinant des effets secondaires partagés par les mêmes médicaments ont été extraits de NetworkDB puis caractérisés en appliquant une méthode de fouille de données relationnelles couplée à Network DB. Les résultats permettent de décrire quelles propriétés des médicaments et de leurs cibles (incluant l'appartenance à des réseaux biologiques) sont associées à tel ou tel profil d'effets secondaires.

Dans les dernières années, les réseaux Bayésiens (RB) sont devenus l'une des méthodes d'apprentissage automatique les plus puissantes permettant de modéliser graphiquement et de manière probabiliste différentes types de systèmes complexes. Un des problèmes communs dans l'apprentissage de la structure des RB est le problème des données de petites tailles. En effet, le résultat de l'apprentissage est sensible au nombre d'échantillons de données. En apprentissage automatique, les méthodes d'apprentissage ensemblistes telles que le bootstrap ou les algorithmes génétiques sont des méthodes souvent utilisées pour traiter le problème de la pauvreté de données. Toutefois, les méthodes existantes se limitent généralement à la fusion d'un ensemble de modèles, mais ne permettent pas de comparer deux ensembles de modèles. Inspiré par les résultats obtenus par les méthodes ensemblistes, nous proposons une nouvelle méthode basée sur le graphe quasi-essentiel (QEG - Quasi-Essential Graph) et l'utilisation d'un test multiple afin de comparer deux ensembles de RB. Le QEG permet de résumer et de visualiser graphiquement un ensemble de RB. Le test multiple permet de vérifier si les différences entre les deux ensembles de RB sont statistiquement significatives et de déterminer la position de ces différences. L'application sur des données synthétiques et expérimentales a démontré les différents intérêts de la méthode proposée dans la reconstruction des réseaux de régulation génétique et perspectivement dans les autres applications avec les données de petites tailles.

Ce mémoire est un recueil et une synthèse de plusieurs études en analyse en moyenne d'algorithmes et en bioinformatique. Il y est présenté des travaux allant de l'étude de problèmes sur les séquences à l'étude de systèmes biologiques, en gardant un fil conducteur fort: quelles que soient les applications, l'objet d'étude central est une source probabiliste qui produit des mots. Ces travaux trouvent des applications en bioinformatique qui se concrétisent par la mise au point d'algorithmes dédiés de recherche de motifs et la définition de tests statistiques et en biologie des systèmes biologiques avec des développements qui ont été appliqués, en collaboration étroite avec des équipes de biologistes, à des modèles biologiques réels.

Les processus morphogénétiques sont les processus qui sous-tendent l'émergence de la forme. Leur étude consiste à décrire, comprendre et expliquer comment les formes apparaissent et évoluent. Pour cela, une approche computationnelle basée sur la simulation numérique, c'est à dire sur la réalisation d'expérience in silico a été utilisée et appliquée à deux cas morphogénétiques en particulier. Le premier cas a concerné la motilité cellulaire, c'est à dire l'étude des mécanismes à l'origine des mouvements et de la forme de la cellule. Une plateforme de modélisation hybride a pour cela été développée. Elle couple un modèle continu des déformations membranaires qui résultent de la dynamique spatio-temporelle de l'actine à un modèle discret de type automate cellulaire pour rendre compte de la nature discrète des adhésions et des fibres du cytosquelette de la cellule. Plusieurs situations expérimentales ont été considérées de la migration de la cellule aux formes cellulaires observées sur des substrats patternés (c'est à dire qui présentent des motifs adhésifs contrôlés) et ont permis de développer progressivement les différents éléments de la plateforme. Le second cas morphogénétique considéré a concerné la croissance vasculaire à travers différentes approches. Une approche expérimentale a eu pour but de mettre en évidence l'impact de la rigidité du substrat sur la formation de cordons vasculaires in vitro. La seconde approche a porté sur le développement d'un modèle computationnel hybride pour rendre compte de la croissance vasculaire dans le contexte de l'angiogenèse tumorale. Le modèle hybride couple une formulation continue pour d écrire les processus de diffusion des différentes espèces moléculaires impliquées (tels que les facteurs de croissance ou l'oxygène) à une formulation discrète pour d écrire la migration individuelle des cellules endothéliales formant les vaisseaux. La structure modulaire du modèle computationnel a de plus permis d'int égrer les mécanismes d'adaptation du diamètre des vaisseaux qui résultent des contraintes hémodynamiques c'est à dire liées au flux sanguin. La plateforme computationnelle a été développée par la suite pour intégrer un module de croissance tumorale et un module sur les moyens d'actions thérapeutiques, dans le cadre du projet CATS pour Computer-Assisted Therapeutic Strategy. L'ambition de ce projet en cours de développement, est de mettre au point une tumeur virtuelle destinée à tester et à optimiser de nouveaux protocoles thérapeutiques.

La phylogénie permet de reconstituer l'histoire évolutive de séquences ainsi que des espèces qui les portent. Les récents progrès des méthodes de séquençage ont permis une inflation du nombre de séquences disponibles et donc du nombre d'arbres de gènes qu'il est possible de construire. La question qui se pose est alors d'optimiser la recherche d'informations dans ces arbres. Cette recherche doit être à la fois exhaustive et efficace. Pour ce faire, mon travail de thèse a consisté en l'écriture puis en l'utilisation d'un ensemble de programmes capables de parcourir et d'annoter les arbres phylogénétiques. Cet ensemble de programmes porte le nom de TPMS (Tree Pattern Matching Suite). Le premier de ces programmes (tpms_query) permet d'effectuer l'interrogation de collections à l'aide d'un formalisme dédie. Les possibilités qu'il offre sont : La détection de transferts horizontaux : Si un arbre de gènes présente une espèce branchée dans un arbre au milieu d'un groupe monophylétique d'espèces avec lesquelles elle n'est pas apparentée, on peut supposer qu'il s'agit d'un transfert horizontal, si ces organismes sont des procaryotes ou des eucaryotes unicellulaires. La détection d'orthologie : Si une partie d'un arbre de gènes correspond exactement à l'arbre des espèces, on peut alors supposer que ces gènes sont un ensemble de gènes d'orthologues. La validation de phylogénies connues : Quand l'arbre des espèces donne lieu à des débats, il peut est possible d'interroger une large collection d'arbres de gènes pour voir combien de familles de gènes correspondent à chaque hypothèse. Un autre programme, tpms_computations, permet d'effectuer des opérations en parallèle sur tous les arbres, et propose notamment l'enracinement automatique des arbres via différents critères, ainsi que l'extraction de sous arbres d'orthologues (séquence unique par espèce). Il propose aussi une méthode de détection automatique d'incongruences. La thèse présente le contexte, les différents algorithmes à la base de ces programmes, ainsi que plusieurs utilisations qui en ont été faites

In this thesis, we address the problem of identifying and quantifying variants (alternative splicing and genomic polymorphism) in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the idea that each variant corresponds to a recognizable pattern, a bubble, in a de Bruijn graph constructed from the RNA-seq reads, we propose a general model for all variants in such graphs. We then introduce an exact method, called KisSplice, to extract alternative splicing events and show that it outperforms general purpose transcriptome assemblers. We put an extra effort to make KisSplice as scalable as possible. In order to improve the running time, we propose a new polynomial delay algorithm to enumerate bubbles. We show that it is several orders of magnitude faster than previous approaches. In order to reduce its memory consumption, we propose a new compact way to build and represent a de Bruijn graph. We show that our approach uses 30% to 40% less memory than the state of the art, with an insignificant impact on the construction time. Additionally, we apply the techniques developed to list bubbles in two classical problems: cycle enumeration and the K-shortest paths problem. We give the first optimal algorithm to list cycles in undirected graphs, improving over Johnson's algorithm. This is the first improvement to this problem in almost 40 years. We then consider a different parameterization of the K-shortest (simple) paths problem: instead of bounding the number of st-paths, we bound the weight of the st-paths. We present new algorithms using exponentially less memory than previous approaches

Nous développons une approche générique pour comprendre comment différents régimes alimentaires peuvent influencer la qualité et la composition du lait. Cette question s'intègre dans le cadre du Flux Balance Analysis (FBA), qui consiste à analyser un réseau métabolique en optimisant un système de contraintes linéaires. Nous avons proposé une extension du FBA pour analyser la transformation des nutriments en intégrant des hypothèses biologiques utilisées par différents modèles numériques dans un modèle générique de la glande mammaire. Notre méthode permet de quantifier les précurseurs qui interviennent dans la composition des sorties du système, en calculant des contributions des entrées dans les sorties [AIO]. A l'aide de cette approche, nous avons montré que la transformation des nutriments du lait ne peut pas être modélisée par l'optimisation d'une combinaison linéaire des flux des réactions sur un modèle du métabolisme mammaire. Pour étudier plus précisément la flexibilité d'un réseau métabolique, nous avons proposé un algorithme e

La croissance exponentielle de la génération de données pour la bioinformatique couplée à une stagnation des fréquences d'horloge des processeurs modernes accentuent la nécessité de fournir des implémentation tirant bénéfice des capacités parallèles des ordinateurs modernes. Cette thèse se concentre sur des algorithmes et implementations pour des problèmes de bioinformatique. Plusieurs types de parallélisme sont décrits et exploités. Cette thèse présente des applications en génétique, avec un outil de détection de QTL paralllisé sur GPU, en comparaison de structures de protéines, avec un outil permettant de trouver des régions similaires entre protéines parallélisé sur CPU, ainsi qu'à l'analyse de larges graphes avec une implémentation multi-GPUs d'un nouvel algorithme pour le problème du "All-Pairs Shortest Path".