Local graph alignment and motif search in biological networks

Abstract

Interaction networks are of central importance in post-genomic molecular biology, with increasing amounts of data becoming available by high-throughput methods. Examples are gene regulatory networks or protein interaction maps. The main challenge in the analysis of these data is to read off biological functions from the topology of the network. Topological motifs, i.e., patterns occurring repeatedly at different positions in the network have recently been identified as basic modules of molecular information processing. In this paper, we discuss motifs derived from families of mutually similar but not necessarily identical patterns. We establish a statistical model for the occurrence of such motifs, from which we derive a scoring function for their statistical significance. Based on this scoring function, we develop a search algorithm for topological motifs called graph alignment, a procedure with some analogies to sequence alignment. The algorithm is applied to the gene regulation network of E. coli.

published version

References in corpus (5)

• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Specificity and stability in topology of protein networks
• Subgraphs in random networks
• Correlated random networks

Cited by in corpus (18)

• Biological network comparison using graphlet degree distribution
• Maximum likelihood: extracting unbiased information from complex networks
• Cross-species analysis of biological networks by Bayesian alignment
• Coarse-Graining and Self-Dissimilarity of Complex Networks
• Homogeneous complex networks
• Probability Models for Degree Distributions of Protein Interaction Networks
• Aligning graphs and finding substructures by a cavity approach
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Functional alignment of regulatory networks: A study of temperate phages
• Network motifs come in sets: correlations in the randomization process
• Fair Evaluation of Global Network Aligners
• From homogeneous to heterogeneous network alignment via colored graphlets
• MAGNA: Maximizing Accuracy in Global Network Alignment
• GREAT: GRaphlet Edge-based network AlignmenT
• Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
• HetNetAligner: Design and Implementation of an algorithm for heterogeneous network alignment on Apache Spark
• An interdisciplinary survey of network similarity methods
• Parameterized Algorithms for Clustering PPI Networks