Caractérisation spécifique minimale (version 1.05)

Caractérisation spécifique minimale (version 1.05)

gilles.hunault "at" univ-angers.fr

Table des matières cliquable

  1. Qu'est-ce que la caractérisation spécifique minimale ?

  2. Formats des données

  3. Scripts associés

1. Qu'est-ce que la caractérisation spécifique minimale ?

Caractériser des groupes d'individus (écrits en lignes) à partir de leurs valeurs (données fournies en colonnes), c'est trouver une «définition» des groupes qui s'exprime à l'aide des colonnes. Prenons un exemple fictif : on veut caractériser deux groupes, celui des hommes et des femmes, à partir de leurs habitudes alimentaires du petit déjeuner. Une certaine expertise aboutit aux données suivantes, considérées comme exactes et spécifiques :

   Groupes    Colonnes    Lignes (format : Num Nom Grp Colonnes)

1 Hommes 2 Femmes 1 Café 2 Thé 3 Sucre 4 Confiture 5 Cannelle 1 Adam 1 1 0 1 0 0 2 Eve 2 0 1 1 1 0 3 Lilith 2 0 1 1 1 1

Ces données montrent par exemple qu'Adam, qui fait partie du groupe des hommes (groupe numéro 1), est en fait le seul individu de ce groupe. Il a répondu 1 0 1 0 0 aux questions, ce qu'il signifie qu'il prend du café au petit déjeuner, pas de thé, etc. Après examen des données, on se rend compte que les femmes prennent du thé et pas de café (ou plus exactement qu'elles prennent TOUTES du thé et JAMAIS de café). On pourrait donc définir les hommes comme les individus qui prennent du café et les femmes comme les individus qui n'en prennent pas. En termes de définition : le groupe numéro 1, celui des hommes, est défini par la valeur 1 pour la colonne 1 (soit encore CAFE=1) et le groupe 2, celui des femmes, par CAFE=0 ou, avec des notations plus générales, G1<==>C1=1 et G2<==>C1=0 (<==> peut se lire «équivaut à»). Il est clair qu'ici on n'a pas eu besoin des 5 colonnes de données et qu'avec une seule colonne (CAFÉ ou C1) on a réussi à caractériser tous nos groupes.

Cette caractérisation est spécifique dans la mesure où tous les hommes vérifient C1=1 et aucun autre personne ne vérifie cette condition.Elle est minimale puisqu'elle met en jeu une seule colonne.

Le but de la caractérisation spécifique minimale (CSM) est justement de trouver un nombre minimal de colonnes qui permettent de définir très exactement tous les individus de chaque groupe et seulement ceux-là. Notre exemple montre qu'il n'y a pas forcément unicité de la solution : comme C2 (THÉ) est la négation logique de CAFÉ pour nos données, on aurait pu prendre comme CSM : G1<==>C2=0 et G2<==>C2=1.

1.1 Existence de la ou des solutions

Pour des problèmes réels, il n'est pas en général aussi simple et facile de trouver une solution. Avec un peu de réflexion, il est possible de constater que chaque groupe peut être défini «en extension» en utilisant toutes les colonnes. Ainsi le groupe 2 de notre exemple précédent peut être défini comme C1=0 et C2=1... et ... C5=0 (valeurs de la ligne 2, EVE) ou comme C1=0 et C2=1... et ... C5=1 (valeurs de la ligne 3, LILITH). Est-ce dans le cas général une CSM ? Sans doute que non, sauf cas exceptionnel. Pire : si deux lignes ont les mêmes valeurs pour toutes les colonnes, alors les individus correspondant sont indiscernables ; s'ils n'appartiennent pas au même groupe, alors notre problème n'a pas de solution : on dit qu'il y a contradiction [logique] dans les données.

