OBJECTIVE: To develop a novel pharmacovigilance inferential framework to infer mechanistic explanations for asserted drug-drug interactions (DDIs) and deduce potential DDIs. MATERIALS AND METHODS: A mechanism-based DDI knowledge base was constructed by integrating knowledge from several existing sources at the pharmacokinetic, pharmacodynamic, pharmacogenetic, and multipathway interaction levels. A query-based framework was then created to utilize this integrated knowledge base in conjunction with 9 inference rules to infer mechanistic explanations for asserted DDIs and deduce potential DDIs. RESULTS: The drug-drug interactions discovery and demystification (D3) system achieved an overall 85% recall rate in terms of inferring mechanistic explanations for the DDIs integrated into its knowledge base, while demonstrating a 61% precision rate in terms of the inference or lack of inference of mechanistic explanations for a balanced, randomly selected collection of interacting and noninteracting drug pairs. DISCUSSION: The successful demonstration of the D3 system's ability to confirm interactions involving well-studied drugs enhances confidence in its ability to deduce interactions involving less-studied drugs. In its demonstration, the D3 system infers putative explanations for most of its integrated DDIs. Further enhancements to this work in the future might include ranking interaction mechanisms based on likelihood of applicability, determining the likelihood of deduced DDIs, and making the framework publicly available. CONCLUSION: The D3 system provides an early-warning framework for augmenting knowledge of known DDIs and deducing unknown DDIs. It shows promise in suggesting interaction pathways of research and evaluation interest and aiding clinicians in evaluating and adjusting courses of drug therapy.

In this paper, we survey algorithms that perform global alignment of networks or graphs. Global network alignment aligns two or more given networks to find the best mapping from nodes in one network to nodes in other networks. Since graphs are a common method of data representation, graph alignment has become important with many significant applications. Protein-protein interactions can be modeled as networks and aligning these networks of protein interactions has many applications in biological research. In this survey, we review algorithms for global pairwise alignment highlighting various proposed approaches, and classify them based on their methodology. Evaluation metrics that are used to measure the quality of the resulting alignments are also surveyed. We discuss and present a comparison between selected aligners on the same datasets and evaluate using the same evaluation metrics. Finally, a quick overview of the most popular databases of protein interaction networks is presented focusing on datasets that have been used recently.

MOTIVATION: There recently has been great interest in aligning protein-protein interaction (PPI) networks to identify potentially orthologous proteins between species. It is thought that the topological information contained in these networks will yield better orthology predictions than sequence similarity alone. Recent work has found that existing aligners have difficulty making use of both topological and sequence similarity when aligning, with either one or the other being better matched. This can be at least partially attributed to the fact that existing aligners try to combine these two potentially conflicting objectives into a single objective. RESULTS: We present Optnetalign, a multiobjective memetic algorithm for the problem of PPI network alignment that uses extremely efficient swap-based local search, mutation and crossover operations to create a population of alignments. This algorithm optimizes the conflicting goals of topological and sequence similarity using the concept of Pareto dominance, exploring the tradeoff between the two objectives as it runs. This allows us to produce many high-quality candidate alignments in a single run. Our algorithm produces alignments that are much better compromises between topological and biological match quality than previous work, while better characterizing the diversity of possible good alignments between two networks. Our aligner's results have several interesting implications for future research on alignment evaluation, the design of network alignment objectives and the interpretation of alignment results. AVAILABILITY AND IMPLEMENTATION: The C++ source code to our program, along with compilation and usage instructions, is available at https://github.com/crclark/optnetaligncpp/

MOTIVATION: As biological inquiry produces ever more network data, such as protein-protein interaction networks, gene regulatory networks and metabolic networks, many algorithms have been proposed for the purpose of pairwise network alignment-finding a mapping from the nodes of one network to the nodes of another in such a way that the mapped nodes can be considered to correspond with respect to both their place in the network topology and their biological attributes. This technique is helpful in identifying previously undiscovered homologies between proteins of different species and revealing functionally similar subnetworks. In the past few years, a wealth of different aligners has been published, but few of them have been compared with one another, and no comprehensive review of these algorithms has yet appeared. RESULTS: We present the problem of biological network alignment, provide a guide to existing alignment algorithms and comprehensively benchmark existing algorithms on both synthetic and real-world biological data, finding dramatic differences between existing algorithms in the quality of the alignments they produce. Additionally, we find that many of these tools are inconvenient to use in practice, and there remains a need for easy-to-use cross-platform tools for performing network alignment.