English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Computing Paths and Cycles in Biological Interaction Graphs

Klamt, S., & von Kamp, A. (2009). Computing Paths and Cycles in Biological Interaction Graphs. BMC Bioinformatics, 10, 181. doi:10.1186/1471-2105-10-181.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-9371-C Version Permalink: http://hdl.handle.net/11858/00-001M-0000-002C-8B4B-A
Genre: Journal Article

Files

show Files
hide Files
:
432264_bmc_bioinfo_2009.pdf (Publisher version), 252KB
Name:
432264_bmc_bioinfo_2009.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Klamt, S.1, Author              
von Kamp, A.1, Author              
Affiliations:
1Analysis and Redesign of Biological Networks, Max Planck Institute for Dynamics of Complex Technical Systems, Max Planck Society, ou_1738139              

Content

show
hide
Free keywords: -
 Abstract: Background Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments. Results We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results w as possible) this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops. Conclusions The calculation of shortest positive/negative paths and cycles in interaction graphs is an important method for network analysis in Systems Biology. This contribution draws the attention of the community to this important computational problem and provides a number of new algorithms, partially specifically tailored for biological interaction graphs. All algorithms have been implemented in the CellNetAnalyzer framework which can be downloaded for academic use at www.mpi-magdeburg.mpg.de/projects/cna/cna.html. © 2009 Klamt and von Kamp , licensee BioMed Central Ltd. [accessed June 29, 2009]

Details

show
hide
Language(s): eng - English
 Dates: 2009
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: Peer
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: BMC Bioinformatics
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 10 Sequence Number: - Start / End Page: 181 Identifier: -