This thesis focuses on algorithms related to ancestral genome reconstruction and phylogenetics analyses. Specially, it studies insertion and deletion (indel) in genomic sequences, their utilities for (1) evolutionary studies of species families, (2) multiple alignment and phylogenetic trees reconstruction assessment, and (3) functional DNA sequence annotation. Here, the indel scenarios reconstruction problem is presented, in a likelihood framework, and it can be stated as follows: given a multiple alignment of orthologous sequences and a phylogenetic tree for these sequences, reconstruct the most likely scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, that we called the Indel Maximum Likelihood Problem (IMLP), is an important step toward the reconstruction of ancestral genomic sequences, and is important for studying evolutionary processes, genome function, adaptation and convergence. In this thesis, first, we showed that we can solve the IMLP using a new type of tree hidden Markov model whose states correspond to single-base evolutionary scenarios and where transitions model dependencies between neighboring columns. The standard Viterbi and Forward-backward algorithms are optimized to produce the most likely ancestral reconstruction and to compute the level of confidence associated to specific regions of the reconstruction. A heuristic is presented to make the method practical for large data sets, while retaining an extremely high degree of accuracy. The developed methods have been made available for the community through a web interface. Second we showed the utilities of the defined indel score for assessing the accuracy of multiple sequence alignment and phylogenetic tree reconstruction. Third, the provided method is included into the framework of the ancestral protein reconstruction of phages under a reticulate evolution and the evolutionary studies of the carcinogencity of the Human Papilloma Vir / Cette thèse traite d'algorithmes pour la reconstruction de génomes ancestraux et l'analyse phylogénétique. Elle étudie particulièrement les scénarios d'insertion et délétion (indels) dans les séquences génomiques, leur utilité (1) pour l'étude des familles d'espèces, (2) pour l'évaluation des alignements multiples de séquences et la reconstruction phylogénétique, (3) et pour l'annotation de séquences génomiques fonctionnelles. Dans cette thèse, le problème de la reconstruction du scénario d'indels est étudié en utilisant le critère de maximum de vraisemblance. Ce problème peut être défini de la manière suivante: étant donné un alignement multiple de séquences orthologues et un arbre phylogénétique traduisant l'histoire évolutive de ces séquences, reconstruire le scénario d'indels le plus vraisemblable capable d'expliquer les brèches présentes dans l'alignement. Ce problème, dénommé ''Indel Maximum Likelihood Problem (IMLP)'', est une importante étape de la reconstruction de séquences ancestrales. Il est également important pour l'étude des processus évolutifs, des fonctions des gènes, de l'adaptation et de la convergence.Dans une première étape de cette thèse, nous montrons que l'IMLP peut être résolu en utilisant un nouveau type de données combinant un arbre phylogénétique et un modèle de Markov caché. Les états de ce modèle de Markov caché correspondent à un scénario évolutif d'une colonne de l'alignement. Ses transitions modélisent la dépendance entre les colonnes voisines de l'alignement.Les algorithmes standard de Viterbi et de Forward-Backward ont été optimisés pour produire le scénario ancestral le plus vraisemblable et pour calculer le niveau de confiance associé aux prédictions. Dans cette thèse, Nous présentons également une heuristique qui permet d'adapter la méthode à des données de grandes tailles. En second, nous montrons l'utilité du score d'indel dans l'évaluatio
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.40771 |
| Date | January 2009 |
| Creators | Diallo, Abdoulaye |
| Contributors | Mathieu Blanchette (Internal/Supervisor), Vladimir Makarenkov (Internal/Cosupervisor2) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0023 seconds