L’informatique joue un rôle de plus en plus prépondérant dans l’analyse et la compréhension des données biologiques. Dans cette thèse, nous présentons le problème de caractérisation multiple qui aborde, sous l’angle de l’optimisation combinatoire, la détection de souches bactériennes phytopathogènes. En effet, certaines bactéries sont responsables de pathologies sur une large gamme de cultures diminuant ainsi la valeur marchande des semences. Des tests de diagnostic peuvent être alors conçus et nécessitent l’identification de caractères observables discriminants. Nous avons développé plusieurs méthodes de résolution exactes (branch and bound et programmation linéaire) et approchées (métaheuristiques) afin de minimiser le nombre de caractères à traiter. Précisément, en considérant un sous-ensembles d’individus représentatifs de différents groupes, il s’agit d’établir pour chacun de ces groupes une caractérisation (sous forme de formule propositionnelle) permettant de distinguer les individus du groupe par rapport à ceux des autres groupes. Nous utilisons le terme (caractérisation multiple) pour rendre compte de l’aspect mutuel de ces discriminations au sens (un groupe versus le reste des groupes) et ce pour chaque groupe. Nos travaux ont été validés expérimentalement sur des jeux de données et une étude approfondie de la complexité de ce problème a été menée. / Computer science plays an increasingly important role in the analysis and understanding of biological data. In this thesis, we present the multiple characterization problem that addresses, as a combinatorial optimization problem, the detection of plant pathogenic bacterial strains. Indeed, some bacteria are responsible for diseases on a wide range of crops and decrease the market value of the seeds. Diagnostic tests can be designed and require the identification of discriminant observable characters. We have developed several exact methods (branch and bound, linear programming) and approximate (metaheuristics) to minimize the number of characters to deal with. Specifically, considering a subset of individuals representing different groups, the aim for each group is to find a characterization (as a propositional formula) to distinguish the individuals of the group compared to those of the other groups. We use the term “multiple characterization” to highlight the mutual aspect of theses discriminations in the sense “versus a group the other groups” and that for each group. Our work has been validated experimentally on data sets and an in-depth study of the problem’s complexity has been conducted.
| Identifer | oai:union.ndltd.org:theses.fr/2014ANGE0018 |
| Date | 01 October 2014 |
| Creators | Chhel, Fabien-Sothéa |
| Contributors | Angers, Saubion, Frédéric, Lardeux, Frédéric |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0016 seconds