Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

L'analyse de réseaux (représentés par des graphes) est une composante importante dans la compréhension de systèmes complexes issus de nombreuses disciplines telles que la biologie, la géographie ou la sociologie. Nous nous intéressons dans cette thèse aux décompositions de ces réseaux. Ces décompositions sont utiles pour la compression des données, la détection de communautés ou la visualisation de graphes. Une décomposition possible est un partitionnement hiérarchique des sommets du graphe. Nous traitons de l'évaluation de la qualité de telles structures (leur capacité à bien capturer la topologie du graphe) par le biais de mesures de qualité. Nous discutons ensuite l'utilisation de ces mesures en tant que fonctions objectives à maximiser dans le cadre d'algorithmes de partitionnement. Enfin, nous nous intéressons à la définition de métaphores visuelles efficaces permettant de représenter différentes décompositions de graphes.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

La décomposition modulaire apparait naturellement dans différents domaines de la combinatoire (et en particulier les graphes). Cette décomposition se révèle être un puissant outil de description d'objets discrets. Elle est aussi utilisée comme étape préliminaire à nombreux d'algorithmes.<br /><br />Dans ce mémoire, nous nous intéressons au calcul de la décomposition modulaire. Malgré la publication d'algorithmes linéaires au milieu des années 90, la recherche sur ce problème n'a pas cessée. Nous faisons le point sur les différentes avancées et techniques utilisées.

Cette thèse traite deux types de problèmes algorithmiques : des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes et des problèmes de découverte de structures secondaires d'ARN. Nous étudions des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes. Ce problème apparaît, par exemple, lorsque l'on souhaite calculer "en place" un système d'équations. Une façon naturelle d'aborder ce problème est de se placer dans le cadre général de la théorie des graphes et des graphes bipartis en particulier. Nous présentons de nombreux résultats de complexité - essentiellement de NP-complétude - liés à ce problème et introduisons quelques extensions dont nous précisons toujours la complexité. Certaines familles d'ARN sont très précisément définies par des motifs de séquence, et des contraintes structurelles secondaires et tertiaires. La plupart des outils ne sont pas adaptés puisqu'ils n'intègrent pas toutes les connaissances sur la molécule lors de l'exploration des banques de séquences. D'où l'intérêt d'algorithmes de recherche assurant une recherche en séquence et structure par le biais d'un descripteur défini par l'utilisateur intégrant l'ensemble des connaissances caractérisant l'ARN à détecter. Une nouvelle façon d'aborder ce problème consiste en l'étude de problèmes algorithmiques sur les graphes d'intersection d'un ensemble de 2-intervalles. Cette notion de 2-intervalles se trouve dans la lignée des études actuelles en matière d'algorithmique de graphes où l'on étudie de plus en plus les structures des graphes issues de modèles géométriques. Nous présentons plusieurs résultats de complexité et montrons en particulier que la recherche de motifs dans un ensemble de 2-intervalles est un problème NP-complet. Nous nous intéressons, plus particulièrement, à appliquer ces travaux pour la prédiction de motifs biologiques structurés. Plus spécifiquement, nous avons mis au point l'algorithme ORANGE pour la prédiction des introns auto-catalytiques de groupe 1 dans de grandes séquences génomiques. Cet algorithme est une amélioration de l'algorithme CITRON mis au point par F. Lisacek et F. Michel du point de vue de la rapidité d'exécution. De plus, une mise-en-œuvre de l'algorithme ORANGE est accessible en ligne sur Internet.

Dans ce manuscrit, nous proposons de concevoir et de mettre en oeuvre un environnement logiciel pour une "gestion guidée par les modèles" des changements dans les architectures des applications distribuées coopératives. Les aspects adaptabilité des applications, les aspects transformations de graphe et les aspects particuliers des applications distribuées coopératives sont étudiés. Une approche d'adaptation s'appuyant sur une modélisation par les graphes et un style architectural de type Poducteur/Consommateur est présentée pour des applications communicantes collaboratives sensibles au contexte. Une démarche de raffinement est proposée permettant de garantir un certain degré d'adaptabilité en faisant un compromis entre les différents paramètres du contexte. Ces travaux de recherche ont aussi permis de définir un cadre algorithmique générique de reconfiguration architecturale multi-niveaux pour la sélection des architectures de déploiement les plus adaptées à un contexte et aux situations associées. Ce cadre a été appliqué au cas de la communication et de la coopération de groupe. Elle a aussi permis de modéliser le style architectural Producteur/Consommateur pour une communication orientée évènement. Des règles d'adaptation ont été définies. Elles comportent une partie basée sur SWRL pour la description du contexte et des règles d'adaptation, et une partie basée sur les grammaires de graphes pour la transformation des configurations de déploiement

Pour modéliser au mieux les phénomènes linguistiques dans les systèmes de traitement automatique des langues (traduction, analyse, etc.), il faut disposer de ressources de qualité. Or, les ressources existantes sont souvent incomplètes et ne permettent pas de traiter correctement les données. Cette thèse s'intéresse à l'acquisition de connaissances linguistiques, plus précisément à leur extraction à partir de corpus. Nous étudions en particulier le problème des collocations, ces couples de termes dont l'un est choisi en fonction de l'autre pour exprimer un sens particulier (comme " pluie battante " où " pluie " exprime l'intensification). Pour permettre l'acquisition de données à grande échelle, il faut la rendre facile à réaliser de manière automatique, et simple à paramétrer par des linguistes aux connaissances limitées en programmation ; cela nécessite une modélisation adaptée et précise des données et des processus. Nous avons réalisé et décrivons MuLLinG, modèle de graphes linguistiques multiniveau, où chaque niveau représente l'information d'une manière différente,et les opérations de manipulation de ces graphes. Ce modèle permet de représenter et traiter divers types de ressources. En effet, les opérations associées ont été écrites pour être les plus génériques possibles : elles sont indépendantes de ce que peuvent représenter les nœuds et les arcs du graphe, et de la tâche à réaliser. Cela permet à notre modèle, mis en œuvre et utilisé pour plusieurs expérimentations (entre autres l'extraction de collocations), de voir un processus parfois complexe d'extraction de connaissances linguistiques comme une succession d'opérations simples de manipulation de graphes.

Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrée (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques

La délimitation précise du contour des lésions pigmentées sur des images est une première étape importante pour le diagnostic assisté par ordinateur du mélanome. Cette thèse présente une nouvelle approche de la détection automatique du contour des lésions pigmentaires sur des images couleurs ou multispectrales de la peau. Nous présentons d'abord la notion de minimisation d'énergie par coupes de graphes en terme de Maxima A-Posteriori d'un champ de Markov. Après un rapide état de l'art, nous étudions l'influence des paramètres de l'algorithme sur les contours d'images couleurs. Dans ce cadre, nous proposons une fonction d'énergie basée sur des classifieurs performants (Machines à support de vecteurs et Forêts aléatoires) et sur un vecteur de caractéristiques calculé sur un voisinage local. Pour la segmentation de mélanomes, nous estimons une carte de concentration des chromophores de la peau, indices discriminants du mélanomes, à partir d'images couleurs ou multispectrales, et intégrons ces caractéristiques au vecteur. Enfin, nous détaillons le schéma global de la segmentation automatique de mélanomes, comportant une étape de sélection automatique des "graines" utiles à la coupure de graphes ainsi que la sélection des caractéristiques discriminantes. Cet outil est comparé favorablement aux méthodes classiques à base de coupure de graphes en terme de précision et de robustesse.

Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.