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

Résumé : 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.
Type de document :
Thèse
Computer Science [cs]. UNICAMP (Université de Campinas), Brésil, 2010. Portuguese
Liste complète des métadonnées

Littérature citée [165 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01092714
Contributeur : Christian Baudet <>
Soumis le : mardi 9 décembre 2014 - 12:20:18
Dernière modification le : mardi 9 décembre 2014 - 16:22:29
Document(s) archivé(s) le : mardi 10 mars 2015 - 11:30:47

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

174