La métagénomique vise à étudier le contenu génétique et génomique d'un échantillon provenant d'un environnement naturel. Cette discipline récente s'attache à étudier les génomes de différents organismes provenant d'un même milieu. La métagénomique pose de nouvelles questions, tant d'un point de vue biologique qu'informatique. Les masses de données générées par les études métagénomiques et la complexité des milieux étudiés, nécessitent de développer de nouvelles structures de données et de nouveaux algorithmes dédiés. Parmi les différentes approches existantes en métagénomique, la métagénomique comparative consiste à comparer plusieurs métagénomes afin d'en connaître les divers degrés de similarité. Lorsque cette comparaison se base uniquement sur le contenu brut des échantillons, sans faire appel à des connaissances externes, on parle de métagénomique comparative de novo. L'objectif des travaux que nous proposons est de développer une méthode permettant d'extraire les séquences similaires de deux jeux de données métagénomiques, où chaque jeu peut être composé de centaines de millions de courtes séquences. La comparaison proposée consiste à identifier les séquences d'un premier jeu similaires à au moins une séquence d'un second jeu. Afin d'être rapide et économe en mémoire, l'implémentation de notre méthode a nécessité la conception d'une nouvelle structure d'indexation, basée sur le filtre de bloom. Le logiciel final, nommé Compareads, a une consommation mémoire faible (de l'ordre de quelques go) et peut calculer l'intersection de deux échantillons de 100 millions de séquences chacun en une dizaine d'heures. Notre méthode est une heuristique qui génère un faible taux de faux positifs. Le logiciel Compareads est dédié à l'analyse de grands jeux de données métagénomiques. À l'heure actuelle, il est le seul outil capable de comparer de tels jeux. Compareads a été appliqué sur plusieurs projets métagénomiques. Notre outil produit des résultats robustes, biologiquement exploitables et en accord avec diverses méthodes fondamentalement différentes. Il est actuellement utilisé de manière intensive sur les échantillons provenant de l'expédition tara oceans. Sur ce projet, notre méthode à permis de mettre en évidence que les grands systèmes océaniques influent sur la répartition globale des micro-organismes marins. / Metagenomics studies overall genomic information of multiple organisms coming from the same biotope. The information is generally provided by next generation sequencing technologies (NGS). Typical data are samples of short reads (i.e. reads of few hundred base pairs). To study such metagenomics information, we developed an original method for extracting similarities between two samples of reads. More precisely, this approach locates the set of common reads present in two samples. In order to fit with current memory capacities and to be time efficient, we used a modified Bloom filter data structure. Finding the common reads between multiple samples and crossing this information with the location of samples leads to visualize some biological processes like ubiquitous species or effect of water stream caring some species. Finally, the tool can also be used as a filter on metagenomics datas to remove for example only one specie. Our software, Compareads, is actually used on the Tara Oceans project where it shows that global dynamic of oceans seems to play a part on the dispersion of marine microorganisms.

Dans cette thèse, nous proposons des méthodes a faible complexité pour la classification en présence d'un très grand nombre de catégories. Ces methodes permettent d'accelerer la prediction des classifieurs afin des les rendre utilisables dans les applications courantes. Nous proposons deux methodes destinées respectivement a la classification monolabel et a la classification multilabel. La première méthode utilise l'information hierarchique existante entre les catégories afin de créer un représentation binaire compact de celles-ci. La seconde approche , destinée aux problemes multilabel adpate le framework des Filtres de Bloom a la representation de sous ensembles de labels sous forme de de vecteurs binaires sparses. Dans chacun des cas, des classifieurs binaires sont appris afin de prédire les representations des catégories/labels et un algorithme permettant de retrouver l'ensemble de catégories pertinentes a partir de la représentation prédite est proposée. Les méthodes proposées sont validées par des expérience sur des données de grandes échelles et donnent des performances supérieures aux méthodes classiquement utilisées pour la classification extreme. / We propose in this thesis new methods to tackle classification problems with a large number of labes also called extreme classification. The proposed approaches aim at reducing the inference conplexity in comparison with the classical methods such as one-versus-rest in order to make learning machines usable in a real life scenario. We propose two types of methods respectively for single label and multilable classification. The first proposed approach uses existing hierarchical information among the categories in order to learn low dimensional binary representation of the categories. The second type of approaches, dedicated to multilabel problems, adapts the framework of Bloom Filters to represent subsets of labels with sparse low dimensional binary vectors. In both approaches, binary classifiers are learned to predict the new low dimensional representation of the categories and several algorithms are also proposed to recover the set of relevant labels. Large scale experiments validate the methods.

