• Accueil LIP6
  • Page : 'rapport_recherche' inconnue (menus.php)

LIP6 2000/004

  • Thèse
    Partitionnement maximalement prédictif sous contrainte d'ordre total.
    Applications aux séquences génétiques
  • L. Guéguen
  • 175 pages - 18/01/2000- document en - http://www.lip6.fr/lip6/reports/2000/lip6.2000.004.ps.gz - 686 Ko
  • Contact : gueguen (at) nullccr.jussieu.fr
  • Ancien Thème : SYSDEF
  • Le partitionnement maximalement prédictif sous contrainte d'ordre total est une méthode de classification qui cherche à partager des séquences d'objets qualitatifs en segments homogènes. L'homogénéité est définie selon un critère basé sur la notion de prédiction. Pour un problème donné, on se munit d'un ensemble fini de prédicteurs possibles. À chaque prédicteur, on associe une fonction -- la prédiction -- à valeurs réelles sur les objets de la séquence. Un segment est évalué par la somme des prédictions de tous ses éléments par un même prédicteur ad hoc. L'évaluation est ainsi un critère d'homogénéité. Une partition de la séquence est évaluée par la somme des prédictions sur ses segments. Sur la base de cette évaluation on veut pouvoir, grâce au prédicteur de chaque segment d'une partition, disposer d'un résumé de la séquence qui mette en relief une éventuelle structure de cette séquence. Il faut alors estimer le nombre de segments en lequel il est le plus judicieux d'opérer cette partition.
    Nous présentons un algorithme qui, sur la donnée d'une séquence, d'un ensemble de prédicteurs et d'un entier k, construit l'ensemble des partitions optimales en i segments de la séquence pour tout i entre 1 et k. C'est ce que nous appelons un partitionnement. Ceci permet aussi d'observer l'évolution des partitions en fonction de leurs nombres de classes. De ces observations, on propose des critères d'estimation du << bon >> nombre de segments pour partager cette séquence.
    L'algorithme présenté a une complexité en temps linéaire avec la longueur de la séquence, la taille de l'ensemble des prédicteurs et le nombre maximum de segments. On peut alors opérer le partitionnement sur de très grandes séquences, et les séquences biologiques en constituent un domaine naturel d'expérimentation. Nous présentons ainsi quelques applications du partitionnement maximalement prédictif sur des séquences génétiques.
  • Mots clés : classification, prédiction, partition, séquences, génomes
  • Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
Mentions légales
Carte du site