Determining the distance to monotonicity of a biological network: a graph-theoretical approach
Determining the distance to monotonicity of a biological network: a graph-theoretical approach
- Author(s): G. Iacono ; F. Ramezani ; N. Soranzo ; C. Altafini
- DOI: 10.1049/iet-syb.2009.0040
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): G. Iacono 1 ; F. Ramezani 2 ; N. Soranzo 1 ; C. Altafini 1
-
-
View affiliations
-
Affiliations:
1: SISSA International School for Advanced Studies, Trieste, Italy
2: Max-Planck-Institut für Informatik, Saarbrücken, Germany
-
Affiliations:
1: SISSA International School for Advanced Studies, Trieste, Italy
- Source:
Volume 4, Issue 3,
May 2010,
p.
223 – 235
DOI: 10.1049/iet-syb.2009.0040 , Print ISSN 1751-8849, Online ISSN 1751-8857
The authors use ideas from graph theory in order to determine how distant is a given biological network from being monotone. On the signed graph representing the system, the minimal number of sign inconsistencies (i.e. the distance to monotonicity) is shown to be equal to the minimal number of fundamental cycles having a negative sign. Suitable operations aiming at computing such a number are also proposed and shown to outperform all algorithms that are so far existing for this task. [Includes supplementary material]
Inspec keywords: complex networks; biology computing; graph theory
Other keywords:
Subjects: Other topics in statistical physics and thermodynamics; General, theoretical, and mathematical biophysics; Algebra, set theory, and graph theory; Biology and medical computing; Combinatorial mathematics
References
-
-
1)
- T. Zaslavsky . Signed graphs. Discrete Appl. Math. , 1 , 47 - 74
-
2)
- E.D. Sontag . Monotone and near-monotone biochemical networks. Syst. Synth. Biol. , 59 - 87
-
3)
- G. Toulouse . Theory of the frustration effect in spin glasses: I. Commun. Phys.
-
4)
- M. Hirsch , H.L. Smith , A. Canada , P. Drabek , A. Fonda . (2006) Monotone dynamical systems,, Handbook of differential equations, ordinary differential equations.
-
5)
- N. Deo . (1974) Graph theory with applications to engineering and computer science.
-
6)
- B. DasGupta , G.A. Enciso , E. Sontag , Y. Zhang . Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. Biosystems , 1 , 161 - 178
-
7)
- A. Bang-Jensen , G. Gutin . When the greedy algorithm fails. Discrete Optim. , 121 - 127
-
8)
- S.S. Shen-Orr , R. Milo , S. Mangan , U. Alon . Network motifs in the transcriptional regulation network of Escherichia coli. Nat. Genet. , 1 , 64 - 68
-
9)
- R. Prim . Shortest connection networks and some generalizations. Bell Syst. Tech. J. , 1389 - 1401
-
10)
- P. Solé , T. Zaslavsky . A coding approach to signed graphs. SIAM J. Discrete Math. , 4 , 544 - 553
-
11)
- H.L. Smith . Systems of ordinary differential equations which generate an order preserving flow. A survey of results. SIAM Rev. , 1 , 87 - 113
-
12)
- E. Sontag , A. Veliz-Cuba , R. Laubenbacher , A.S. Jarrah . The effect of negative feedback loops on the dynamics of boolean networks. Biophys. J. , 2 , 518 - 526
-
13)
- T. Zaslavsky . A mathematical bibliography of signed and gain graphs and allied areas. Electr. J. Comb.
-
14)
- U. Alon . Network motifs: theory and experimental approaches. Nat. Rev. Genet. , 6 , 450 - 461
-
15)
- F. Hüffner , N. Betzler , R. Niedermeier . Separator-based data reduction for signed graph balancing’. J. Comb. Optim.
-
16)
- G. Kirchhoff . Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen Verteilung galvanischer strome gefuhrt wird. Ann. Phys. Chem. , 497 - 508
-
17)
- A. Ma'ayan , A. Lipshtat , R. Iyengar , E. Sontag . Proximity of intracellular regulatory networks to monotone. IET Syst. Biol. , 103 - 112
-
18)
- A. Caprara , A. Panconesi , R. Rizzi . Packing cycles in undirected graphs. J. Algorithms , 1 , 239 - 256
-
19)
- K. Oda , T. Kimura , Y. Matsuoka , A. Funahashi , M. Muramatsu , H. Kitano . Molecular inter-action map of a macrophage. AfCS Reports , 14
-
20)
- H. Salgado , S. Gama-Castro , M. Peralta-Gil . RegulonDB (version 5.0): Escherichia coli K-12 transcriptional regulatory network, operon organization, and growth conditions. Nucl. Acids Res. , D394 - D397
-
21)
- M.X. Goemans , D.P. Williamson . Improved approximation algorithms for maximum cut and satisfiability problems using semi-definite programming. J. ACM , 6 , 1115 - 1145
-
22)
- R. Milo , S. Shen-Orr , S. Itzkovitz , N. Kashtan , D. Chklovskii , U. Alon . Network motifs: simple building blocks of complex networks. Science , 5594 , 824 - 827
-
23)
- K. Oda , Y. Matsuoka , A. Funahashi , H. Kitano . A comprehensive pathway map of epidermal growth factor receptor signaling. Mol. Syst. Biol.
-
1)
Related content
