Dans le domaine de la biologie végétale, l'acquisition des données n'est plus forcément un problème majeur mais leur traitement et leur utilisation soulèvent toujours des difficultés. Nous nous intéressons plus particulièrement ici à la caractérisation des souches de bactéries phytopathogènes constitue un enjeu important dans l'étude des pathologie végétales. De plus, les dégâts générés par ces bactéries sur les cultures ou leurs dangerosités (certaines sont recensées sur des listes d'organismes de quarantaine voire même sur des listes de bio-terrorisme) nécessite le développement rapide de tests de diagnostic permettant de déceler de telles menaces. A l'aide de données fournies par les biologistes indiquant la présence ou l'absence de gènes dans des souches bactériennes, nous proposons une modélisation du problème comme la recherche de formules en logique propositionnelle. Nous prouvons ensuite que ce problème appartient à la classe de complexité Sigma^p_2-complet. Enfin, nous proposons une méthode algorithmique permettant d'obtenir les plus petites caractérisations possibles. Cette méthode nous a permis de caractériser certaines souches et des tests de diagnostic ont pu être ainsi produits et utilisés.