Application du problème de caractérisation multiple à la conception de tests de diagnostic pour la biologie végétale

Overview & Synopsis

Dans cet article, 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. Les résultats obtenus sur ces dernières ont pu être valorisés par le dépôt d'un brevet et la validation au niveau européen d'un test de dépistage basé sur les caractérisations trouvées.