Local graph alignment and motif search in biological networks
Authors:
- 24 September 2004
- journal article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 101 (41) , 14689-14694
Abstract
Interaction networks are of central importance in postgenomic 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 article, 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 Escherichia coli .Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Subgraphs in random networksPhysical Review E, 2003
- Correlated Random NetworksPhysical Review Letters, 2002
- Assortative Mixing in NetworksPhysical Review Letters, 2002
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- Network motifs in the transcriptional regulation network of Escherichia coliNature Genetics, 2002
- Random graphs with arbitrary degree distributions and their applicationsPhysical Review E, 2001
- A new algorithm for error-tolerant subgraph isomorphism detectionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1998
- Superparamagnetic Clustering of DataPhysical Review Letters, 1996
- Evolutionary trees from DNA sequences: A maximum likelihood approachJournal of Molecular Evolution, 1981
- An Algorithm for Subgraph IsomorphismJournal of the ACM, 1976