Determining the distance to monotonicity of a biological network: a graph-theoretical approach
- 13 May 2010
- journal article
- research article
- Published by Institution of Engineering and Technology (IET) in IET Systems Biology
- Vol. 4 (3) , 223-235
Abstract
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]Keywords
This publication has 9 references indexed in Scilit:
- The Effect of Negative Feedback Loops on the Dynamics of Boolean NetworksBiophysical Journal, 2008
- Chapter 4 Monotone Dynamical Systems2006
- Packing cycles in undirected graphsJournal of Algorithms, 2003
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A Coding Approach to Signed GraphsSIAM Journal on Discrete Mathematics, 1994
- Systems of Ordinary Differential Equations Which Generate an Order Preserving Flow. A Survey of ResultsSIAM Review, 1988
- Signed graphsDiscrete Applied Mathematics, 1982
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957