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

被引:40
|
作者
Iacono, G. [1 ]
Ramezani, F. [2 ]
Soranzo, N. [1 ]
Altafini, C. [1 ]
机构
[1] SISSA, Int Sch Adv Studies, I-34014 Trieste, Italy
[2] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
关键词
MOTIFS;
D O I
10.1049/iet-syb.2009.0040
中图分类号
Q2 [细胞生物学];
学科分类号
071009 ; 090102 ;
摘要
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.
引用
收藏
页码:223 / U76
页数:16
相关论文
共 50 条