Parameterized algorithmics for finding connected motifs in biological networks

Temporal networks in biology and medicine: a survey on models, algorithms, and tools

The use of static graphs for modelling and analysis of biological and biomedical data plays a key role in biomedical research. However, many real-world scenarios present dynamic behaviours resulting in both node and edges modification as well as feature evolution. Consequently, ad-hoc models for capturing these evolutions along the time have been introduced, also referred to as dynamic, temporal, time-varying graphs. Here, we focus on temporal graphs, i.e., graphs whose evolution is represented by a sequence of time-ordered snapshots. Each snapshot represents a graph active in a particular timestamp. We survey temporal graph models and related algorithms, presenting fundamentals aspects and the recent advances. We formally define temporal graphs, focusing on the problem setting and we present their main applications in biology and medicine. We also present temporal graph embedding and the application to recent problems such as epidemic modelling. Finally, we further state some promising research directions in the area. Main results of this study include a systematic review of fundamental temporal network problems and their algorithmic solutions considered in the literature, in particular those having application in computational biology and medicine. We also include the main software developed in this context.

Detecting list-colored graph motifs in biological networks using branch-and-bound strategy

In this work, we study the list-colored graph motif problem, which was introduced to detect functional motifs in biological networks. Given a multi-set M of colors as the query motif and a list-colored graph G where each vertex in G is associated with a set of colors, the aim of this problem is to find a sub-graph of G whose vertex set is colored exactly as motif M. To solve this problem, we present a heuristic method to efficiently and accurately detect list-colored graph motifs in biological networks using branch-and-bound strategy. We transform the detection of list-colored graph motif to the search of connected induced sub-graphs in list-colored graph, where the vertices in the sub-graph are assigned to distinctive colors of query motif. This transformation enables our method to accurately discover the occurrences of query motif without enumerating and verifying all sub-graphs. Furthermore, a new initial vertex selection strategy based on the colors of vertices is proposed to accurately determine the search scope of motifs. Experiments conducted on metabolic networks and protein-interaction networks demonstrate that our method can achieve better performance in accuracy and efficiency in comparison to other existing methods.

Trios-promising in silico biomarkers for differentiating the effect of disease on the human microbiome network

Recent advances in the HMP (human microbiome project) research have revealed profound implications of the human microbiome to our health and diseases. We postulated that there should be distinctive features associated with healthy and/or diseased microbiome networks. Following Occam's razor principle, we further hypothesized that triangle motifs or trios, arguably the simplest motif in a complex network of the human microbiome, should be sufficient to detect changes that occurred in the diseased microbiome. Here we test our hypothesis with six HMP datasets that cover five major human microbiome sites (gut, lung, oral, skin, and vaginal). The tests confirm our hypothesis and demonstrate that the trios involving the special nodes (e.g., most abundant OTU or MAO, and most dominant OTU or MDO, etc.) and interactions types (positive vs. negative) can be a powerful tool to differentiate between healthy and diseased microbiome samples. Our findings suggest that 12 kinds of trios (especially, dominantly inhibitive trio with mixed strategy, dominantly inhibitive trio with pure strategy, and fully facilitative strategy) may be utilized as in silico biomarkers for detecting disease-associated changes in the human microbiome, and may play an important role in personalized precision diagnosis of the human microbiome associated diseases.

Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems

Fixed-parameter algorithms are designed to efficiently find optimal solutions to some computationally hard (NP-hard) problems by identifying and exploiting "small" problem-specific parameters. We survey practical techniques to develop such algorithms. Each technique is introduced and supported by case studies of applications to biological problems, with additional pointers to experimental results.

An Integrated Data Driven Approach to Drug Repositioning Using Gene-Disease Associations

Drug development is both increasing in cost whilst decreasing in productivity. There is a general acceptance that the current paradigm of R&D needs to change. One alternative approach is drug repositioning. With target-based approaches utilised heavily in the field of drug discovery, it becomes increasingly necessary to have a systematic method to rank gene-disease associations. Although methods already exist to collect, integrate and score these associations, they are often not a reliable reflection of expert knowledge. Furthermore, the amount of data available in all areas covered by bioinformatics is increasing dramatically year on year. It thus makes sense to move away from more generalised hypothesis driven approaches to research to one that allows data to generate their own hypothesis. We introduce an integrated, data driven approach to drug repositioning. We first apply a Bayesian statistics approach to rank 309,885 gene-disease associations using existing knowledge. Ranked associations are then integrated with other biological data to produce a semantically-rich drug discovery network. Using this network, we show how our approach identifies diseases of the central nervous system (CNS) to be an area of interest. CNS disorders are identified due to the low numbers of such disorders that currently have marketed treatments, in comparison to other therapeutic areas. We then systematically mine our network for semantic subgraphs that allow us to infer drug-disease relations that are not captured in the network. We identify and rank 275,934 drug-disease has_indication associations after filtering those that are more likely to be side effects, whilst commenting on the top ranked associations in more detail. The dataset has been created in Neo4j and is available for download at https://bitbucket.org/ncl-intbio/genediseaserepositioning along with a Java implementation of the searching algorithm.

Mining integrated semantic networks for drug repositioning opportunities

Current research and development approaches to drug discovery have become less fruitful and more costly. One alternative paradigm is that of drug repositioning. Many marketed examples of repositioned drugs have been identified through serendipitous or rational observations, highlighting the need for more systematic methodologies to tackle the problem. Systems level approaches have the potential to enable the development of novel methods to understand the action of therapeutic compounds, but requires an integrative approach to biological data. Integrated networks can facilitate systems level analyses by combining multiple sources of evidence to provide a rich description of drugs, their targets and their interactions. Classically, such networks can be mined manually where a skilled person is able to identify portions of the graph (semantic subgraphs) that are indicative of relationships between drugs and highlight possible repositioning opportunities. However, this approach is not scalable. Automated approaches are required to systematically mine integrated networks for these subgraphs and bring them to the attention of the user. We introduce a formal framework for the definition of integrated networks and their associated semantic subgraphs for drug interaction analysis and describe DReSMin, an algorithm for mining semantically-rich networks for occurrences of a given semantic subgraph. This algorithm allows instances of complex semantic subgraphs that contain data about putative drug repositioning opportunities to be identified in a computationally tractable fashion, scaling close to linearly with network data. We demonstrate the utility of our approach by mining an integrated drug interaction network built from 11 sources. This work identified and ranked 9,643,061 putative drug-target interactions, showing a strong correlation between highly scored associations and those supported by literature. We discuss the 20 top ranked associations in more detail, of which 14 are novel and 6 are supported by the literature. We also show that our approach better prioritizes known drug-target interactions, than other state-of-the art approaches for predicting such interactions.

RANGI: a fast list-colored graph motif finding algorithm

Given a multiset of colors as the query and a list-colored graph, i.e., an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query. This problem was introduced to find functional motifs in biological networks. We present a branch-and-bound algorithm named RANGI for finding and enumerating list-colored graph motifs. As our experimental results show, RANGI's pruning methods and heuristics make it quite fast in practice compared to the algorithms presented in the literature. We also present a parallel version of RANGI that achieves acceptable scalability.