Show item record

dc.contributor.advisorEl-Mabrouk, Nadia
dc.contributor.advisorCsuros, Miklos
dc.contributor.authorBenzaid, Billel
dc.date.accessioned2017-05-08T18:58:14Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2017-05-08T18:58:14Z
dc.date.issued2017-03-28
dc.date.submitted2016-10
dc.identifier.urihttp://hdl.handle.net/1866/18470
dc.subjectAlgorithmefr
dc.subjectAlignementfr
dc.subjectOrdres de gènesfr
dc.subjectProgrammation dynamiquefr
dc.subjectComplexitéfr
dc.subjectDuplicationfr
dc.subjectPertefr
dc.subjectRéarrangements génomiquesfr
dc.subjectAlgorithmfr
dc.subjectAlignmentfr
dc.subjectGene ordersfr
dc.subjectDynamic programmingfr
dc.subjectComplexityfr
dc.subjectLossfr
dc.subjectGenomic rearrangementsfr
dc.subject.otherApplied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)fr
dc.titleÉvolution des génomes par mutations locales et globales : une approche d’alignementfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelDoctorat / Doctoralfr
etd.degree.namePh. D.fr
dcterms.abstractDurant leur évolution, les génomes accumulent des mutations pouvant affecter d’un nucléotide à plusieurs gènes. Les modifications au niveau du nombre et de l’organisation des gènes dans les génomes sont dues à des mutations globales, telles que les duplications, les pertes et les réarrangements. En comparant les ordres de gènes des génomes, il est possible d’inférer les événements évolutifs les plus fréquents, le contenu en gènes des espèces ancestrales ainsi que les histoires évolutives ayant menées aux ordres observés. Dans cette thèse, nous nous intéressons au développement de nouvelles méthodes algorithmiques, par approche d’alignement, afin d’analyser ces différents aspects de l’évolution des génomes. Nous nous intéressons à la comparaison de deux ou d’un ensemble de génomes reliés par une phylogénie, en tenant compte des mutations globales. Pour commencer, nous étudions la complexité théorique de plusieurs variantes du problème de l’alignement de deux ordres de gènes par duplications et pertes, ainsi que de l’approximabilité de ces problèmes. Nous rappelons ensuite les algorithmes exacts, en temps exponentiel, existants, et développons des heuristiques efficaces. Nous proposons, dans un premier temps, DLAlign, une heuristique quadratique pour le problème d’alignement de deux ordres de gènes par duplications et pertes. Ensuite, nous présentons, OrthoAlign, une extension de DLAlign, qui considère, en plus des duplications et pertes, les réarrangements et les substitutions. Nous abordons également le problème de l’alignement phylogénétique de génomes. Pour commencer, l’heuristique OrthoAlign est adaptée afin de permettre l’inférence de génomes ancestraux au noeuds internes d’un arbre phylogénétique. Nous proposons enfin, MultiOrthoAlign, une heuristique plus robuste, basée sur la médiane, pour l’inférence de génomes ancestraux et d’histoires évolutives d’un ensemble de génomes représentés aux feuilles d’un arbre phylogénétique.fr
dcterms.abstractDuring the evolution process, genomes accumulate mutations that may affect the genome at different levels, ranging from one base to the overall gene content. Global mutations affecting gene content and organization are mainly duplications, losses and rearrangements. By comparing gene orders, it is possible to infer the most frequent events, the gene content in the ancestral genomes and the evolutionary histories of the observed gene orders. In this thesis, we are interested in developing new algorithmic methods based on an alignment approach for comparing two or a set of genomes represented as gene orders and related through a phylogenetic tree, based on global mutations. We study the theoretical complexity and the approximability of different variants of the two gene orders alignment problem by duplications and losses. Then, we present the existing exact exponential time algorithms, and develop efficient heuristics for these problems. First, we developed DLAlign, a quadratic time heuristic for the two gene orders alignment problem by duplications and losses. Then, we developed OrthoAlign, a generalization of DLAlign, accounting for most genome-wide evolutionary events such as duplications, losses, rearrangements and substitutions. We also study the phylogenetic alignment problem. First, we adapt our heuristic OrthoAlign in order to infer ancestral genomes at the internal nodes of a given phylogenetic tree. Finally, we developed MultiOrthoAlign, a more robust heuristic, based on the median problem, for the inference of ancestral genomes and evolutionary histories of extent genomes labeling leaves of a phylogenetic tree.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record