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.

Determining the distance to monotonicity of a biological network: a graph-theoretical approach

Altafini, Claudio
2010-01-01

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.
2010
4
223
235
G., Iacono; F., Ramezani; N., Soranzo; Altafini, Claudio
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11767/30144
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 41
social impact