Il est possible (et assez facile) de démontrer que s'il n'y a pas de contradiction logique (CL) dans les données, alors il y a au moins une caractérisation, à savoir : le groupe numéro i est défini par les valeurs de son premier indidvidu ou de son deuxième ou de son troisième etc. Le seul hic c'est que c'est une CS, pas une CSM, c'est-à-dire qu'il n'y a pas minimalité de la solution... Il est possible aussi de démontrer, mais là c'est franchement plus dur, que le problème qui consiste à trouver une CSM avec des données sans CL est ∑₂^p-complet.

1.2 Intérêt des caractérisations spécifiques minimales

Il existe un certain nombre de domaine d'expertise qui auraient besoin de caractérisation spécifique minimale (CSM) en tant qu'outils d'aide à la décision. Par exemple tout ce qui touche à l'identification ou le diagnostic de pathologies ou d'agents pathogènes : la partie CS de CSM garantit la qualité des résultats, le M de CSM fournit la faisabilité. Ainsi, pour des données issues de séquençage mettant en jeu plusieurs centaines de gènes, trouver une CSM avec une dizaine de gènes pertinents ouvre la voie à la réalisation d'un test de détection par PCR multiplex ou d'une puce à ADN...

1.3 Liens avec d'autres approches statistiques ou informatiques

Essayer de caractériser des groupes de lignes via leurs colonnes de données n'est pas un problème original. Statistiquement, un tel problème s'apparente à de la régression logistique, du classement (de la «classification supervisée»), de l'analyse discriminante ou de l'identification probabiliste. Informatiquement, on parlera plutôt d'apprentissage ou de modélisation (au sens du Data Mining). Il y a toutefois une différence importante avec notre problème de CSM : quand ces deux disciplines cherchent un modèle, des formules mathématiques ou logiques, des règles d'affectation... elles utilisent tout ou partie des données en vue de trouver un résultat sans garantie d'efficacité maximale. Nous, nous cherchons nous un modèle qui classe 100 % des individus de départ exactement dans leur groupe d'origine, de plus avec un minimum de données, c'est-à-dire sans sur ajustement ou sur apprentissage, comme ils disent. Et là, cela devient un problème nouveau et difficile. Cela signifie aussi que les données utilisées doivent être des données expertes, exactes, considérées comme spécifiques du domaine, suffisamment nombreuses pour qu'il n'y ait pas de contradiction logique, ce qui est bien sûr le cas avec des données de bioinformatique après curation (car les banques de données regorgent d'informations putatives ou non validées) ou avec des données médicales de cohortes...
2. Formats des données
Historiquement, les données fournies étaient des fichiers Excel et le premier solveur (le programme qui cherche les CSM), lui, ne lisait que les fichiers textes sans caractère de controle. Il fallait donc convertir les données. Aujourd'hui, nous avons mis au point un format XML et des pages Web pour construire ce fichier XML à partir de diverses sources.

2.1 Format texte pour le premier solveur

Le premier solveur, prévu pour tester des données binaires quelconques, ne se préoccupe ni des noms de colonnes ni des noms de groupes. Il utilise des données avec le format standard présenté ci-dessus : chaque ligne comporte un identifiant, un numéro de groupe puis les données binaires de l'individu. L'identifiant correspond à un seul mot (on peut utiliser le symbole _ comme séparateur) qui doit êter unique pour le fichier ; c'est bien sûr le cas si on utilise des numéros CFBP de souches ou des numéros d'accession NCBI. Afin de garantir une relecture aisée des solutions, il faut en général fournir un fichier dit «galerie» (ou fichier .GAL) qui donne la correspondance entre numéro de colonne et nom de colonne. De même, le fichier «des groupes» (ou fichier .NGR) donne la correspondance entre numéro de groupe et nom de groupe. Le fichier des données binaires, lui, est nommé fichier .DAC et c'est le seul fichier requis par le solveur. En cas de succès, le solveur fournit les solutions sous forme d'un fichier .CS qui contient des informations de suivi puis les caractérisations.

Vous pouvez cliquer sur les liens ci-dessous pour voir les fichiers texte correspondant aux données PARADIS :

