Local graph alignment and motif search in biological networks

Background: The computation of the statistical properties of motif occurrences has an obviously relevant practical application: for example, patterns that are significantly over- or under-represented in the genome are interesting candidates for biological roles. However, the problem is computationally hard; as a result, virtually all the existing pipelines use fast but approximate scoring functions, in spite of the fact that they have been shown to systematically produce inco...

Network alignment aims to uncover topologically similar regions in the protein-protein interaction (PPI) networks of two or more species under the assumption that topologically similar regions tend to perform similar functions. Although there exist a plethora of both network alignment algorithms and measures of topological similarity, currently no gold standard exists for evaluating how well either is able to uncover functionally similar regions. Here we propose a formal, mat...

Networks are a fundamental model of complex systems throughout the sciences, and network datasets are typically analyzed through lower-order connectivity patterns described at the level of individual nodes and edges. However, higher-order connectivity patterns captured by small subgraphs, also called network motifs, describe the fundamental structures that control and mediate the behavior of many complex systems. We develop three tools for network analysis that use higher-ord...

Gene regulatory networks are powerful abstractions of biological systems. Since the advent of high-throughput measurement technologies in biology in the late 90s, reconstructing the structure of such networks has been a central computational problem in systems biology. While the problem is certainly not solved in its entirety, considerable progress has been made in the last two decades, with mature tools now available. This chapter aims to provide an introduction to the basic...

Empirical studies of graphs have contributed enormously to our understanding of complex systems. Known today as network science, what was originally a theoretical study of graphs has grown into a more scientific exploration of communities spanning the physical, biological, and social. However, as the quantity and types of networks have grown so has their heterogeneity in quality and specificity. This has hampered efforts to develop general network theory capable of inferring ...

Background: Networks in different domains are characterized by similar global characteristics while differing in local structures. To further extend this concept, we investigated network regularities on a fine scale in order to examine the functional impact of recurring motifs in signed oriented biological networks. In this work we generalize to signaling net works some considerations made on feedback and feed forward loops and extend them by adding a close scrutiny of Linear...

Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo \emph{et al}, that provided motifs as a way to uncover the basic building blocks of most networks. In Bioinformatics, motifs have been mainly applied in the field of gene regulation networks. This paper proposes new algorithms to exactly count isomorphic pattern motifs of sizes 3, 4 and 5 in directed graphs. Let $G(V,E)$ be a directed graph with $m=|E|$. We describe an $O({m\s...

RNA 3D motifs are recurrent substructures, modelled as networks of base pair interactions, which are crucial for understanding structure-function relationships. The task of automatically identifying such motifs is computationally hard, and remains a key challenge in the field of RNA structural biology and network analysis. State of the art methods solve special cases of the motif problem by constraining the structural variability in occurrences of a motif, and narrowing the s...

Aligning protein-protein interaction (PPI) networks of different species has drawn a considerable interest recently. This problem is important to investigate evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. It is however a difficult combinatorial problem, for which only heuristic methods have been proposed so far. We reformulate the PPI alignment as a...

Understanding why some cellular components are conserved across species, while others evolve rapidly is a key question of modern biology. Here we demonstrate that in S. cerevisiae proteins organized in cohesive patterns of interactions are conserved to a significantly higher degree than those that do not participate in such motifs. We find that the conservation of proteins within distinct topological motifs correlates with the motif's inter-connectedness and function and also...