The problem of developing drugs that can be used to cure diseases is important and requires a careful approach. Since pursuing the wrong candidate drug for a particular disease could be very costly in terms of time and money, there is a strong interest in minimizing such risks. Drug repositioning has become a hot topic of research, as it helps reduce these risks significantly at the early stages of drug development by reusing an approved drug for the treatment of a different disease. Still, finding new usage for a drug is non-trivial, as it is necessary to find out strong supporting evidence that the proposed new uses of drugs are plausible. Many computational approaches were developed to narrow the list of possible candidate drug-target interactions (DTIs) before any experiments are done. However, many of these approaches suffer from unacceptable levels of false positives. We developed two novel methods based on graph mining networks of drugs and targets. The first method (DASPfind) finds all non-cyclic paths that connect a drug and a target, and using a function that we define, calculates a score from all the paths. This score describes our confidence that DTI is correct. We show that DASPfind significantly outperforms other state-of-the-art methods in predicting the top ranked target for each drug. We demonstrate the utility of DASPfind by predicting 15 novel DTIs over a set of ion channel proteins, and confirming 12 out of these 15 DTIs through experimental evidence reported in literature and online drug databases. The second method (DASPfind+) modifies DASPfind in order to increase the confidence and reliability of the resultant predictions. Based on the structure of the drug-target interaction (DTI) networks, we introduced an optimization scheme that incrementally alters the network structure locally for each drug to achieve more robust top 1 ranked predictions. Moreover, we explored effects of several similarity measures between the targets on the prediction accuracy and proposed an enhanced strategy for DTI prediction. Our results show significant improvements of the accuracy of the top ranked DTI prediction over the current state-of-the-art methods.

Causal graphs are a useful notation to represent the interplay between the actors as well as the polarity and strength of the relationship that they share. They are used extensively in educational, professional, and industrial contexts to simulate different scenarios, validate behavioral aspects, visualize the connections between different processes, and explore the adversarial effects of changing certain nodes. However, as the size of the causal graphs increase, interpreting them also becomes increasingly tougher. In such cases, new analytical tools are required to enhance the user's comprehension of the graph, both in terms of correctness and speed. To this purpose, this thesis introduces 1) a system that allows for causal exploration of directed graphs, while enabling the user to see the effect of interventions on the target nodes, 2) the use of natural language generation techniques to create a coherent passage explaining the propagation effects, and 3) results of an expert user study validating the efficacy of the narratives in enhancing the user's understanding of the causal graphs. In overall, the system aims to enhance user experience and promote further causal exploration. / Master of Science / Narrative generation is the art of creating coherent snippets of text that cumulatively describe a succession of events, played across a period of time. These goals of narrative generation are also shared by causal graphs – models that encapsulate inferences between the nodes through the strength and polarity of the connecting edges. Causal graphs are an useful mechanism to visualize changes propagating amongst nodes in the system. However, as the graph starts addressing real-world actors and their interactions, it becomes increasingly difficult to understand causal inferences between distant nodes, especially if the graph is cyclic. Moreover, if the value of more than a single node is altered and the cumulative effect of the change is to be perceived on a set of target nodes, it becomes extremely difficult to the human eye. This thesis attempts to alleviate this problem by generating dynamic narratives detailing the effect of one or more interventions on one or more target nodes, incorporating time-series analysis, Wikification, and spike detection. Moreover, the narrative enhances the user's understanding of the change propagation occurring in the system. The efficacy of the narrative was further corroborated by the results of user studies, which concluded that the presence of the narrative aids the user's confidence level, correctness, and speed while exploring the causal network.

