De nombreuses applications informatiques nécessitent l’utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d’édition. Celle-ci correspond au nombre minimal d’opérations d’édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l’application traitée, il est possible de paramétrer la distance d’édition en associant à chaque opération d’édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d’apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L’algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l’aide d’un échantillon d’apprentissage composé de paires d’exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l’efficacité de l’apprentissage par rapport à l’utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d’états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d’entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques / In computer science, a lot of applications use distances. In the context of structured data, strings or trees, we mainly use the edit distance. The edit distance is defined as the minimum number of edit operation (insertion, deletion and substitution) needed to transform one data into the other one. Given the application, it is possible to tune the edit distance by adding a weight to each edit operation. In this work, we use a supervised machine learning approach to learn the weight of edit operation. The exploited algorithm, called Expectation-Maximisation, is a method for finding maximum likelihood estimates of parameters in a model given a learning sample of pairs of similar examples. The first contribution is an extension of earlier works on string to trees. The model is represent by a transducer with a single state. We apply successfully our method on a handwritten character recognition task. In a last part, we introduce a new model on strings under constraints. The model is made of a finite set of states where the transitions are constrained. A constraint is a finite set of boolean functions defined over an input string and one of its position. We show the relevance of our approach on a molecular biology task. We consider the problem of detecting Transcription Factor Binding Site in DNA sequences

La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes. Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,...,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées. Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.

De nombreuses applications informatiques nécessitent l'utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d'édition. Celle-ci correspond au nombre minimal d'opérations d'édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l'application traitée, il est possible de paramétrer la distance d'édition en associant à chaque opération d'édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d'apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L'algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l'aide d'un échantillon d'apprentissage composé de paires d'exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l'efficacité de l'apprentissage par rapport à l'utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d'états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d'entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques

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

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks. Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,...,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations. Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class. / La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes. Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,...,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées. Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.

L'augmentation exponentielle du nombre d'images nécessite des moyens efficaces pour les classer en fonction de leur contenu visuel. Le sac de mot visuel (Bag-Of-visual-Words, BOW), en raison de sa simplicité et de sa robustesse, devient l'approche la plus populaire. Malheureusement, cette approche ne prend pas en compte de l'information spatiale, ce qui joue un rôle important dans les catégories de modélisation d'image. Récemment, Lazebnik ont introduit la représentation pyramidale spatiale (Spatial Pyramid Representation, SPR) qui a incorporé avec succès l'information spatiale dans le modèle BOW. Néanmoins, ce système de correspondance rigide empêche la SPR de gérer les variations et les transformations d'image. L'objectif principal de cette thèse est d'étudier un modèle de chaîne de correspondance plus souple qui prend l'avantage d'histogrammes de BOW locaux et se rapproche de la correspondance de la chaîne. Notre première contribution est basée sur une représentation en chaîne et une nouvelle distance d'édition (String Matching Distance, SMD) bien adapté pour les chaînes de l'histogramme qui peut calculer efficacement par programmation dynamique. Un noyau d'édition correspondant comprenant à la fois d'une pondération et d'un système pyramidal est également dérivée. La seconde contribution est une version étendue de SMD qui remplace les opérations d'insertion et de suppression par les opérations de fusion entre les symboles successifs, ce qui apporte de la souplesse labours et correspond aux images. Toutes les distances proposées sont évaluées sur plusieurs jeux de données tâche de classification et sont comparés avec plusieurs approches concurrentes / The exponential increasing of the number of images requires efficient ways to classify them based on their visual content. The most successful and popular approach is the Bag of visual Word (BoW) representation due to its simplicity and robustness. Unfortunately, this approach fails to capture the spatial image layout, which plays an important roles in modeling image categories. Recently, Lazebnik et al (2006) introduced the Spatial Pyramid Representation (SPR) which successfully incorporated spatial information into the BoW model. The idea of their approach is to split the image into a pyramidal grid and to represent each grid cell as a BoW. Assuming that images belonging to the same class have similar spatial distributions, it is possible to use a pairwise matching as similarity measurement. However, this rigid matching scheme prevents SPR to cope with image variations and transformations. The main objective of this dissertation is to study a more flexible string matching model. Keeping the idea of local BoW histograms, we introduce a new class of edit distance to compare strings of local histograms. Our first contribution is a string based image representation model and a new edit distance (called SMD for String Matching Distance) well suited for strings composed of symbols which are local BoWs. The new distance benefits from an efficient Dynamic Programming algorithm. A corresponding edit kernel including both a weighting and a pyramidal scheme is also derived. The performance is evaluated on classification tasks and compared to the standard method and several related methods. The new method outperforms other methods thanks to its ability to detect and ignore identical successive regions inside images. Our second contribution is to propose an extended version of SMD replacing insertion and deletion operations by merging operations between successive symbols. In this approach, the number of sub regions ie. the grid divisions may vary according to the visual content. We describe two algorithms to compute this merge-based distance. The first one is a greedy version which is efficient but can produce a non optimal edit script. The other one is an optimal version but it requires a 4th degree polynomial complexity. All the proposed distances are evaluated on several datasets and are shown to outperform comparable existing methods.

