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

Ce mémoire traite d'une méthode bayésienne, analysée par Marchand et Strawderman (2013), pour la construction d'intervalles bayésiens pour des modèles de densités continues avec contrainte sur l'espace des paramètres Θ. Notamment, on obtiendra une classe d'intervalles bayésiens Iπ0,α(.), associés à la troncature d'une loi a priori non informative π0 et générés par une fonction de distribution α(.), avec une probabilité de recouvrement bornée inférieurement par 1-α/1+α. Cette classe inclut la procédure HPD donnée par Marchand et Strawderman (2006) dans le cas où la densité sous-jacente d'un pivot est symétrique. Plusieurs exemples y illustrent la théorie étudiée. Finalement, on présentera de nouveaux résultats pour la probabilité de recouvrement des intervalles bayésiens appartenant à la classe étudiée pour des densités log-concaves. Ces résultats établissent la borne inférieure à 1- 3α/2 et généralisent les résultats de Marchand et al.(2008) tenant sous une hypothèse de symétrie.

En bioinformatique, un des problèmes très étudiés est la reconstitution des événements évolutifs qui transforment un génome A en un autre génome B. L'ordre des gènes dans les génomes est souvent modélisé par des permutations signées. Dans ce travail, nous définissons des liens entre le problème de tri des permutations signées par inversions et la conservation des structures combinatoires communes aux génomes à comparer. En utilisant les arbres des intervalles forts (Bergeron et al. (3)), nous démontrons que même si le calcul d'un scénario parfait et parcimonieux est difficile (Figeac et Varré (11)), il peut se faire d'une façon efficace pour une grande classe de permutations. Nous avons appliqué ces résultats à la comparaison des chromosomes X de l'humain, de la souris et du rat, basée sur les données de l'article de Gibbs et al. (12). ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Génomique comparée, Scénarios d'évolution, Tri par inversions, Intervalles communs.

Le but principal de ce travail est d'apporter une synthèse des travaux effectués sur les algorithmes capables d'identifier des groupes de gènes, ou des segments de génomes, communs à différentes espèces. Nous nous limitons à une approche basée sur la modélisation des génomes à l'aide de permutations, où les groupes d'éléments conservés entre différents génomes sont définis par la notion d'intervalles communs. L'étude approfondie de cette problématique nous a aussi permis d'innover et de présenter un nouvel algorithme plus général. Ce travail comporte donc deux aspects principaux, bien que le second soit intercalé dans le premier : une partie synthèse et une partie innovatrice. Après un survol des notions de bases, la partie synthèse présente les premiers algorithmes qui permettent de calculer les intervalles communs, puis l'approche de Bergeron et al. (2005) qui a grandement simplifié les premières solutions. Cette partie comprend aussi les algorithmes des mêmes auteurs qui calculent les intervalles communs dits forts, et une discussion sur les avantages de leur utilisation par rapport aux intervalles communs classiques. La partie innovatrice présente un nouvel algorithme qui généralise deux algorithmes de Bergeron et al. (2005). Nous concluons cette étude en constatant l'extrême simplicité et la grande efficacité, autant théorique que pratique, des plus récents algorithmes et nous croyons peu vraisemblable qu'il soit possible d'en améliorer la performance de façon significative. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithmique, Génomique comparée, Intervalles communs, Permutations.