La métagénomique vise à étudier le contenu génétique et génomique d'un échantillon provenant d'un environnement naturel. Cette discipline récente s'attache à étudier les génomes de différents organismes provenant d'un même milieu. La métagénomique pose de nouvelles questions, tant d'un point de vue biologique qu'informatique. Les masses de données générées par les études métagénomiques et la complexité des milieux étudiés, nécessitent de développer de nouvelles structures de données et de nouveaux algorithmes dédiés. Parmi les différentes approches existantes en métagénomique, la métagénomique comparative consiste à comparer plusieurs métagénomes afin d'en connaître les divers degrés de similarité. Lorsque cette comparaison se base uniquement sur le contenu brut des échantillons, sans faire appel à des connaissances externes, on parle de métagénomique comparative de novo. L'objectif des travaux que nous proposons est de développer une méthode permettant d'extraire les séquences similaires de deux jeux de données métagénomiques, où chaque jeu peut être composé de centaines de millions de courtes séquences. La comparaison proposée consiste à identifier les séquences d'un premier jeu similaires à au moins une séquence d'un second jeu. Afin d'être rapide et économe en mémoire, l'implémentation de notre méthode a nécessité la conception d'une nouvelle structure d'indexation, basée sur le filtre de bloom. Le logiciel final, nommé Compareads, a une consommation mémoire faible (de l'ordre de quelques go) et peut calculer l'intersection de deux échantillons de 100 millions de séquences chacun en une dizaine d'heures. Notre méthode est une heuristique qui génère un faible taux de faux positifs. Le logiciel Compareads est dédié à l'analyse de grands jeux de données métagénomiques. À l'heure actuelle, il est le seul outil capable de comparer de tels jeux. Compareads a été appliqué sur plusieurs projets métagénomiques. Notre outil produit des résultats robustes, biologiquement exploitables et en accord avec diverses méthodes fondamentalement différentes. Il est actuellement utilisé de manière intensive sur les échantillons provenant de l'expédition tara oceans. Sur ce projet, notre méthode à permis de mettre en évidence que les grands systèmes océaniques influent sur la répartition globale des micro-organismes marins.

