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.

La quantité d'informations sur Internet aujourd'hui accable la plupart des utilisateurs. La découverte d'informations pertinentes (p. Ex. Des nouvelles à lire ou des vidéos à regarder) prend du temps et est fastidieuse; pourtant, elle fait partie du travail quotidien d'au moins 80% des employés en Amérique du Nord. Plusieurs systèmes de filtrage d'informations pour le Web peuvent faciliter cette tâche pour les utilisateurs. Les exemples se retrouvent dans des familles telles que les réseaux sociaux, les systèmes de notation sociale et les systèmes de bookmarking social. Tous ces systèmes exigent que l'engagement de l'utilisateur fonctionne (par exemple, la soumission ou l'évaluation du contenu). Ils fonctionnent bien dans une communauté Internet, mais souffrent dans le cas des petites communautés. En effet, dans les petites communautés, l'apport des utilisateurs est plus rare. Nous nous concentrons sur les communautés d'un endroit qui sont des communautés qui regroupent les gens qui vivent, travaillent ou étudient dans la même région. Exemples de communautés d'un lieu: (i) les étudiants d'un campus, (ii) les personnes vivant dans un quartier ou (iii) les chercheurs travaillant sur le même site. Anecdote nous savons que seulement 0,3% des travailleurs contribuent quotidiennement à leur réseau social d'entreprise. Cette information montre qu'il ya un manque d'engagement des utilisateurs dans les communautés d'un endroit.Dans cette thèse, nous tirons parti de l'observation passive des communautés d'un endroit pour réduire les frais généraux pour les utilisateurs de participer à des systèmes de filtrage de l'information. Nous obtenons une nouvelle source riche d'informations que nous utilisons pour (i) concevoir WeBrowse, un outil de restauration de contenu pour les communautésLa quantité d'informations sur Internet aujourd'hui accable la plupart des utilisateurs. La découverte d'informations pertinentes (p. Ex. Des nouvelles à lire ou des vidéos à regarder) prend du temps et est fastidieuse; pourtant, elle fait partie du travail quotidien d'au moins 80% des employés en Amérique du Nord. Plusieurs systèmes de filtrage d'informations pour le Web peuvent faciliter cette tâche pour les utilisateurs. Les exemples se retrouvent dans des familles telles que les réseaux sociaux, les systèmes de notation sociale et les systèmes de bookmarking social. Tous ces systèmes exigent que l'engagement de l'utilisateur fonctionne (par exemple, la soumission ou l'évaluation du contenu). Ils fonctionnent bien dans une communauté Internet, mais souffrent dans le cas des petites communautés. En effet, dans les petites communautés, l'apport des utilisateurs est plus rare. Nous nous concentrons sur les communautés d'un endroit qui sont des communautés qui regroupent les gens qui vivent, travaillent ou étudient dans la même région. Exemples de communautés d'un lieu: (i) les étudiants d'un campus, (ii) les personnes vivant dans un quartier ou (iii) les chercheurs travaillant sur le même site. Anecdote nous savons que seulement 0,3% des travailleurs contribuent quotidiennement à leur réseau social d'entreprise. Cette information montre qu'il ya un manque d'engagement des utilisateurs dans les communautés d'un endroit. / The amount of information on the Internet today overwhelms most users. Discovering relevant information (e.g. news to read or videos to watch) is time-consuming and tedious and yet it is part of the daily job of at least 80% of the employees in North America. Several information filtering systems for the web can ease this task for users. Examples fall into families such as Social Networks, Social Rating Systems and Social Bookmarking Systems. All these systems require user engagement to work (e.g. submission or rating of content). They work well in an Internet-wide community but suffer in the case smaller communities. Indeed, in smaller communities, the users' input is more scarce. We focus on communities of a place that are communities that group people who live, work or study in the same area. Examples of communities of a place are: (i) the students of a campus, (ii) the people living in a neighborhood or (iii) researchers working in the same site. Anecdotally we know that only 0.3% of workers contribute daily to their corporate social network. This information shows that there is a lack of user engagement in communities of a place.