paradis.ngr fichier des groupes ; format : numéro_de_groupe nom_de_groupe

paradis.gal fichier des colonnes ; format : numéro_de_colonne nom_de_colonne

paradis.dac fichier des données binaires avec indication de groupe ; format : identifiant numéro_de_groupe valeurs binaires

paradis.cs fichier des résultats du solveur

Quelques explications sur le format du fichier des résultats fournis par le solveur : la chaine #Instance: doit être présente dans le fichier. Ensuite, on doit trouver, à raison d'une ligne par groupe, une solution pour chaque groupe ou la formule (0) lorsque le groupe n'est pas trouvé. Chaque solution se présente sous la forme numéro_de_groupe f= formule_CNF. Voici un exemple :
     #Instance:
     1 f=(1)&(2)&(~3)
     2 f=(4)&(~5)&(~6)
     3	f=(~1)&(2)
     4	f=(~2)&(~9)
     5	f=(3)&(6)
     6	f=(1)&(4)
     7	f=(7)&(~11)
     8	f=(0)
     9	f=(~1)&(~4)&(~6)
     10	f=(1)&(~5)&(6)
     11	f=(4)&(6)&(~12)
     12	f=(~5)&(12)
     13	f=(1)&(~2)&(~6)
     14	f=(2)&(~7)
     
2.2 Format XML et DOCTYPE (grammaire) pour le second solveur

Il est facile de copier ou de transférer le fichier des données binaires .DAC et d'oublier de transférer le fichiers des colonnes .GAL et le fichier des groupes .NGR. De plus, la vérification des données doit se faire à la main ou par un programme spécialisé. Pour toutes ces raisons, et pour une meilleure portabilité, il est plus rationnel de tout intégrer dans un format XML. L'écriture de la grammaire du format (ici un schéma XSD issu d'un schéma Relax NG) permet l'utilisation d'outils généraux pour vérifier les données, les convertir, les extraire...

Vous pouvez cliquer sur les liens ci-dessous pour voir la grammaire et le fichier texte correspondant aux données PARADIS :

cs.xsd fichier-grammaire qui définit la structure des fichiers XML ;

paradis.xml exemple de fichier XML des groupes, colonnes et des données binaires avec indication de groupe ;

instance.xsd fichier-grammaire qui définit la structure (v2) des fichiers XML en entrée ;

resultat.xsd fichier-grammaire qui définit la structure des fichiers XML en sortie.
3. Scripts associés

Il est nécessaire de tout vérifier. D'où des scripts de vérification des fichiers texte, des fichiers XML. De même, les données venant de plusieurs sources et devant être intégrés dans des documents divers ou utilisés par de nombreux programmes et pages Web, il faut là encore importer, exporter, convertir...

3.1 Vérifications, réduction et résolution

Le script anared[.rex] vient analyser le fichier .DAC des données binaires avec indication de groupe et recherche les lignes et les colonnes semblables de façon à réduire le fichier des données binaires à traiter. Le script cs[.rex] vient essayer de une solution par groupe. Il se lance sur le fichier .DAC ; en cas de solution, on peut rediriger la sortie dans un fichier .CS et utiliser le script decodecs[.php] pour gérer les fichiers de données binaires correspondant à la solution minimale. En cas d'impossibilité («contradiction»), il faut utiliser le script contra[.rex]. Le script cs fait référence au premier solveur de F. Chhel. On peut aussi utiliser le script cs2[.rex] qui fait référence au second solveur de F. Chhel.

3.2 Conversions

Les scripts dac2xml[.rex] et xml2dac[.rex] convertissent les fichiers-textes en XML et réciproquement.

3.3 Mises en forme

Le script cc_cli[.php] génére une analyse statistique élémentaire des données binaires par groupe. En cas de contradiction logique, le script contra[.rex] met en forme les contradictions et génère un fichier .CTD.

3.4 Tracés d'arbres

Le tracé d'arbre est intégré directement aux pages Web de sortie.

Retour à la page principale de (gH)