La génomique comparative étudie les similarités et/ou les dissimilarités entre génomes et permet d'établir des relations entre les espèces afin notamment de construire des phylogénies. Elle permet également de mettre en évidence des régions conservées au sein des génomes et de trouver ainsi des ensembles de gènes impliqués dans des processus biologiques conservés au cours de l'évolution. Dans ce mémoire, nous nous intéressons au calcul de mesures entre deux génomes en présence de gènes dupliqués, et plus particulièrement aux mesures à base de points de cassure, d'adjacences, d'intervalles communs et d'intervalles conservés. Suivant une démarche informatique, nous proposons tout d'abord une étude avancée de la complexité algorithmique des problèmes rencontrés, en prouvant notamment pour la plupart d'entre eux soit leur NP-Complétude soit leur APX-Difficulté. Par la suite, nous exposons plusieurs méthodes de calcul de mesures entre deux génomes, à savoir (i) une approche exacte basée sur une transformation en un problème de contraintes à variables booléennes, (ii) une heuristique et (iii) une méthode hybride qui s'appuie sur la méthode exacte et l'heuristique proposées. Par une étude sur un jeu de données réel, nous montrons les qualités respectives de ces méthodes. Enfin, nous proposons un protocole de calcul des intervalles communs et mettons en évidence, par son utilisation et par un outil de visualisation, l'aspect fonctionnel de certains intervalles communs.

.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

Ce mémoire traite d'une application pratique de deux méthodes statistiques non paramétriques : le bootstrap et le test de permutation. La méthode du bootstrap a été proposée par Bradley Efron (1979) comme une alternative aux modèles mathématiques traditionnels dans des problèmes d'inférence complexe; celle-ci fournit plusieurs avantages sur les méthodes d'inférence traditionnelles. L'idée du test de permutation est apparue au début du XXème siècle dans les travaux de Neyman, Fisher et Pitman. Le test de permutation, très intensif quant au temps de calcul, est utilisé pour construire une distribution empirique de la statistique de test sous une hypothèse afin de la comparer avec la distribution de la même statistique sous l'hypothèse alternative. Notre objectif est de déterminer l'intervalle de confiance pour un estimateur à maximum de vraisemblance d'une méthode de cartographie génétique existante (MapArg, Larribe et al. 2002) et de tester la qualité de cet estimateur, c'est-à-dire d'établir des seuils de signification pour la fonction de la vraisemblance. Les deux méthodes utilisent le calcul répétitif d'une même statistique de test sur des échantillons obtenus à partir de l'échantillon initial, soit avec le «bootstrap», soit avec des permutations. Dans un test d'hypothèse, les deux méthodes sont complémentaires. Le but de ce mémoire est de proposer différentes variantes pour la construction de l'intervalle de confiance, et de tester des hypothèses distinctes, afin de trouver la meilleure solution adaptée pour la méthode MapArg. Pour faciliter la compréhension des décisions prises, un rappel de l'inférence statistique et des tests d' hypothèse est fait dans les chapitres 4 et 5 où la théorie du bootstrap et celle de test de permutation sont présentées. Comme les qualités d'un estimateur dépendent de la méthode utilisée pour le calculer, les chapitres 1 et 2 présentent la base biologique et la base en mathématiques sur lesquelles la méthode MapArg est construite, tandis qu'on trouvera dans le chapitre 3 une explication de la méthode MapArg. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Mutation, Recombinaison, Coalescence, Cartographie génétique, «Bootstrap», Test de permutation.

Ce m??moire traite d'une m??thode bay??sienne, analys??e par Marchand et Strawderman (2013), pour la construction d'intervalles bay??siens pour des mod??les de densit??s continues avec contrainte sur l'espace des param??tres ??. Notamment, on obtiendra une classe d'intervalles bay??siens I??0,??(.), associ??s ?? la troncature d'une loi a priori non informative ??0 et g??n??r??s par une fonction de distribution ??(.), avec une probabilit?? de recouvrement born??e inf??rieurement par 1-??/1+??. Cette classe inclut la proc??dure HPD donn??e par Marchand et Strawderman (2006) dans le cas o?? la densit?? sous-jacente d'un pivot est sym??trique. Plusieurs exemples y illustrent la th??orie ??tudi??e. Finalement, on pr??sentera de nouveaux r??sultats pour la probabilit?? de recouvrement des intervalles bay??siens appartenant ?? la classe ??tudi??e pour des densit??s log-concaves. Ces r??sultats ??tablissent la borne inf??rieure ?? 1- 3??/2 et g??n??ralisent les r??sultats de Marchand et al.(2008) tenant sous une hypoth??se de sym??trie.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.