Mémoire en recherche-création / L’essai Études des procédés d’appropriation esthétique de l’astronautique dans Nous trois de Jean Echenoz explore les stratégies développées par l’écrivain Jean Echenoz pour engager un dialogue inédit avec le thème de l’astronautique, qu’il met en récit dans son sixième roman. Caractérisé par une adhésion ludique et distanciée au genre romanesque, Nous trois multiplie les jeux stylistiques, référentiels et langagiers, inscrivant son univers thématique au sein d’une esthétique de la précarité, qui n’épargne aucune dimension de l’œuvre. La structure du récit induit une part troublante d’équivoque autour de l’identité des personnages et des instances narratives. Sur le plan diégétique, le romancier met en place un univers instable et inquiétant dans lequel le milieu de l’astronautique est exposé sans complaisance. Tirant profit de la précarité inhérente au langage, Echenoz s’approprie un lexique rattaché au thème de l’astronautique qu’il exploite à des fins stylistiques. Le roman Hellen-Freischmann raconte le parcours d’un personnage écrivain singulier qui cherche à faire publier un manuscrit ayant pour protagonistes des corps célestes. Cette trame narrative a pour contrepoint un récit mettant en scène l’éditrice d’une maison d’édition prestigieuse, qui doit composer avec cette soumission atypique. Ces personnages évoluent au sein d’un univers sombre où l’étrangeté côtoie le familier, où le vraisemblable menace de basculer dans le fantastique, où la fiction contamine la réalité. Le roman est porté par une voix narrative inusitée, instable, caractérisée par des jeux complexes de focalisation, des registres contrastés et une certaine indécidabilité quant au rapport de la narration à l’histoire racontée. Ce narrateur assimile une nomenclature propre à l’astronomie, qui sert tant le développement de l’intrigue que les jeux stylistiques du roman. / The essay entitled Études des procédés d’appropriation esthétique de l’astronautique dans Nous trois de Jean Echenoz explores the strategies employed by the author Jean Echenoz to engage in a new dialogue with the theme of astronautics, which he brings into play in his sixth novel. Characterized by a playful and distanced adherence to literary fiction, Nous trois plays with styles, references and language, inscribing his universe into an esthetic of precariousness, sparing no dimension of his work. His narrative structure induces a troubling ambiguity around the characters’ identities and narrative instances. On a diegesis level, the author sets an unstable and unsettling universe in which the subject of astronautics is exposed without any complacency. Taking advantage of the language’s inherent precariousness, Echenoz takes ownership of the astronautics’ lexicon which he employs to further his style. The novel Hellen-Freischmann narrates the journey of a peculiar author whose goal is to publish his manuscript starring celestial bodies as protagonists. This narrative is intertwined with the tale of a publisher from a prestigious publishing house who must come to terms with this atypical submission. These characters evolve within a dark universe where strangeness stands alongside familiarity, where likelihood threatens to fall into fantasy, and fiction contaminates reality. The novel is carried by an unusual and unstable voice, characterized by complex plays on focus, contrasted language use, and a certain indecision towards the role of narration in the story told. This playful narrator incorporates a nomenclature proper to astronomy, which serves both the intrigue and the style of the novel.

