Biclustering des données de biopuces par les arbres pondérés de plus long préfixe. Modélisation discrète des données de puces à ADN
Les arbres pondérés de plus long préfixe (WLPTs) sont introduits pour modéliser et analyser les données de puces à ADN. Ils permettent d'examiner le problème de bicluster pour l'appliquer à la fouille de données. Nous fournissons un algorithme de permutations successives pour réduire le nombre de noeuds dans les WLPTs afin de compresser les données. Ces algorithmes permettent également de trouver des biclusters maximaux (globaux et locaux). Expérimentalement, nous montrons que le problème de biclustering est effectué en temps linéaire par les WLPTs. Un autre avantage des WLPTs est qu'ils permettent de reconstruire des diagrammes de Hasse associés à un treillis de Galois et d'en extraire les concepts formels dans le contexte de la fouille de données.
Weighted longest prefix trees (WLPTs) are introduced for modelling and analyzing DNA microarray data. They enable to examine the problem of biclustering to apply for the data mining step in the process of knowledge discovery in databases (KDD).We give an algorithm of successive permutations to reduce number of nodes in the WLPTs in order to compress the data. These algorithms enable also to find maximal (global and local) biclusters. Experimentally, we show that the problem of biclustering is carried out in linear time by use of the WLPTs. Another advantage of the WLPTs is that they enable to deduce the Hasse diagram associated to a Galois lattices and to extract its formal concepts in the context of data mining.
T.TRAN, C.NGUYEN, N.HOANG
Reçu le 5 octobre 2005.
Accepté le 15 juin 2006.
modélisation discrète, combinatoire des mots, arbres pondérés, fouille de données, classification, biclustering, treillis de Galois, puces à ADN.
discrete modeling, combinatorics on words, weighted trees, data mining, clustering, biclustering, Galois lattice, DNA microarray.
Français
|
