Graph theory enables drug repurposing--how a mathematical model can drive the discovery of hidden mechanisms of action.

We introduce a methodology to efficiently exploit natural-language expressed biomedical knowledge for repurposing existing drugs towards diseases for which they were not initially intended. Leveraging on developments in Computational Linguistics and Graph Theory, a methodology is defined to build a graph representation of knowledge, which is automatically analysed to discover hidden relations between any drug and any disease: these relations are specific paths among the biomedical entities of the graph, representing possible Modes of Action for any given pharmacological compound. We propose a measure for the likeliness of these paths based on a stochastic process on the graph. This measure depends on the abundance of indirect paths between a peptide and a disease, rather than solely on the strength of the shortest path connecting them. We provide real-world examples, showing how the method successfully retrieves known pathophysiological Mode of Action and finds new ones by meaningfully selecting and aggregating contributions from known bio-molecular interactions. Applications of this methodology are presented, and prove the efficacy of the method for selecting drugs as treatment options for rare diseases.

Exploring complex networks via topological embedding on surfaces.

We demonstrate that graphs embedded on surfaces are a powerful and practical tool to generate, to characterize, and to simulate networks with a broad range of properties. Any network can be embedded on a surface with sufficiently high genus and therefore the study of topologically embedded graphs is non-restrictive. We show that the local properties of the network are affected by the surface genus which determines the average degree, which influences the degree distribution, and which controls the clustering coefficient. The global properties of the graph are also strongly affected by the surface genus which is constraining the degree of interwovenness, changing the scaling properties of the network from large-world kind (small genus) to small- and ultrasmall-world kind (large genus). Two elementary moves allow the exploration of all networks embeddable on a given surface and naturally introduce a tool to develop a statistical mechanics description for these networks. Within such a framework, we study the properties of topologically embedded graphs which dynamically tend to lower their energy towards a ground state with a given reference degree distribution. We show that the cooling dynamics between high and low "temperatures" is strongly affected by the surface genus with the manifestation of a glass-like transition occurring when the distance from the reference distribution is low. We prove, with examples, that topologically embedded graphs can be built in a way to contain arbitrary complex networks as subgraphs. This method opens a new avenue to build geometrically embedded networks on hyperbolic manifolds.