Tout d'abord, nous présentons des méthodes permettant d'inférer un graphe à partir de signaux, afin de modéliser le support des données à classifier. Ensuite, des translations préservant les voisinages des sommets sont identifiées sur le graphe inféré. Enfin, ces translations sont utilisées pour déplacer un noyau convolutif sur le graphe, afin dedéfinir un réseau de neurones convolutif adapté aux données d'entrée.Nous avons illustré notre méthodologie sur une base de données d'images. Sans utiliser de connaissances sur les signaux, nous avons pu inférer un graphe proche d'une grille. Les translations sur ce graphe sont proches des translations Euclidiennes, ce qui nous a permis de définir un réseau de neurones convolutif très similaire à ce que l'on aurait pu obtenir en utilisant l'information que les signaux sont des images. Ce réseau, entraîné sur les données initiales, a dépassé lesperformances des méthodes de l'état de l'art de plus de 13 points, tout en étant simple et facilement améliorable.La méthode que nous avons introduite est une généralisation des réseaux de neurones convolutifs, car ceux-ci sont des cas particuliers de notre approche quand le graphe est une grille. Nos travaux ouvrent donc de nombreuses perspectives, car ils fournissent une méthode efficace pour construire des réseaux adaptés aux données. / This manuscript sums up our work on extending convolutional neuralnetworks to irregular domains through graph inference. It consists of three main chapters, each giving the details of a part of a methodology allowing the definition of such networks to process signals evolving on graphs with unknown structures.First, graph inference from data is explored, in order to provide a graph modeling the support of the signals to classify. Second, translation operators that preserve neighborhood properties of the vertices are identified on the inferred graph. Third, these translations are used to shift a convolutional kernel on the graph in order to define a convolutional neural network that is adapted to the input data.We have illustrated our methodology on a dataset of images. While not using any particular knowledge on the signals, we have been able to infer a graph that is close to a grid. Translations on this graph resemble Euclidean translations. Therefore, this has allowed us to define an adapted convolutional neural network that is very close what one would obtain when using the information that signals are images. This network, trained on the initial data, has out performed state of the art methods by more than 13 points, while using a very simple and easily improvable architecture.The method we have introduced is a generalization of convolutional neural networks. As a matter of fact, they can be seen as aparticularization of our approach in the case where the graph is a grid. Our work thus opens the way to numerous perspectives, as it provides an efficient way to build networks that are adapted to the data.

L'inférence de réseaux ou inférence de graphes a de plus en plus d'applications notamment en santé humaine et en environnement pour l'étude de données micro-biologiques et génomiques. Les réseaux constituent en effet un outil approprié pour représenter, voire étudier des relations entre des entités. De nombreuses techniques mathématiques d'estimation ont été développées notamment dans le cadre des modèles graphiques gaussiens mais aussi dans le cas de données binaires ou mixtes. Le traitement des données d'abondance (de micro-organismes comme les bactéries par exemple) est particulier pour deux raisons : d'une part elles ne reflètent pas directement la réalité car un processus de séquençage a lieu pour dupliquer les espèces et ce processus apporte de la variabilité, d'autre part une espèce peut être absente dans certains échantillons. On est alors dans le cadre de données inflatées en zéro. Beaucoup de méthodes d'inférence de réseaux existent pour les données gaussiennes, les données binaires et les données mixtes mais les modèles inflatés en zéro sont très peu étudiés alors qu'ils reflètent la structure de nombreux jeux de données de façon pertinente. L'objectif de cette thèse concerne l'inférence de réseaux pour les modèles inflatés en zéro. Dans cette thèse, on se limitera à des réseaux de dépendances conditionnelles. Le travail présenté dans cette thèse se décompose principalement en deux parties. La première concerne des méthodes d'inférence de réseaux basées sur l'estimation de voisinages par une procédure couplant des méthodes de régressions ordinales et de sélection de variables. La seconde se focalise sur l'inférence de réseaux dans un modèle où les variables sont des gaussiennes inflatées en zéro par double troncature (à droite et à gauche). / Network inference has more and more applications, particularly in human health and environment, for the study of micro-biological and genomic data. Networks are indeed an appropriate tool to represent, or even study, relationships between entities. Many mathematical estimation techniques have been developed, particularly in the context of Gaussian graphical models, but also in the case of binary or mixed data. The processing of abundance data (of microorganisms such as bacteria for example) is particular for two reasons: on the one hand they do not directly reflect reality because a sequencing process takes place to duplicate species and this process brings variability, on the other hand a species may be absent in some samples. We are then in the context of zero-inflated data. Many graph inference methods exist for Gaussian, binary and mixed data, but zero-inflated models are rarely studied, although they reflect the structure of many data sets in a relevant way. The objective of this thesis is to infer networks for zero-inflated models. In this thesis, we will restrict to conditional dependency graphs. The work presented in this thesis is divided into two main parts. The first one concerns graph inference methods based on the estimation of neighbourhoods by a procedure combining ordinal regression models and variable selection methods. The second one focuses on graph inference in a model where the variables are Gaussian zero-inflated by double truncation (right and left).