La métagénomique vise à étudier le contenu génétique et génomique d'un échantillon provenant d'un environnement naturel. Cette discipline récente s'attache à étudier les génomes de différents organismes provenant d'un même milieu. La métagénomique pose de nouvelles questions, tant d'un point de vue biologique qu'informatique. Les masses de données générées par les études métagénomiques et la complexité des milieux étudiés nécessitent de développer de nouvelles structures de données et de nouveaux algorithmes dédiés. Parmi les différentes approches existantes en métagénomique, la métagénomique comparative consiste à comparer plusieurs métagénomes afin d'en connaitre les divers degrés de similarité. Lorsque cette comparaison se base uniquement sur le contenu brut des échantillons, sans faire appel à des connaissances externes, on parle de métagénomique comparative de novo. L'objectif des travaux que nous proposons est de développer une méthode permettant d'extraire les séquences similaires entre deux jeux de données métagénomiques, où chaque jeu peut être composé de centaines de millions de courtes séquences d'adn. La comparaison proposée consiste à identifier les séquences d'un premier jeu similaires à au moins une séquence d'un second jeu. Afin d'être rapide et économe en mémoire, l'implémentation de notre méthode a nécessité la conception d'une nouvelle structure d'indexation, basée sur le filtre de bloom. Le logiciel final, nommé Compareads, a une consommation mémoire faible (de l'ordre de quelques go) et peut calculer l'intersection de deux échantillons de 100 millions de séquences chacun en une dizaine d'heures. Notre méthode est une heuristique qui génère un faible taux de faux positifs. Le logiciel Compareads est dédié à l'analyse de grands jeux de données métagénomiques. À l'heure actuelle, il est le seul outil capable de comparer de tels jeux. Compareads a été appliqué sur plusieurs projets métagénomiques. Notre outil produit des résultats robustes, biologiquement exploitables et en accord avec diverses méthodes fondamentalement différentes. Il est actuellement utilisé de manière intensive sur les échantillons provenant de l'expédition tara oceans. Sur ce projet, notre méthode a permis de mettre en évidence que les grands systèmes océaniques influent sur la répartition globale des microorganismes marins.

Dans cette thèse, nous abordons le problème de l'identification et de la quantification de variants (épissage alternatif et polymorphisme génomique) dans des données de RNA-seq sans génome de référence, et sans faire un assemblage complet des transcripts. Basé sur l'idée que chaque variant correspond à un motif reconnaissable, qu'on appelle une bulle, dans un graphe de Bruijn construit à partir des lectures de RNA-seq, nous proposons un modèle pour les variants dans de tels graphes. Nous introduisons ensuite une méthode, appelé KisSplice, pour extraire les événements d'épissage alternatif, et nous montrons qu'il trouve plus d'événements corrects que les assembleurs de transcriptome traditionnels. Afin d'améliorer son temps d'exécution, nous proposons un nouvel algorithme polynomial pour énumérer les bulles. On montre qu'il est plusieurs ordres de grandeur plus rapide que les approches précédentes. Afin de réduire sa consommation en mémoire, nous proposons une nouvelle façon de représenter un graphe de Bruijn. Nous montrons que notre approche utilise 30% à 40% moins de mémoire que l'état de l'art. Nous appliquons les techniques développées pour énumérer les bulles à deux problémes classiques. Nous donnons le premier algorithme optimal pour énumérer les cycles dans des graphes non orientés. Il s'agit de la première amélioration à ce probléme en près de 40 ans. Nous considérons ensuite une variante du problème des K chemins plus courts: au lieu de limiter le nombre des chemins, nous limitons leurs poids. Nous présentons de nouveaux algorithmes qui utilisent exponentiellement moins mémoire que les approches précédentes / In this thesis, we address the problem of identifying and quantifying variants (alternative splicing and genomic polymorphism) in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the idea that each variant corresponds to a recognizable pattern, a bubble, in a de Bruijn graph constructed from the RNA-seq reads, we propose a general model for all variants in such graphs. We then introduce an exact method, called KisSplice, to extract alternative splicing events and show that it outperforms general purpose transcriptome assemblers. We put an extra effort to make KisSplice as scalable as possible. In order to improve the running time, we propose a new polynomial delay algorithm to enumerate bubbles. We show that it is several orders of magnitude faster than previous approaches. In order to reduce its memory consumption, we propose a new compact way to build and represent a de Bruijn graph. We show that our approach uses 30% to 40% less memory than the state of the art, with an insignificant impact on the construction time. Additionally, we apply the techniques developed to list bubbles in two classical problems: cycle enumeration and the K-shortest paths problem. We give the first optimal algorithm to list cycles in undirected graphs, improving over Johnson’s algorithm. This is the first improvement to this problem in almost 40 years. We then consider a different parameterization of the K-shortest (simple) paths problem: instead of bounding the number of st-paths, we bound the weight of the st-paths. We present new algorithms using exponentially less memory than previous approaches

Les systèmes de recommandation visent à présélectionner et présenter en premier les informations susceptibles d'intéresser les utilisateurs. Ceci a suscité l'attention du commerce électronique, où l'historique des achats des utilisateurs sont analysés pour prédire leurs intérêts futurs et pouvoir personnaliser les offres ou produits (appelés aussi items) qui leur sont proposés. Dans ce cadre, les systèmes de recommandation exploitent les préférences des utilisateurs et les caractéristiques des produits et des utilisateurs pour prédire leurs préférences pour des futurs items. Bien qu'ils aient démontré leur précision, ces systèmes font toujours face à de grands défis tant pour le monde académique que pour l'industrie : ces techniques traitent un grand volume de données qui exige une parallélisation des traitements, les données peuvent être également très hétérogènes, et les systèmes de recommandation souffrent du démarrage à froid, situation dans laquelle le système n'a pas (ou pas assez) d'informations sur (les nouveaux) utilisateurs/items pour proposer des recommandations précises. La technique de factorisation matricielle a démontré une précision dans les prédictions et une simplicité de passage à l'échelle. Cependant, cette approche a deux inconvénients : la complexité d'intégrer des données hétérogènes externes (telles que les caractéristiques des items) et le démarrage à froid pour un nouvel utilisateur. Cette thèse a pour objectif de proposer un système offrant une précision dans les recommandations, un passage à l'échelle pour traiter des données volumineuses, et permettant d'intégrer des données variées sans remettre en question l'indépendance du système par rapport au domaine d'application. De plus, le système doit faire face au démarrage à froid utilisateurs car il est important de fidéliser et satisfaire les nouveaux utilisateurs. Cette thèse présente quatre contributions au domaine des systèmes de recommandation: (1) nous proposons une implémentation d'un algorithme de recommandation de factorisation matricielle parallélisable pour assurer un meilleur passage à l'échelle, (2) nous améliorons la précision des recommandations en prenant en compte l'intérêt implicite des utilisateurs dans les attributs des items, (3) nous proposons une représentation compacte des caractéristiques des utilisateurs/items basée sur les filtres de bloom permettant de réduire la quantité de mémoire utile, (4) nous faisons face au démarrage à froid d'un nouvel utilisateur en utilisant des techniques d'apprentissage actif. La phase d'expérimentation utilise le jeu de données MovieLens et la base de données IMDb publiquement disponibles, ce qui permet d'effectuer des comparaisons avec des techniques existantes dans l'état de l'art. Ces expérimentations ont démontré la précision et l'efficacité de nos approches. / Recommender Systems aim at pre-selecting and presenting first the information in which users may be interested. This has raised the attention of the e-commerce, where the interests of users are analysed in order to predict future interests and to personalize the offers (a.k.a. items). Recommender systems exploit the current preferences of users and the features of items/users in order to predict their future preference in items.Although they demonstrate accuracy in many domains, these systems still face great challenges for both academia and industry: they require distributed techniques to deal with a huge volume of data, they aim to exploit very heterogeneous data, and they suffer from cold-start, situation in which the system has not (enough) information about (new) users/items to provide accurate recommendations. Among popular techniques, Matrix Factorization has demonstrated high accurate predictions and scalability to parallelize the analysis among multiple machines. However, it has two main drawbacks: (1) difficulty of integrating external heterogeneous data such as items' features, and (2) the cold-start issue. The objective of this thesis is to answer to many challenges in the field of recommender systems: (1) recommendation techniques deal with complex analysis and a huge volume of data; in order to alleviate the time consumption of analysis, these techniques need to parallelize the process among multiple machines, (2) collaborative filtering techniques do not naturally take into account the items' descriptions in the recommendation, although this information may help to perform more accurate recommendations, (3) users' and items' descriptions in very large dataset contexts can become large and memory-consuming; this makes data analysis more complex, and (4) the new user cold-start is particularly important to perform new users' recommendations and to assure new users fidelity. Our contributions to this area are given by four aspects: (1) we improve the distribution of a matrix factorization recommendation algorithm in order to achieve better scalability, (2) we enhance recommendations performed by matrix factorization by studying the implicit interest of the users in the attributes of the items, (3) we propose an accurate and low-space binary vector based on Bloom Filters for representing users/items through a high quantity of features in low memory-consumption, and (4) we cope with the new user cold-start in collaborative filtering by using active learning techniques. The experimentation phase uses the publicly available MovieLens dataset and IMDb database, what allows to perform fair comparisons to the state of the art. Our contributions demonstrate their performance in terms of accuracy and efficiency.

La problématique des botnets, réseaux de machines infectées par des logiciels malveillants permettant de les contrôler à distance, constitue une préoccupation majeure du fait du nombre de machines infectées et des menaces associées: attaque par déni de service distribué (DDoS), spam, vol de données bancaires. Les solutions de lutte contre les botnets proposées présentent des limitations majeures dans le contexte d'un opérateur réseau (contraintes de volumétrie et de passage à l'échelle, respect de la confidentialité et de la vie privée des utilisateurs). Cette thèse propose quatre contributions orientées réseau de lutte contre les botnets. Chaque contribution traite d'une étape complémentaire dans la problématique des botnets: la première contribution permet de remonter à la source d'attaques par déni de service, et ainsi d'identifier un groupe de machines infectées à l'origine de ces attaques. La deuxième contribution concerne la détection des communications entre les machines infectées et leurs serveurs de contrôle et commande dans un réseau à large échelle, et offre ainsi l'opportunité de bloquer ces serveurs pour limiter le risque de nouvelles attaques. La troisième contribution permet une détection collaborative de botnets dans un contexte inter-domaine et inter-opérateur, permettant ainsi de lutter contre l'aspect hautement distribué de ces botnets. Enfin, la dernière contribution proposée permet de remédier aux botnets en ralentissant les communications entre les machines infectées et leur serveur de contrôle, offrant par ce biais une contre-mesure aux stratégies d'évasions développées par les cybercriminels afin de rendre leurs botnets plus résilients. / The problem of botnets, networks of infected hosts controlled remotely by attackers, is a major concern because of the number of infected hosts and associated threats, like distributed denial of service (DDoS), spams, and data theft. State of the art solutions to fight against botnets have major limitations in a context of a network operator (scalability of the solution, confidentiality and privacy of users). In this thesis, we propose four network-based contributions to fight against botnets. Each solution address a different and complementary issue in this area: the first contribution tracebacks the source of denial of service attacks which threaten the network availability, allowing by that way to identify infected devices used to perpetrate these attacks. The second contribution detects the communications between infected computers and their command and control server (C&C) in a large scale network and offers the opportunity to block these servers to minimize the risk of future attacks. The third contribution enables collaborative detection of botnets in an inter-domain and inter-operator context in order to fight against the highly distributed aspect of these botnets. Finally, the last contribution mitigates botnets by slowing down the communication between infected hosts and their C&C server, providing a countermeasure against evasion techniques developed by cybercriminals to make their botnets more resilient