Enumeração de traces e Identificação de Breakpoints : Estudo de aspectos da evolução. - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2010

Traces enumeration and Breakpoint identification: Study of evolutionary aspects.

Enumération de Traces et Identification de Points de Cassure: Étude des aspects évolutifs

Enumeração de traces e Identificação de Breakpoints : Estudo de aspectos da evolução.

Christian Baudet

Résumé

The study of genome rearrangements helps biologists understand the evolution of species. The species differentiation phenomenon are derived by analyzing mutational events (inversions, transpositions, fissions, fusions, etc) and their effects. In this context, this work aims the study of two different subjects: Traces Enumeration and Breakpoints Identification.Algorithms that solve the problem of sorting oriented permutations through reversals output only one optimal solution, although the set of solutions can be huge. The enumeration of traces of solutions for this problem allows a compact representation of the set of all optimal solutions which sort a permutation. By using this technique, biologists can study many evolutionary scenarios.We carried out a study to improve the efficiency of the enumeration algorithm by adopting a simple data structure. Due to the exponential nature of the problem, large permutations cannot be processed at a satisfactory time. Thus, in order to produce alternative evolutionary scenarios for large permutations, we proposed and evaluated strategies for partial enumeration of traces.Breakpointss are regions that border conserved segments in the chromosomes and reflect the occurrence of evolutionary rearrangements. The techniques for breakpoints identification are meant to identify such points in the chromosome sequences.In this work, we implemented a method proposed in the literature, that performs detection and refinement of breakpointss. The implementation is available as a package to other researchers. Additionally, we introduced a new methodology for breakpoints identification based on the analysis of the hit coverage observed in the alignments of intergenic sequences.
Les algorithmes traditionnels pour le problème de tri de permutations signées par inversions produisent comme sortie une seule solution. Cependant, l'espace des solutions peut être gigantesque et le concept de traces est utilisé pour le représenter d'une manière plus compacte. Dans ce contexte, nous avons étudié des algorithmes pour l'énumération de traces et nous en proposons un qui est plus efficace. Il réduit ainsi la consommation en mémoire et le temps d'exécution du seul algorithme existant par un facteur de 10 et 5, respectivement. Malgré cette amélioration, le temps et l'espace nécessaires pour traiter de grosses permutations sont trop élevés et nous avons donc proposé et évalué trois algorithmes permettant un échantillonnage des solutions optimales.Pour que nous puissions étudier les réarrangements génomiques, il faut que nous soyons capables de bien identifier ses événements dans les génomes. Si nous considérons un pair de génomes, il est possible d'identifier les régions conservées (aussi connues comme "blocs de synténie") à travers de la comparaison des ordres et direction des marqueurs orthologues. Une région localisée entre deux blocs de synténies est appellée point de cassure. Lemaitre et al. ont développé une méthode formel pour la définitions et le raffinement des points de cassure en utilisant information des orthologies de gènes. Nous avons développé le logiciel Cassis qui implémente cette méthodologie. Cassis a été utilisé pour définir les points de cassures des génomes de l'homme et de la souris. Nous avons aligné des séquences intergéniques des deux espèces et nous avons observé que les régions internes aux points de cassure ont des scores d'alignement plus faibles que les régions qui sont externes. En utilisant ces résultats comme base, nous avons proposé une méthodologie pour l'identification des points de cassures qui n'utilise pas les informations d'orthologie. Cette méthodologie a été capable d'identifier 60% des points de cassures trouvés par Cassis.
O estudo de rearranjo de genomas tem o objetivo de auxiliar o entendimento da evolução. Através da análise dos eventos de mutação como inversões, transposições, fissões, fusões, entre outros, buscamos compreender as suas influências sobre o fenômeno da diferenciação das espécies. Dentro deste contexto, esta tese ataca dois temas distintos: a Enumeração de Traces e a Identificação de Breakpoints. Os algoritmos de ordenação de permutações por reversões orientadas produzem uma única solução ótima enquanto o conjunto de soluções é imenso. A enumeração de traces de soluções para este problema oferece um modo mais compacto de representar o conjunto completo de soluções ótimas. Dessa maneira, esta técnica fornece aos biólogos a possibilidade de análise de diversos cenários evolutivos.Neste trabalho, realizamos um estudo para melhora da eficiência do algoritmo de enumeração através da adoção de uma estrutura de dados mais simples. Devido ao caráter exponencial do problema, grandes permutações não podem ser processadas em um tempo satisfatório. Assim, com o objetivo de produzir cenários evolucionários alternativos para grandes permutações, propomos e avaliamos estratégias para a enumeração parcial de traces.Os pontos de quebra (ou breakpoints) são regiões que delimitam os segmentos conservados existentes nos cromossomos e denotam a ocorrência de rearranjos evolutivos. As técnicas de identificação de breakpoints têm a função de identificar tais pontos nas sequências dos cromossomos. Nesta tese, implementamos um método de detecção e refinamento de pontos de quebra proposto na literatura e o disponibilizamos como um pacote que pode ser utilizado por outros pesquisadores. Além disso, introduzimos uma nova metodologia de identificação de breakpoints baseada na análise da cobertura de hits observada nos alinhamentos de sequências intergênicas, provenientes dos genomas das espécies comparadas.
Fichier principal
Vignette du fichier
TeseDoutorado_ChristianBaudet_VersaoFinal.pdf (5.7 Mo) Télécharger le fichier
Loading...

Dates et versions

tel-01092714 , version 1 (09-12-2014)

Identifiants

  • HAL Id : tel-01092714 , version 1

Citer

Christian Baudet. Enumeração de traces e Identificação de Breakpoints : Estudo de aspectos da evolução.. Computer Science [cs]. UNICAMP (Université de Campinas), Brésil, 2010. Portuguese. ⟨NNT : ⟩. ⟨tel-01092714⟩
61 Consultations
183 Téléchargements

Partager

Gmail Facebook X LinkedIn More