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

Abstract : 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.
Liste complète des métadonnées

Cited literature [165 references]  Display  Hide  Download

https://hal.inria.fr/tel-01092714
Contributor : Christian Baudet <>
Submitted on : Tuesday, December 9, 2014 - 12:20:18 PM
Last modification on : Tuesday, December 9, 2014 - 4:22:29 PM
Document(s) archivé(s) le : Tuesday, March 10, 2015 - 11:30:47 AM

Identifiers

  • HAL Id : tel-01092714, version 1

Citation

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. ⟨tel-01092714⟩

Share

Metrics

Record views

121

Files downloads

210