ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 27/4-5 - 2013  - pp.649-668  - doi:10.3166/ria.27.649-668
TITRE
Application du problème de caractérisation multiple à la conception de tests de diagnostic pour la biologie végétale

TITLE
Application of the multiple characterization problem to design diagnostic test for plant biology

RÉSUMÉ
Nous présentons un problème de caractérisation issu de la biologie végétale. Ce problème de caractérisation multiple consiste à traiter simultanément plusieurs groupes d’entités (représentées par des interprétations booléennes) et à trouver une caractérisation pour chacun d’eux sous forme de formules booléennes. Cette caractérisation doit être exacte et une des difficultés majeures est de trouver une caractérisation minimale. Une étude de complexité de ce problème est réalisée et nous arrivons à la conclusion que le problème est W[2]-Complet. Nous proposons une reformulation du problème en programmation linéaire ainsi que différentes approches de résolutions. Une étude expérimentale est réalisée sur des instances aléatoires ainsi que des instances réelles.


ABSTRACT
In this paper, we address a characterization problem coming from plant biology. The multiple characterization problem consists of entities (represented by a Boolean assignment) belonging to several groups to find a characterization for each group using propositional logic. It implies that this characterization must be exact and the main difficulty is to compute the minimal one. We show that this problem is W[2]-Complete. We also propose a reformulation to a linear program and describe different approaches for the resolution. We experiment on random and real instances whose solutions are used to design a patent-protected diagnostic test.


AUTEUR(S)
Fabien CHHEL, Frédéric LARDEUX, Frédéric SAUBION, Bruno ZANUTTINI

MOTS-CLÉS
caractérisation booléenne multiple, minimisation de formule, W[2]-difficile, test de diagnostic.

KEYWORDS
Boolean multiple characterisation, formula minimization, W[2]-difficile, diagnostic test.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (266 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier