Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes. / In this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs.

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

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

[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents. Différents algorithmes ont été proposés pour inférer une histoire de duplication en tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions. Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces événements dans le modèle de duplication en tandem classique. Nos contributions sont les suivantes: • Intégrer les inversions dans un modèle de duplication en tandem simple (duplication d’un gène à la fois) et proposer un algorithme exact permettant de calculer le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de GRT. • Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans plusieurs espèces. • Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents. / [English] Tandemly arrayed genes (TAGs) represent an important fraction of most genomes. A fundamental mechanism at the origin of TAG clusters is unequal crossing-over during meiosis, leading to the duplication of chromosomal segments containing one or many adjacent genes. Such duplications are called tandem duplications, as the duplicated segment is placed next to the original one on the chromosome. Different algorithms have been proposed to infer the tandem duplication history of a TAG cluster. However, their applicability is limited in practice since they do not take into account other frequent evolutionary events such as inversion, inverted duplication and deletion. In this thesis, we propose different algorithmic approaches allowing to integrate these evolutionary events in the original tandem duplication model of evolution. Our contributions are summarized as follows: • We integrate inversion events in a tandem duplication model restricted to single gene duplications, and we propose an exact algorithm allowing to compute the minimum number of inversions explaining the evolution of a TAG cluster. • We generalize this model to the study of orthologous TAG clusters in different species. • We propose an algorithm allowing to infer the evolutionary history of a TAG cluster through tandem duplication, inverted duplication, inversion and deletion of chromosomal segments containing one or many adjacent genes.

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

Face à l'intérêt grandissant pour les forêts mélangées, des d'outils et des modèles adaptés à leur gestion sont nécessaires. L'objectif de cette thèse est de montrer comment la construction et la comparaison de modèles ayant différents niveaux de détail peuvent nous aider à choisir le niveau le plus approprié pour modéliser la croissance d'un peuplement mélangé dans un contexte d'application donné. A partir de données récoltées dans des peuplements mélangés chêne sessile (Quercus petraea L.) pin sylvestre (Pinus sylvestris L.), nous avons construit une famille de modèles à différents niveaux de détail : un modèle arbre indépendant des distances (MAID), un modèle arbre dépendant des distances (MADD), trois modèles peuplement et un modèle intermédiaire entre le MAID et le MADD utilisant des distributions de voisinage. Pour que la comparaison de ces modèles soit pertinente, nous avons assuré une cohérence entre les modèles en utilisant plusieurs approches. Ces modèles nous ont permis d'acquérir des connaissances sur la croissance et la dynamique de ces forêts en particulier sur les interactions spatiales et temporelles entre le chêne et le pin. Ainsi le MAID a permis de montrer qu'il peut y avoir des phénomènes de compensation de croissance entre les deux espèces. Le MADD a permis de montrer que dans ces peuplements la compétition intraspécifique est supérieure à la compétition interspécifique. Un modèle peuplement obtenu à partir du MADD a permis d'étudier l'influence du taux de mélange sur la production. Pour évaluer la qualité prédictive des modèles, nous avons utilisé un jeu de données indépendant obtenu en partageant nos données avant la construction des modèles. Nous avons ainsi montré que le MAID était plus performant que le MADD pour prédire les accroissements individuels. Les modèles ont aussi été comparés sur des exemples d'applications mettant en œuvre des simulations à court ou moyen terme. La démarche proposée présente un intérêt aussi bien pour la compréhension du phénomène étudié que pour sa modélisation dans un but prédictif. En regroupant l'ensemble des résultats acquis, ce travail nous a permis d'apprécier la pertinence d'un type de modèle en fonction du contexte d'utilisation. Cette démarche très générale pourrait être appliquée à la modélisation d'autres processus comme la mortalité ou la régénération.

Cette thèse s'intéresse d'une part au problème de décomposition technologique orienté surface sur des réseaux programmables de type FPGAs (Field Programmable Gate Arrays) et d'autre part à la synthèse des macro-générateurs sur ASICs et plus précisément de la synthèse des additionneurs. La décomposition s'articule autour de deux axes essentiels: tout d'abord, il s'agit d'optimiser la taille de la représentation des fonctions booléennes. Les représentations de base choisies ici sont les ROBDDs (Reduced Ordered Binary Decision Diagrams) ainsi qu'une structure dérivée, les ITE (If Then Else). La deuxième étape concerne la décomposition proprement dite. Les technologies cibles sont ici des FPGAs à base de LUT-k (Look Up Table), en particulier les FPGAs XC5200 de Xilinx et Orca de AT&T. Les deux méthodes de décomposition technologique orienté surface proposées permettent une décomposition hétérogène en prenant en compte non pas une seule configuration mais un ensemble de configurations possibles de la cellule cible. La première méthode est fondée sur un parcours descendant et optimisé du ROBDD. La seconde méthode s'appuie sur une modélisation en recouvrement d'hypergraphe du problème de décomposition technologique. Dans les deux méthodes, le coût exact en terme de surface finale du circuit est pris en compte à chaque étape de la décomposition. L'étude menée dans la deuxième partie de la thèse sur la macro-génération conduit dans un premier temps à l'exploration de l'espace des solutions possibles puis à l'optimisation d'une solution sélectionnée par un algorithme de dérivation discrète. L'utilisation d'un filtre permet la restriction de l'espace des solutions à explorer et d'autre part guide le processus de dérivation en éliminant les solutions trivialement médiocres. La combinaison des processus d'exploration et de dérivations permet la génération de macros dont les caractéristiques physiques sont les plus proches possibles de celles fixées par un utilisateur potentiel. Ces méthodes ont été intégrées au sein d'un outil universitaire ASYL+ développé au laboratoire CSI

[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents. Différents algorithmes ont été proposés pour inférer une histoire de duplication en tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions. Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces événements dans le modèle de duplication en tandem classique. Nos contributions sont les suivantes: • Intégrer les inversions dans un modèle de duplication en tandem simple (duplication d’un gène à la fois) et proposer un algorithme exact permettant de calculer le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de GRT. • Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans plusieurs espèces. • Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents. / [English] Tandemly arrayed genes (TAGs) represent an important fraction of most genomes. A fundamental mechanism at the origin of TAG clusters is unequal crossing-over during meiosis, leading to the duplication of chromosomal segments containing one or many adjacent genes. Such duplications are called tandem duplications, as the duplicated segment is placed next to the original one on the chromosome. Different algorithms have been proposed to infer the tandem duplication history of a TAG cluster. However, their applicability is limited in practice since they do not take into account other frequent evolutionary events such as inversion, inverted duplication and deletion. In this thesis, we propose different algorithmic approaches allowing to integrate these evolutionary events in the original tandem duplication model of evolution. Our contributions are summarized as follows: • We integrate inversion events in a tandem duplication model restricted to single gene duplications, and we propose an exact algorithm allowing to compute the minimum number of inversions explaining the evolution of a TAG cluster. • We generalize this model to the study of orthologous TAG clusters in different species. • We propose an algorithm allowing to infer the evolutionary history of a TAG cluster through tandem duplication, inverted duplication, inversion and deletion of chromosomal segments containing one or many adjacent genes.

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

Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k –1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n–1)/2 – c(n–2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 –5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) – 2)/2 avec c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , où j(j –1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n – 3)(n – 4) + 3n – 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 – 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes. / A c-edge-colored graph Gc is a graph whose edges are colored by a given set of colors. A subgraph of Gc is proper if no two adjacent edges have the same color.A c-edge-colored graph or multigraph Gc is k-linked (respectively k-edge-linked) if for any 2k distinct vertices, say x1 y1 , x2 y2 , ..., xk yk , there exist k vertex-disjoint (respectively edge-disjoint) proper paths joining x1 to y1 , x2 to y2 , ... , xk to yk .A proper spanning tree of a graph Gc is a spanning tree such that any two adjacent edges differ in colors.A weak spanning tree is a spanning rooted tree such that there exists a proper path between the root and every vertex of the graph.In the first part of this thesis, we provide conditions which are sufficient for an edge-colored graph to be k-linked. It is a classic problem in graph theory , with many applications. So, we established among others the following results.A) Every 2-edge-colored multigraph of order n ≥ 242k such that dc(Gc) ≥ n/2+k –1, is k-linked.B) Every c-edge-colored multigraph of order n ≥ 2k and size m≥ cn(n–1)/2 – c(n–2k +1)+1 is k-linked.C) Every c-edge-colored multigraph of order n ≥ 2k is k-edge-linked if for each vertex x, dc(x) ≥ n/2.D) Every 2-edge-colored multigraph of order n ≥ 2k ≥ 10 and size m ≥ n2 – 5n + 11 is k-edge-linked if for each vertex x, dc(x) ≥ 1.In the second part of this thesis, two other classic problems in graph theory are treated in edge-colored version: spanning trees and hamiltonian paths. We give below some results.E) Every c-edge-colored simple k-connected graph of order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree.F) Every c-edge-colored connected graph Gc of rainbow degree rd(Gc)=k and order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree. G) Every c-edge-colored simple k-connected graph of order n ≥ ((k + j)2 + 3(k + j) – 2)/2 and c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , with j(j –1)=k , has a weak spanning tree.H) Every c-edge-colored multigraph Gc of order n ≥ 14 and size m ≥ (n – 3)(n – 4) + 3n – 2 such that rd(Gc) = 2, has a proper hamiltonian path.I) Every c-edge-colored multigraph of order n ≠ 5, 7 and size m ≥ n2 – 3n + 4, has a proper hamiltonian path.Most of the given results are the best possible with regard to the properties on the sufficient conditions.