Partitionnement maximalement prédictif sous contrainte d'ordre total.
Applications aux séquences génétiques

L. Guéguen

LIP6 2000/004: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
175 pages - Janvier/January 2000 - French document.

Get it : 670 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Partitionnement maximalement prédictif sous contrainte d'ordre total.
Applications aux séquences génétiques
Titre anglais : Maximal predictive partitionning with total order constraint.
Applications on genetic sequences

Résumé : 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.

Abstract : Maximal predictive partitionning with total order constraint is a classification method that seeks to part sequences of qualitative objects into homogeneous segments. The homogeneity is defined according to criteria that follow the notion of prediction. Given a specific problem, a finite set of predictors is introduced and for each predictor the prediction is an evaluation function on the objects of the sequence. The homogeneity of a segment is evaluated by the sum of the predictions on its elements by a same optimal predictor. The evaluation of a partition is the sum of the predictions of its segments. The aims of this approach is to get a `` good `` summary of the sequence, owing to the predictors of the segments of a `` good `` partition, and to reveal a possible structure of that sequence. The relevant number of segments in a good partition is also to be found out.
We introduce an algorithm that builds up the optimal predictive partitions in i classes of a given sequence, given a specified set of predictors, for all i between 1 and a given number. In the result of such a calculus, which is called a partitionning, we can analyse the successive sets of partitions according to their number of segments, and some estimation criteria of the `` good `` number of segments are given.
That algorithm has a time-complexity linear with the length of the sequence, the size of the set of predictors, and with the maximal number of segments. Hence, partitionning can be made on very big sequences, such as biological ones. We present some applications of maximal predictive partitionning on genetic sequences.

Mots-clés : classification, prédiction, partition, séquences, génomes

Key-words : classification, prediction, partition, sequences, genomes

Publications internes LIP6 2000 / LIP6 research reports 2000

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr