Search

Temporal networks are graphs where each edge is associated with a timestamp denoting when two nodes interact. Temporal Subgraph Isomorphism (TSI) aims at retrieving all the subgraphs of a temporal network (called target) matching a smaller temporal network (called query), such that matched target edges appear in the same chronological order of corresponding query edges. Few algorithms have been proposed to solve the TSI problem (or variants of it) and most of them are applicable only to small or specific queries. In this paper we present TemporalRI, a new subgraph isomorphism algorithm for temporal networks with multiple contacts between nodes, which is inspired by RI algorithm. TemporalRI introduces the notion of temporal flows and uses them to filter the search space of candidate nodes for the matching. Our algorithm can handle queries of any size and any topology. Experiments on real networks of different sizes show that TemporalRI is very efficient compared to the state-of-the-art, especially for large queries and targets.

Background/Aim: Malignant melanoma is a skin cancer originating from the oncogenic transformation of melanocytes located in the epidermal layers. Usually, the patient’s prognosis depends on timing of disease detection and molecular and genetic profiling, which may all significantly influence mortality rates. Genetic analyses often detect somatic BRAF, NRAS and cKIT mutations, germline substitutions in CDKN2A, and alterations of the PI3K-AKT-PTEN pathway. A peculiar molecular future of melanoma is its high immunogenicity, making this tumor targetable by programmed cell death protein 1-specific antibodies. Materials and Methods: Ten formalin-fixed paraffin embedded samples derived from melanoma patients were subjected to next-generation sequencing (NGS) analysis using the FDA-approved FoundationOne CDx™ test. The molecular features of each case were then analyzed employing several in silico prediction tools. Results: We analyzed the mutational landscape of patients with metastatic or relapsed cutaneous melanoma to define enriched pathways and protein-protein interactions. The analysis showed that both known genetic alterations and variants of unknown significance rely on redundant signaling converging on similar gene ontology biological processes. Complex informatics analyses of NGS-based genetic results identified pivotal signaling pathways that could provide additional targets for cancer treatment. Conclusion: Our data suggest an additional role for NGS in melanoma, as analysis of comprehensive genetic findings using innovative informatic tools may lengthen the list of druggable molecular targets that impact patient outcome.

Sarcomas are mesenchymal-derived cancers with overlapping clinical and pathologic features and a remarkable histological heterogeneity. While a precise diagnosis is often challenging to achieve, systemic treatment of sarcomas is still quite uniform. In this scenario, next generation sequencing (NGS) may be exploited to assist diagnosis and to identify specific targetable alterations. However, the precise role of genomic characterization in these diseases is still debated. In the present study, we analyzed 18 samples from 11 low-incidence sarcomas using NGS technology. We also used an in-silico prediction tool to reclassify variants of unknown significance and then looked for potentially druggable alterations to match with targeted therapies. Our cohort presented several predictable findings (e.g. MYC amplification in radio-induced angio-sarcoma, COL1A1-PDGFB rearrangements in dermatofibrosarcoma protuberans) along with unexpected results (e.g. the reciprocal WT1-EWSR1 fusion in a desmoplastic small round cell tumor). One third of patients (6/18) displayed at least one actionable molecular alterations. Our experience confirms the potential role of NGS in the management of rare sarcomas. This tool may support the diagnostic process, but also detect targets for personalized therapies.

Pathway analysis is a wide class of methods allowing to determine the alteration of functional processes in complex diseases. However, biological pathways are still partial, and knowledge coming from posttranscriptional regulators has started to be considered in a systematic way only recently. Here we will give a global and updated view of the main pathway and subpathway analysis methodologies, focusing on the improvements obtained through the recent introduction of microRNAs as regulatory elements in these frameworks.

A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding all the possible subgraphs of a target graph that are structurally equivalent to an input pattern graph. Targets may be very large and complex structures compared to patterns. Methods that address this NP-complete problem use heuristics. Their performance in both time and quality depends on a few subtleties of those heuristics. This paper compares the performance of state-of-the-art algorithms for subgraph isomorphism on small, medium and very large graphs. Results show that heuristics based on pattern graphs alone prove to be the most efficient, an unexpected result.

A labelled multi-relational network (or labelled multigraph, for short) is one in which nodes have labels and a pair of nodes may be connected by an edge with one or more labels. For example, in an airline route database, ‘large European city’ may be the label on the Paris node and ‘large Asian city’ may be the label on the New Delhi node and the edge between the two cities may be labelled by several carriers. This article presents an analytical method to compute the p-values of labelled subgraph (sub-network) motifs in such labelled multi-relational networks (multigraphs). The method (and a fast approximation to the method) works for both directed and undirected graphs and extends to large subgraphs. We have validated these methods on a dataset of medium size real networks (up to tens of thousands of nodes and hundreds of thousands of edges) of different types (biological, infrastructural and collaboration networks). The pure analytical model is faster than a randomized simulation model by a factor of approximately 1000 in most of our experiments. This improvement in performance is greater for larger graphs. The approximate analytical model avoids the calculations of statistical variance and achieves nearly the same precision and recall as the pure analytical model while being several times faster. To test the scalability of our methods, we run our algorithms on synthetic and real datasets from protein–protein interaction networks, airline flight paths, the internet infrastructural network and the IMDB movie network. We also illustrate a use case of this form of analysis on a large relationship network of people involved in the Panama papers scandal, retrieving frequently used money laundering patterns. labelled multigraphs motif enumeration; motif statistical significance; random network models; multi-relational networks; multigraphs.

Pathway analysis is a wide class of methods allowing to determine the alteration of functional processes in complex diseases. However, biological pathways are still partial, and knowledge coming from posttranscriptional regulators has started to be considered in a systematic way only recently. Here we will give a global and updated view of the main pathway and subpathway analysis methodologies, focusing on the improvements obtained through the recent introduction of microRNAs as regulatory elements in these frameworks.

Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.

Frequent pattern mining is an important research field and can be applied to different labeled data structures ranging from itemsets to graphs. There are scenarios where a label can be assigned to a taxonomy and generalized patterns can be mined by replacing labels by their ancestors. In this work, we propose a novel approach to generalized frequent subgraph mining. In contrast to existing work, our approach considers new requirements from use cases beyond molecular databases. In particular, we support directed multigraphs as well as multiple taxonomies to deal with the different semantic meaning of vertices. Since results of generalized frequent subgraph mining can be very large, we use a fast analytical method of p-value estimation to rank results by significance. We propose two extensions of the popular gSpan algorithm that mine frequent subgraphs across all taxonomy levels. We compare both algorithms in an experimental evaluation based on a database of business process executions represented by graphs.

Background The analysis of tissue-specific protein interaction networks and their functional enrichment in pathological and normal tissues provides insights on the etiology of diseases. The Pan-cancer proteomic project, in The Cancer Genome Atlas, collects protein expressions in human cancers and it is a reference resource for the functional study of cancers. However, established protocols to infer interaction networks from protein expressions are still missing. Results We have developed a methodology called Inference Network Based on iRefIndex Analysis (INBIA) to accurately correlate proteomic inferred relations to protein-protein interaction (PPI) networks. INBIA makes use of 14 network inference methods on protein expressions related to 16 cancer types. It uses as reference model the iRefIndex human PPI network. Predictions are validated through non-interacting and tissue specific PPI networks resources. The first, Negatome, takes into account likely non-interacting proteins by combining both structure properties and literature mining. The latter, TissueNet and GIANT, report experimentally verified PPIs in more than 50 human tissues. The reliability of the proposed methodology is assessed by comparing INBIA with PERA, a tool which infers protein interaction networks from Pathway Commons, by both functional and topological analysis. Conclusion Results show that INBIA is a valuable approach to predict proteomic interactions in pathological conditions starting from the current knowledge of human protein interactions. Electronic supplementary material The online version of this article (10.1186/s12859-018-2183-5) contains supplementary material, which is available to authorized users.

Motif discovery is the problem of finding subgraphs of a network that appear surprisingly often. Each such subgraph may indicate a small-scale interaction feature in applications ranging from a genomic interaction network, a significant relationship involving rock musicians, or any other application that can be represented as a network. We look at the problem of constrained search for motifs based on labels (e.g. gene ontology, musician type to continue our example from above). This chapter presents a brief review of the state of the art in motif finding and then extends the gTrie data structure from Ribeiro and Silva (Data Min Knowl Discov 28(2):337–377, 2014b) to support labels. Experiments validate the usefulness of our structure for small subgraphs, showing that we recoup the cost of the index after only a handful of queries.

Network motif discovery is the problem of finding subgraphs of a network that occur more frequently than expected, according to some reasonable null hypothesis. Such subgraphs may indicate small scale interaction features in genomic interaction networks or intriguing relationships involving actors or a relationship among airlines. When nodes are labeled, they can carry information such as the genomic entity under study or the dominant genre of an actor. For that reason, labeled subgraphs convey information beyond structure and could therefore enjoy more applications. To identify statistically significant motifs in a given network, we propose an analytical method (i.e. simulation-free) that extends the works of Picard et al. (J Comput Biol 15(1):1---20, 2008) and Schbath et al. (J Bioinform Syst Biol 2009(1):616234, 2009) to label-dependent scale-free graph models. We provide an analytical expression of the mean and variance of the count under the Expected Degree Distribution random graph model. Our model deals with both induced and non-induced motifs. We have tested our methodology on a wide set of graphs ranging from protein---protein interaction networks to movie networks. The analytical model is a fast (usually faster by orders of magnitude) alternative to simulation. This advantage increases as graphs grow in size.

Protein–protein interaction (PPI) networks available in public repositories usually represent relationships between proteins within the cell. They ignore the specific set of tissues or tumors where the interactions take place. Indeed, proteins can form tissue-selective complexes, while they remain inactive in other tissues. For these reasons, a great attention has been recently paid to tissue-specific PPI networks, in which nodes are proteins of the global PPI network whose corresponding genes are preferentially expressed in specific tissues. In this paper, we present SPECTRA, a knowledge base to build and compare tissue or tumor-specific PPI networks. SPECTRA integrates gene expression and protein interaction data from the most authoritative online repositories. We also provide tools for visualizing and comparing such networks, in order to identify the expression and interaction changes of proteins across tissues, or between the normal and pathological states of the same tissue. SPECTRA is available as a web server at http://alpha.dmi.unict.it/spectra.

Comparing protein interaction networks can reveal interesting patterns of interactions for a specific function or process in distantly related species. In this paper we present GASOLINE, a Cytoscape app for multiple local alignments of PPI (protein-protein interaction) networks. The app is based on the homonymous greedy and stochastic algorithm. GASOLINE starts with the identification of sets of similar nodes, called seeds of the alignment. Alignments are then extended in a greedy manner and finally refined. Both the identification of seeds and the extension of alignments are performed through an iterative Gibbs sampling strategy. GASOLINE is a Cytoscape app for computing and visualizing local alignments, without requiring any post-processing operations. GO terms can be easily attached to the aligned proteins for further functional analysis of alignments. GASOLINE can perform the alignment task in few minutes, even for a large number of input networks.

Multiple local structure comparison helps to identify common structural motifs or conserved binding sites in 3D structures in distantly related proteins. Since there is no best way to compare structures and evaluate the alignment, a wide variety of techniques and different similarity scoring schemes have been proposed. Existing algorithms usually compute the best superposition of two structures or attempt to solve it as an optimization problem in a simpler setting (e.g., considering contact maps or distance matrices). Here, we present PROPOSAL (PROteins comparison through Probabilistic Optimal Structure local ALignment), a stochastic algorithm based on iterative sampling for multiple local alignment of protein structures. Our method can efficiently find conserved motifs across a set of protein structures. Only the distances between all pairs of residues in the structures are computed. To show the accuracy and the effectiveness of PROPOSAL we tested it on a few families of protein structures. We also compared PROPOSAL with two state-of-the-art tools for pairwise local alignment on a dataset of manually annotated motifs. PROPOSAL is available as a Java 2D standalone application or a command line program at http://ferrolab.dmi.unict.it/proposal/proposal.html.

Motivations. A central problem in biological network analysis is the Local Network Alignment. The aim is to detect conserved subnetworks or complexes of proteins, across two or more species, which are involved in processes or functions. This allows to predict either new interactions or the functions of unknown proteins. Since the problem of finding conserved subnetworks in a set of networks is related to subgraph isomorphism, which is known to be NP-Hard, several heuristics have been proposed. These include PathBlast [1] and MaWISh [2] for pairwise local alignment and NetworkBlast-M [3] and Graemlin [4] for the multiple case. Although NetworkBlast-M has been proved to be the most efficient and accurate method, it is able to find significant conserved complexes composed by no more than 15 proteins. Here we introduce GASOLINE (Greedy And Stochastic algorithm for Optimal Local alignment of Interaction Networks) an algorithm based on Gibbs Sampling [5] in connection to a seed-extend approach to search for significant conserved complexes of any size. Methods. The algorithm consists of two main phases. In the first phase, we look for ortholog proteins across the networks. We call these proteins seeds of the suboptimal pattern. In the second phase, called iterative phase, we extend each seed, by adding one adjacent node. Here, through a stochastic process based on Gibbs Sampling, we choose a node among a set of randomly picked adjacent ones. The chosen nodes will be those that maximize similarity among the N extended seeds. We repeat the iterative phase until we obtain a set of N conserved subgraphs each of size W. These N subgraphs represent our final alignment. The topological density and the conservation of a complex are measured through an Index of Density and Structural Conservation (hereafter IDSC). The IDSC score ranges from 0 to 1 and it is dynamically computed during the iterative phase. The iteration will terminate when IDSC is above a fixed threshold. This allows the removal of parameter W producing a set of highly dense and conserved complexes of different sizes. Results. GASOLINE has been tested on 10 microbial PPI networks, taken from Graemlin [4] and on 6 eukaryotic PPI networks, taken from STRING database [6]. The number of proteins in microbial networks ranges from 1,000 to 7,000 with the amount of interactions ranging from 13,000 to 230,000, whereas the size of eukaryotic networks ranges from 6,000 to 12,500 proteins and from 26,000 to 166,000 edges. 2000 of execution of GASOLINE have been performed. As output we consider the best distinct (not overlapping) complexes, with respect to size andIDSC score. In our experiments we selected complexes of at least 5 proteins with IDSC score > 0.7. All tests have been performed on an Intel Core i5-2500 3.30Ghz CPU with 4 GB RAM. The complexes computed by the algorithm have been then validated by annotating their proteins with GO categories. For the microbial networks, annotations have been downloaded from DAVID [7,8], while eukaryotic networks proteins have been annotated using BioDBNet [9]. Significant conserved categories have been obtained by computing a p-value (< 0.0001), based on hypergeometric distribution. A GO category has been considered conserved when it resulted significant in at least N-1 species, where N is the number of aligned networks. The executions of GASOLINE on microbial networks revealed the existence of a big conserved complex of 40 proteins, forming the large and small subunits of ribosome, with IDSC equals to 0.755 (see Tab. 1). As for the 6 eukaryotic networks, 15 conserved complexes have been found by GASOLINE with IDSC greater than 0.75. They are listed in Tab. 2, with their IDSC and the number of GO categories enriched. References 1. Kelley BP, Sharan R, Karp R, Sittler ET, Root DE, Stockwell BR, and Ideker T. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc Natl Acad Sci U S A 100, 11394-9, 2003. 2. Koyuturk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, and Grama A, Pairwise alignment of protein interaction networks, Journal of Computational Biology, 13(2), 182-199, 2006 3. Kalaev M, Bafna V, and Sharan R. Fast and accurate alignment of multiple protein networks. Journal of computational biology, 16(8), 989–999, 2009. 4. Flannick J, Novak A, Srinivasan B, McAdams H, and Batzoglou S. Graemlin: general and robust alignment of multiple large interaction networks. Genome research, 16(9), 1169, 2006 5. Geman S, Geman D. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence 6 (6): 721–741, 1984 6. Szklarczyk D, Franceschini A, Kuhn M, Simonovic M, Roth A, Minguez P, Doerks T, Stark M, Muller J, Bork P, Jensen LJ, von Mering C. The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res. 39 (Database issue):D561-8. Epub 2010 Nov 2, 2011. 7. Huang DW, Sherman BT, Lempicki RA. Systematic and integrative analysis of large gene lists using DAVID Bioinformatics Resources. Nature Protoc. 4(1):44-57, 2009. 8. Huang DW, Sherman BT, Lempicki RA. Bioinformatics enrichment tools: paths toward the comprehensive functional analysis of large gene lists. Nucleic Acids Res. 37(1):1-13, 2009 9. Mudunuri U, Che A, Yi M, and Stephens RM. BioDBnet: the biological database network. Bioinformatics. 25(4): 555–556, 2009

The value of recommending latex allergy screening in allergy departments of the Army's Hospital was studied. The purpose of the study was to evaluate whether atopy was a risk factor for latex sensitization in a specific population such as the young male soldiers of the Italian Army. The study was also aimed to assess the role of other risk factors. One thousand five hundred male subjects (1000 subjects who were atopic and 500 subjects who were nonatopic), visiting the Department of Allergology and Respiratory Physiopathology of the Army's Hospital in Bari, Italy, were enrolled into the study. The protocol included a questionnaire (symptoms of atopy, use of latex gloves and condoms and possible reactions previous surgical procedures), a clinical examination, a skin-prick test to latex and common allergens to evaluate atopy, and in part a latex challenge. Among the 1000 subjects who were atopic, 2.8% had evidence for sensitization to latex compared with 1.2% in the 500 subjects in the nonatopic group. The risk of latex sensitization was 19 times higher for subjects with a history of reactions to latex exposure and had a twofold increase for each surgical procedure and for each skin test positivity for inhalant allergens. Another risk factor was positivity to skin-prick tests for Artemisia vulgaris, cypress, and molds. Atopy significantly relates to an increased risk of latex sensitization. Screening is recommended in the Army's Hospital to identify latex-sensitized subjects and inform them about the risks connected with this condition.