Ces dernières années, l'importance cruciale des métriques en apprentissage automatique a mené à un intérêt grandissant pour l'optimisation de distances et de similarités en utilisant l'information contenue dans des données d'apprentissage pour les rendre adaptées au problème traité. Ce domaine de recherche est souvent appelé apprentissage de métriques. En général, les méthodes existantes optimisent les paramètres d'une métrique devant respecter des contraintes locales sur les données d'apprentissage. Les métriques ainsi apprises sont généralement utilisées dans des algorithmes de plus proches voisins ou de clustering.Concernant les données numériques, beaucoup de travaux ont porté sur l'apprentissage de distance de Mahalanobis, paramétrisée par une matrice positive semi-définie. Les méthodes récentes sont capables de traiter des jeux de données de grande taille.Moins de travaux ont été dédiés à l'apprentissage de métriques pour les données structurées (comme les chaînes ou les arbres), car cela implique souvent des procédures plus complexes. La plupart des travaux portent sur l'optimisation d'une notion de distance d'édition, qui mesure (en termes de nombre d'opérations) le coût de transformer un objet en un autre.Au regard de l'état de l'art, nous avons identifié deux limites importantes des approches actuelles. Premièrement, elles permettent d'améliorer la performance d'algorithmes locaux comme les k plus proches voisins, mais l'apprentissage de métriques pour des algorithmes globaux (comme les classifieurs linéaires) n'a pour l'instant pas été beaucoup étudié. Le deuxième point, sans doute le plus important, est que la question de la capacité de généralisation des méthodes d'apprentissage de métriques a été largement ignorée.Dans cette thèse, nous proposons des contributions théoriques et algorithmiques qui répondent à ces limites. Notre première contribution est la construction d'un nouveau noyau construit à partir de probabilités d'édition apprises. A l'inverse d'autres noyaux entre chaînes, sa validité est garantie et il ne comporte aucun paramètre. Notre deuxième contribution est une nouvelle approche d'apprentissage de similarités d'édition pour les chaînes et les arbres inspirée par la théorie des (epsilon,gamma,tau)-bonnes fonctions de similarité et formulée comme un problème d'optimisation convexe. En utilisant la notion de stabilité uniforme, nous établissons des garanties théoriques pour la similarité apprise qui donne une borne sur l'erreur en généralisation d'un classifieur linéaire construit à partir de cette similarité. Dans notre troisième contribution, nous étendons ces principes à l'apprentissage de métriques pour les données numériques en proposant une méthode d'apprentissage de similarité bilinéaire qui optimise efficacement l'(epsilon,gamma,tau)-goodness. La similarité est apprise sous contraintes globales, plus appropriées à la classification linéaire. Nous dérivons des garanties théoriques pour notre approche, qui donnent de meilleurs bornes en généralisation pour le classifieur que dans le cas des données structurées. Notre dernière contribution est un cadre théorique permettant d'établir des bornes en généralisation pour de nombreuses méthodes existantes d'apprentissage de métriques. Ce cadre est basé sur la notion de robustesse algorithmique et permet la dérivation de bornes pour des fonctions de perte et des régulariseurs variés / In recent years, the crucial importance of metrics in machine learningalgorithms has led to an increasing interest in optimizing distanceand similarity functions using knowledge from training data to make them suitable for the problem at hand.This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms.When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets.Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another.We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored.In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (epsilon,gamma,tau)-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (epsilon,gamma,tau)-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.

Les années 2000-2010 ont été marquées par la popularité grandissante du web et des réseaux sociaux, mais aussi par l'émergence d'une trentaine de nouvelles maisons d'édition littéraire au Québec. Un certain nombre d'entre elles ont réussi à se démarquer, notamment en dévoilant des auteurs qui ont remporté des prix littéraires et en obtenant une réception critique fort envieuse. Intriguée par cette réalite, j'ai choisi de consacrer mon mémoire de maîtrise au phénomène d'apparition de nouvelles maisons d'édition littéraire québécoises et à leur utilisation du web. Il m'a semblé que le fait de maintenir à jour un site web et d'être actifs sur les réseaux sociaux Facebook et Twitter offrait l'occasion aux nouveaux éditeurs de développer des initiatives promotionnelles leur permettant d'acquérir une plus grande visibilité dans le paysage littéraire du Québec, de se constituer une communauté de lecteurs et d'accroître leur capital symbolique. Le présent mémoire comprend, dans un premier temps, une étude du phénomène d'émergence de nouvelles maisons d'édition littéraire au Québec de 2000 à 2010. Je me suis ensuite consacrée au cas de trois maisons d'édition -- Alto, Le Quartanier et Marchand de feuilles -- pour analyser, dans un deuxième temps, leur site web. Puis, dans un troisième temps, j'ai étudié leur utilisation des réseaux sociaux Facebook et Twitter. Au final, il m'est apparu que sans être totalement innovatrices, les stratégies de promotion, de représentation et de réseautage développées sur le web et les réseaux sociaux permettent aux nouveaux éditeurs de se construire une image de marque forte, de susciter l'intérêt d'une communauté de lecteurs, d'atteindre une notoriété dans le champ littéraire québécois et d'accumuler du capital symbolique.

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.<p><p>Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations.<p><p>Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class.<p>/<p>La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes.<p><p>Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées.<p><p>Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished