Detecting conserved interaction patterns in biological networks.

Detecting conserved interaction patterns in biological networks. Research Abstract Details 

Research Abstract Table of Contents

Jump to the:

Detecting conserved interaction patterns in biological networks. Abstract Text:

Mehmet ,Yohan Kim,Shankar Subramaniam,Wojciech Szpankowski,Ananth Grama,

Molecular interaction data plays an important role in understanding biological processes at a modular level by providing a framework for understanding cellular organization, functional hierarchy, and evolutionary conservation. As the quality and quantity of network and interaction data increases rapidly, the problem of effectively analyzing this data becomes significant. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm, MULE, for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique based on ortholog contraction, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable and scalable to large numbers of networks. We show, experimentally, that our algorithm can extract frequently occurring patterns in metabolic pathways and protein interaction networks from the KEGG, DIP, and BIND databases within seconds. When compared to existing approaches, our graph simplification technique can be viewed either as a pruning heuristic, or a closely related, but computationally simpler task. When used as a pruning heuristic, we show that our technique reduces effective graph sizes significantly, accelerating existing techniques by several orders of magnitude! Indeed, for most of the test cases, existing techniques could not even be applied without our pruning step. When used as a stand-alone analysis technique, MULE is shown to convey significant biological insights at near-interactive rates. The software, sample input graphs, and detailed results for comprehensive analysis of nine eukaryotic PPI networks are available at www.cs.purdue.edu/homes/koyuturk/mule.

Detecting conserved interaction patterns in biological networks. Publishing Authors By Initials

M ,Y Kim,S Subramaniam,W Szpankowski,A Grama,

For similar biochemical phenomena, metabolism, and nutrition: biochemical phenomena: sequence homology research abstracts see: biochemical phenomena, metabolism, and nutrition: biochemical phenomena: sequence homology research

PUBMED ID PMID:

MEDLINE DATE:

Detecting conserved interaction patterns in biological networks. Journal Published:

PUBLICATION TYPE: Research Support, U.S. Gov't,

Journal: Journal of computational biology : a journal of co

VOLUME: 13

Page Numbers: 1299-322

Journal Abbreviation: J. Comput. Biol.

ISSN: 1066-5277

DAY: 3

MONTH: Sep

YEAR: 2006

Detecting conserved interaction patterns in biological networks. Information

Number of References:

LANGUAGE: eng

NlmUniqueID: 9433358

Detecting conserved interaction patterns in biological networks. Keywords Mesh Terms:

KEYWORDS: Sequence Homology

MESH TERMS: methods

Chemical & Substance for Abstract: Detecting conserved interaction patterns in biological networks. Information

Substance Name:

Registry Number:

Grant and Affiliation Information for Detecting conserved interaction patterns in biological networks.

AFFILIATION: Department of Computer Sciences, Purdue University, West Lafayette, Indiana 47906, USA. koyuturk@cs.purdue.edu

Country: United States

AGENCY: United States NIGMS

GRANT: R01 GM068959-01

ACRONYM: GM

MEDLINETA: J Comput Biol

REFSOURCE:

DATABASENAME:

ACCESSION NUMBER:

Number Hits: 0

Detecting conserved interaction patterns in biological networks Related Publications

• 2D-pattern matching image and video compression: theory, algorithms, and experiments.
• Annotating pathways in interaction networks.
• Assessing significance of connectivity and conservation in protein interaction networks.
• Detecting conserved interaction patterns in biological networks.
• Functional coherence in domain interaction networks.