BACKGROUND
it is well known that bio-molecular networks can keep their regulatory functions robust against various types of external or internal perturbations.
for instance, the fate decision mechanism in a bacteriophage life cycle  <cit> , the chemotaxis process in escherichia coli  <cit> , and segmental polarization in drosophila melanogaster  <cit>  were shown to be robust against noisy environments.
it is more interesting that the dynamics of a biological network can be highly related to its structural characteristics  <cit> .
in particular, many recent studies have shown that a feedback loop , a circular chain of interactions, can play an important role in controlling the robustness or susceptibility of networks  <cit> .
for instance, the negative fbl between mdm <dig> and p <dig> maintains an optimal level of p <dig> and creates appropriate dynamics of p <dig> expression level changes for a given level of dna damage  <cit> .
the xenopus cell cycle is also robustly controlled against a certain level of perturbation with the help of several fbls  <cit> .
it was shown that a high proportion of coherently coupled fbls can enhance the robustness of a network against state perturbations  <cit> .
the number of fbls involved at a node was also found to be positively correlated with the node’s functional importance  <cit> .
those simulation studies, however, cannot fully explain how the fbls influence the network robustness.
hence, there is a pressing need to more rigorously analyze the relationship between fbl structures and network dynamics.
to measure network robustness, i herein use a synchronous boolean network model  <cit>  in which a node state is represented by a boolean value, and the states of all nodes are synchronously updated at every discrete time step.
every network state moves to another state, and a series of consecutive transitions are represented by a network state trajectory that eventually converges to a fixed-point or cyclic attractor.
the attractor can describe various dynamic behaviors in a biological system, such as multi-stability and oscillations.
if a node state is perturbed, the trajectory might converge to a different attractor.
therefore, a network is considered robust if the attractor does not change against a perturbation.
some tools have been proposed to quantify the network robustness by simulating the state transitions after randomly initializing the node states .
they have a limitation in network size for analysis, though, due to the exponential complexity of attractor computation.
therefore, it is a critical issue to find analytic results that can identify trivial parts that do not require further computation of state transitions.
in this paper, i focus on the effects of an fbl on boolean converging dynamics.
a state of a node is propagated to other nodes along a path in a chain of consecutive interactions.
therefore, the state cannot be fed back to the original node if it is not involved in an fbl.
in other words, the current state of a node will eventually disappear unless a downstream path constructs an fbl.
from that idea, i developed an fbl-based notion to classify nodes in a network.
in particular, i defined two sets of nodes, no-fbl-in-upstream  and no-fbl-in-downstream , according to whether the upstream and downstream paths, respectively, involve any fbls and proved two theorems regarding nfu and nfd nodes.
one is that every nfu node is always frozen irrespective of the initial states of other nodes.
this implies that the converging values of all nfu nodes are eventually fixed to a value determined by the upstream source nodes.
it also means that a network is likely to be susceptible to a perturbation subject to the source nodes.
the other is that a network is robust against an arbitrary perturbation subject to a non-source nfd node.
in other words, a network state eventually converges to the same attractor despite a state perturbation subject to a non-source nfd node.
inspired by those results, i further developed a perturbation-sustainable probability which indicates how likely it is that a perturbation effect will be sustained through a network state trajectory and showed that it can adequately identify functionally important genes, such as essential, disease-associated, and drug-target genes, in large human signaling networks.
taken together, all of these results will promote understanding of the effects of fbls on boolean converging dynamics and reduce the computational costs of state transition-based simulation tools.
methods
structural classification of nodes in a network
in this study, a biological network is represented by a directed graph g where v = {v <dig>  v <dig>  ⋯, vn} is a set of nodes and e = {e <dig>  e <dig>  ⋯, ea} is a set of directed edges ; an edge e ∈ e is an ordered pair of nodes  where vi, vj ∈ v. i use some notions from graph theory, including fbl and upstream/downstream paths, to represent the biological networks as follows.
definition
a node u is an input node of v if there exists an interaction from u to v  ∈ e).
in addition, in-degree of v means the number of input nodes of v.
definition
a node v is a source node if in-degree of v is zero.
it is assumed that the state of a source node is fixed to its initial value over all the time.
definition
given a network g, a path p of a length l is represented by a sequence of ordered nodes u1u2 ⋯ ul +  <dig> with interactions from ui to ui +  <dig>  ∈ e for∀ i ∈ { <dig>   <dig>  ⋯, l}) with no repeated nodes except u <dig> and ul +  <dig>  in addition, p is called a feedback loop  if u1 = ul +  <dig>
definition
given a network g, an upstream  path p = u1u2 ⋯ ul +  <dig> of a node v ∈ v is a path in which the last  node ul +  <dig>  is v. note that if p is a feedback loop, then it is both an upstream and downstream path of v. in addition, p = u1u2 ⋯ ul +  <dig> is a maximal upstream  path if there is no longer path such as wu1u2 ⋯ ul +  <dig>  for some w ∈ v.
based on those terms, i define no-fbl-in-upstream and no-fbl-in-downstream nodes as follows:
definition
given a network g, a node v is called a no-fbl-in-upstream   node if there is no upstream  path p = u1u2 ⋯ ulv  such that for some i ∈ { <dig>   <dig>  ⋯, l}, ui is involved in any feedback loop.
figure  <dig> shows an example of nfu and nfd nodes in a network.
this network contains five nfu nodes v <dig>  v <dig>  v <dig>  v <dig>  and v <dig> and four nfd nodes v <dig>  v <dig>  v <dig> and v <dig>  note that v <dig>  v <dig> and v <dig> are both nfu and nfd nodes.
on the other hand, it also contains five nodes that are neither nfu nor nfd nodes because an fbl is both upstream and downstream of each of them.
in particular, note that v <dig> is not directly involved in an fbl.
in this paper, i will show that the nfu and nfd nodes can induce interesting dynamic properties in a perturbation analysis.fig.
<dig> an example of nfu and nfd nodes in a network.
every node is classified into one of four categories: “nfu but not-nfd”, “nfd but not-nfu”, “nfu and nfd”, and “neither nfu nor nfd”
a perturbation analysis in a boolean network model
to define the robustness or sensitivity of a network, i use a synchronous boolean network model used in previous studies  <cit> .
in a boolean network g, each vi ∈ v has a value of  <dig>  or  <dig>  that represent the possible states of the corresponding elements.
for example, the values  <dig> and  <dig> represent the “turn-on” and “turn-off” states of a gene, respectively.
a directed interaction  can represent a positive  or negative  relationship from vi to vj.
the value of each variable vi at time t +  <dig> is determined by the values of ki other variables vi <dig> vi <dig> ⋯,viki with an interaction to vi at time t by a boolean update function fi:01ki→ <dig> where fi is a constant value if vi is a source node.
all the boolean variables are synchronously updated by a set of update functions f = {f <dig>  f <dig>  ⋯, fn}, and each update rule can be written as vit+1=fivi1t,vi2t,⋯,vikit.
many studies have been performed to elucidate the dynamic behaviors of biological networks.
in particular, i address robustness against perturbations in terms of boolean dynamics.
in a boolean network g , a network state at time t is represented by an ordered list v =  ∈ { <dig>  1}n. then, for a subset u = {u <dig>  u <dig>  ⋯, um} ⊆ v, a subset state of u at time t denoted by vu =  ∈ { <dig>  1}m is an ordered list consisting of values u <dig> through um at time t. a state trajectory of v starts from an initial state and eventually converges to either a fixed-point or limit-cycle attractor.
these attractors can represent diverse biological network behaviors, such as multi-stability and oscillation .
this notion of an attractor introduces robustness in terms of the boolean network dynamics as follows.
if a network sustains an attractor against a perturbation, it is called robust against the perturbation.
this concept has been widely used .
here, i consider an initial-state perturbation.
given an initial state v =  at t =  <dig>  an initial-state perturbation subject to node vx ∈ v represents a situation in which v is mutated to v' = , i.e., the corresponding initial value is switched to vx¯ <dig> ).
an initial-state perturbation represents the abnormal  status of a protein or gene caused by a mutation.
the attractors to which v and v'  will converge can be compared to each other.
the network is called robust or sensitive against the perturbation according to whether the attractors are the same as or different from each other, respectively.
based on this concept, i define some terms more rigorously with respect to the boolean dynamics, as follows.
definition
the sequence of states to which v eventually converges is called the attractor induced from v, which is denoted by an ordered list of network states ζ =  where v = v for ∀ t ≥ τ , and v ≠ v for ∀ i ≠ j ∈ {τ, τ +  <dig>  …, τ + p − 1}.
in addition, for a subset u ⊆ v, ζ =  represents the states sequence of u in the attractor induced from v.
definition
for u ⊆ v, ζ is frozen if there exists a time step τ such that v = v for ∀ v ∈ u and ∀ t ≥.
definition
given two attractors with a same length, ζ =  and ζ = , they are equivalent to each other if there exists a time step offset t ≥  <dig> such that v = v' mod p) for ∀ i ∈ { <dig>   <dig>  …, p − 1}.
definition
consider an arbitrary initial state v =  and its perturbed state at vx ∈ v, v' = .
the boolean network is called robust against the perturbation subject to vx if ζ is equivalent to ζ. otherwise, it is called sensitive or susceptible.
datasets of signaling networks and functionally important genes
in this study, i derive an estimated probability with which a perturbation effect is sustained in a network.
to show the usefulness of it, i used two large-scale human signaling networks.
one is the signaling network of  <dig> genes and  <dig> interactions constructed in a previous study  <cit>  by integrating all the human signaling pathways in the kegg  database  <cit>  .
the other signaling network consists of  <dig> genes and  <dig>  interactions  downloaded from http://www.bri.nrc.ca/wang  <cit>  .
in this work, i call them the kegg and wang networks, respectively.
in addition, i considered essential, disease, and drug-targeted genes to represent functionally important genes.
by using the deg  database  <cit> , i found  <dig> and  <dig> essential genes included in the kegg and wang networks, respectively.
i also found  <dig> and  <dig> disease genes in the kegg and wang networks, respectively, using the omim  database  <cit> .
finally, i identified  <dig> and  <dig> drug target genes in the kegg and wang networks, respectively, using the drugbank database  <cit> .
RESULTS
dynamic properties of nfu nodes
in this section, i show that nfu nodes are eventually frozen in boolean network dynamics.
a boolean network g with a set of update functions f is given.
lemma 1
given an initial state v and a node vk ∈ v, let u = {u <dig>  u <dig>  ⋯, um} be the set of input nodes of vk.
if ζ is frozen, then ζvvk is also frozen.
proof
for ∀ ui ∈ u, there exists a time step τi such that ui = ui for ∀ t ≥ τi since ζvui is frozen.
let τ=maxi∈12…mτi.
then, vk = fk, ⋯, um) = fk, ⋯, um) = vk for ∀ t ≥ τ. thus, ζvvk is also frozen ■
lemma 2
an initial state v and a node v ∈ v are given.
if every maximal upstream path of v includes at least one node u where ζ is frozen, then ζ is also frozen.
proof
let p <dig>  p <dig>  ⋯, pm be the list of maximal upstream paths of v, and let ui ∈ pi  be the node where ζvui is frozen.
then consider a sub-path pi' of pi starting from ui and ending at v. define w = {w ∈ v|w ∈ pi' for some i} and let l be the length of the longest path from w to v. assuming that l = maxw ∈ wl, w can be divided into l +  <dig> disjoint subsets w <dig>  w <dig>  ⋯ and wl where wk = {w ∈ w|l = k}.
then ζ for ∀ w ∈ w is frozen by mathematical induction with respect to l, as follows.
when k = l, it is obvious that ζ of every w ∈ wl is frozen because w ∈ {u <dig>  u <dig>  …, um}.
assume that ζ of every w ∈ wk +  <dig> is frozen and consider an arbitrary element w' ∈ wk.
then every input node of w' is an element of wk +  <dig>  by lemma  <dig>  ζvw' is frozen.
thus, ζ of every w ∈ wk is also frozen.
by mathematical induction, ζ of every w ∈ w is frozen.
therefore, ζ is also frozen because v ∈ w■
lemma  <dig> provides a sufficient condition for the frozenness of a node.
this can be extended to the case of nfu nodes as follows.
theorem 1
an initial statev is given.
if v ∈ v is an nfu node, then ζ is frozen.
proof
by the definition of nfu nodes, every maximal upstream of v starts with a source node u whose ζ is frozen.
by lemma  <dig>  ζ is also frozen ■
this theorem implies that the states of nfu nodes are dependent on the states of source nodes, and this might make the network tend to be susceptible to perturbations subject to source nodes.
corollary
an initial state v is given.
if there is no fbl then ζ is frozen.
proof
since there are no fbls, every v ∈ v is an nfu node.
by theorem  <dig>  it follows that ζ is always frozen irrespective of the initial states ■
theorem  <dig> and its corollary explain the effect of fbls on the frozenness of the converging state sequences.
more specifically, every nfu node is frozen to a value determined by the set of source nodes included in its upstream paths.
i also note that this result is strongly related to previous studies based on synchronous or asynchronous boolean network models .
in particular, the corollary corresponds to a previous result having stated that the boolean dynamics converges to a unique fixed point in an acyclic boolean network  <cit> .
it is also relevant to the previous results showed that limit-cycle attractors can be induced by negative feedback loops  <cit> .
in addition, theorem  <dig> can reduce the computation of attractors in a large scale network by easily obtaining the converging values of the nfu nodes.
dynamic properties of nfd nodes
in the lemmas and a theorem of this section, i investigate the effect of fbls on robustness.
i consider an arbitrary initial state v =  and a perturbed state at vx ∈ v from v, v' =  in the following lemmas  <dig> and  <dig>  and theorem  <dig>  i denote the value of a node w ∈ v at time t in the trajectories starting from v and v' by v{w} and v{w}', respectively.
lemma 3
let v be an initial state, v' a perturbed state at vx ∈ v from v, and w ∈ v an arbitrary node.
if there is no path from vx to w then v{w} = v{w}' for ∀ t ≥  <dig>
proof
the state value of node w is updated irrespective of that of node vx because there is no path from vx to w. thus, the lemma holds ■
lemma 4
let v be an initial state, v' a perturbed state at vx ∈ v from v, w ∈ v an arbitrary node.
let y = {y ∈ v|y is included in some path from vx to w} and l the length of a longest path from vx to y ∈ y. if vx is a non-source node and no node in y is involved with any fbl, then v{w} = v{w}' for ∀ t ≥ l +  <dig>
proof
by mathematical induction with respect to l, i show that for every y ∈ y, v{y} = v{y}' for ∀ t ≥ l +  <dig>  as follows.
when l =  <dig>  it is obvious that y = vx.
then vvxt=vvx't for ∀ t ≥  <dig> because vx is a non-source node and involved with no fbl.
to prove the inductive step, i assume that the property holds for l ≤ k −  <dig>  consider an arbitrary y ∈ y such that l = k and let u be the set of input nodes of y. for every u ∈ u, there are two cases to consider: either u ∈ y or u ∉ y. in case of u ∈ y, it is obvious that l ≤ k −  <dig> by the definition of l. by the induction hypothesis, v{u} = v{u}' for ∀ t ≥ l +  <dig>  in case of u ∉ y, it means that there is no path from vx to u. then v{u} = v{u}' for ∀ t ≥  <dig> by lemma  <dig>  from both cases, for ∀ u ∈ u, v{u} = v{u}' for ∀ t ≥ k. then v{y} = v{y}' for ∀ t ≥ k +  <dig>  thereby showing the property holds when l = k. since w ∈ y, the lemma holds ■
theorem 2
letv be an initial state, v' a perturbed state at vx ∈ v fromv, and w ∈ v an arbitrary node.
if vxis an nfd and non-source node, then the network is robust against a state perturbation subject to vx.
proof
i show that there exists a constant time t such that v{w} = v{w}' for ∀ t ≥ t in the following three cases.
case that = vx : because w is an nfd and non-source node, v{w} = v{w}' for ∀ t ≥  <dig>   case that w is not connected by any path from vx : by lemma  <dig>  v{w} = v{w}' for ∀ t ≥  <dig>   case that w is connected by at least one path from vx : let y = {y ∈ v|y is included in some path from vx to w} and l be a longest length of those paths, respectively.
because vx is an nfd node, no node included in y is involved with any fbl.
by lemma  <dig>  v{w} = v{w}' for ∀ t ≥ l +  <dig>  by ,, and , there exists a constant time t such that v{w} = v{w}' for ∀ t ≥ t and ∀ w ∈ v. accordingly, the attractors starting at v and v' are equivalent to each other.
therefore, the network is robust against the state perturbation subject to vx■
theorem  <dig> indicates that biological networks might be robust against perturbations subject to nfd nodes.
to support this result, i compared nfd and non-nfd gene groups with respect to the proportions of essential genes, disease genes, and drug targets in two human signaling networks, the kegg and wang networks .
as shown in fig.
<dig>  the proportions of essential genes, disease genes, and drug targets among nfd genes were significantly smaller than those among non-nfd genes in both networks .
i assume that essential genes, disease genes, and drug targets are likely to be susceptible to mutations, perturbations, or other external changes.
in this regard, the relatively low proportions of essential genes, disease genes, and drug targets in the nfd group in the large-scale signaling networks support theorem  <dig>  in addition, i further examined the proportions of essential genes, disease genes, and drug targets in nfd group in random networks to examine if the observed result is specific to the signaling networks .
i created each set of  <dig> random networks by rewiring the interactions of the kegg ) and wang ) networks so that the in-degree and the out-degree of the nodes are conserved, and observed that there is little difference between the nfd and non-nfd groups with respect to the proportions of essential genes, disease genes, and drug targets.
this implies that the functionally important genes in the real signaling networks are not randomly distributed in terms of nfd classification.fig.
<dig> comparison between groups of nfd and non-nfd genes in signaling networks.
a result in kegg network with  <dig> nfd genes and  <dig> non-nfd genes.
the proportions of essential genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of disease genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of drug-targets in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
b result in wang network with  <dig> nfd genes and  <dig> non-nfd genes.
the proportions of essential genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of disease genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of drug-targets in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
in both networks, all the proportions for the nfd group were significantly smaller than those for the non-nfd group
estimation of sustainability of a perturbation effect
in the previous section, theorem  <dig> showed that a network state is robust against a perturbation as long as the perturbation effect is not sustained by downstream fbls.
in other words, the existence of downstream fbls is a necessary condition to make a network susceptible to a perturbation.
inspired by that result, i have derived an estimated probability that a perturbation effect will be sustained.
given a node vx ∈ v subject to a perturbation, lemma  <dig> shows that only downstream paths of vx need to be considered, and lemma  <dig> shows that only those involved with an fbl need to be considered.
i first estimate the probability with which a perturbation subject to vx is sustained through a single path involved with a fbl.
figure  <dig> shows an example of a downstream path p = vxu1u2 ⋯ ul of vx which includes an fbl, and i consider v and v' which are an initial state and a perturbed state at vx ∈ v from v, respectively.
it is said that the effect of a perturbation starting at vx at the initial time is sustained through propagations in a sequence of u <dig>  u <dig>  ⋯, ul if vuii≠vui'i for ∀ i ∈ { <dig>  ⋯, l}.
herein, it is assumed that a probability with which ui is differently updated by the flipped value of ui −  <dig>  denoted by prvuii≠vui'i|vui−1i−1≠vui−1'i− <dig>  is the inverse of the in-degree of ui because of the following reason .
let w=w <dig> w <dig> ⋯,wdi be the set of input nodes of ui where di is the in-degree of ui.
by assuming that the input nodes have an even degree of influence on updating ui, i.e., pry|x1=⋯=pry|xdi where y and xk denote two events vuii≠vui'i and vwki−1≠vwk'i− <dig>  respectively.
it is also assumed that ui is always differently updated given a perturbation has occurred at one of the input nodes.
accordingly, pry|uk∈1⋯dixk=pry|x1+⋯+pry|xdi= <dig>  and thus pr = 1/di .
note that ui − 1 ∈ w because ui −  <dig> is one of the input nodes of ui.
with this result, the probability with which the perturbation subject to vx is sustained through a path p can be derived as follows:fig.
<dig> an example of a downstream path with a feedback loop.
a node v
x is subject to a state perturbation, and the perturbation effect can be sustained at u
<dig> with a probability of the inverse of the in-degree of u
<dig>  this propagation is continued along the path p = v
x
u
1
u
2 ⋯ u
l involved with a fbl
<dig> prp=∏i=1l1/di,ifanfblisinvolved, <dig> otherwise let p <dig>  p <dig>  ⋯, pm be the set of all downstream paths of vx.
then i define the perturbation-sustainable probability γ, the probability that the perturbation subject to vx will be sustained through at least one fbl, as follows:  <dig> γvx=maxi∈1⋯mprpi.
if a gene with a relatively high γ value is subject to a perturbation, the network is likely to induce an abnormal dynamics due to the well conserved perturbation effect.
in this regard, the perturbation-sustainable probability can indicate how much a gene is functionally or dynamically important in a signaling network.
to show the usefulness of this probability, i examined the relationship between γ and the proportions of putatively susceptible genes in human signaling networks .
given a threshold value β, the proportions of essential genes, disease genes, and drug targets among the set of genes such that {vx|γ ≥ β} are plotted against the threshold value in the kegg  and wang  networks.
as shown in the figure, the genes with a high perturbation-sustainable probability are more likely to be essential genes, disease genes, and drug targets in both networks.
this implies that the perturbation-sustainable probability can adequately identify the functionally important genes in human signaling networks.
in addition, it is notable that the relation of the perturbation-sustainable probability to the functionally important genes was not observed in the random networks created by rewiring the interactions of the signaling networks .
as in the results of additional file 2: figure s <dig>  this also implies that the functionally important genes in the real signaling networks are not randomly distributed in terms of nfd classification.
taken together, it is interesting that such a simple topological measurement of genes based only on fbls can efficiently predict the functionally important genes in human signaling networks.fig.
<dig> changes in proportions of functionally important genes over the threshold value of the perturbation-sustainable probability.
given a threshold value β, the y-axis values indicate the proportions of essential genes, disease genes, and drug targets over the set of candidate genes whose perturbation-sustainable probability is larger than or equal to β. the larger the value of β, the smaller the number of candidate genes is.
a results of essential genes, disease genes, and drug targets in the kegg network.
for a reliable comparison, the maximal β was set to  <dig>  which generates  <dig> candidate genes.
b results of essential genes, disease genes, and drug targets in the wang network.
the maximal β was set to  <dig> , which results in  <dig> candidate genes
discussion
in this study, i did not address the dynamics of non-nfu and non-nfd nodes, i.e., nodes that are involved in fbls, and the analysis of their dynamics remains an open problem.
in addition, the update-rule perturbation, another well-known type of perturbations, was not considered in this study because it influences the network robustness in a different way than the initial-state perturbation by changing the state transition diagram.
therefore, a future study should include analyses of genes that are neither nfu nor nfd nodes, and analysis of robustness against update-rule perturbations.
finally, it should be noted that the analyses in this study might not be effective for other types of biological networks than the signaling networks.
for example, nfu/nfd classification was not meaningful in the large-scale gene regulatory networks  <cit>  because most genes were classified to nfd nodes.
this implies that another method to further classify nfd nodes is required for analysis of those networks.
CONCLUSIONS
it is well known that biological networks can keep their regulatory functions robust against external or internal perturbations.
more interestingly, the network robustness is highly related to the network’s structural characteristics, including fbls.
however, previous results  <cit>  have been presented mainly through simulation and experiment studies because of the complexity of real biological networks.
that raised a pressing need to develop various analytical approaches to validate the promising conjectures.
in this paper, i used a synchronous boolean network model in which a node state is represented by a boolean value and updated by a logical rule.
a network is considered robust if the attractor does not change against a state perturbation.
based on that assumption, i created a novel concept to characterize the nodes with respect to fbl structures: no-fbl-in-upstream  and no-fbl-in-downstream .
this fbl-based characterization is different from other fbl-based measures  <cit>  in that it focuses on involvement with fbls in the upstream or downstream paths, not with the node itself.
based on that notion, i proved two simple but useful theorems.
one is that an nfu node is always frozen irrespective of the initial states of other nodes.
thus, the converging dynamics of an nfu node can be simply determined.
the other is that a network is robust against an arbitrary perturbation subject to a non-source nfd node.
this result shows that a network state eventually converges to the same attractor despite a perturbation subject to non-source nfd nodes.
note that the two theorems hold for arbitrary update functions as well as initial states.
in addition, the second theorem led me to develop a function to approximately compute the perturbation-sustainable probability.
i verified its effectiveness by showing that the higher the probability, the larger the proportion of essential, disease-associated, and drug-target genes in human signaling networks.
i believe these results will promote understanding of the effects of fbls on network dynamics and reduce the cost of computing robustness in existing tools which simulate a network state trajectory .
additional files
additional file 1: table s <dig>  dataset of kegg network.
it consists of  <dig> genes and  <dig> interactions constructed by integrating all the human signaling pathways in the kegg  database.
table s <dig>  dataset of wang network.
it consists of  <dig> genes and  <dig>  interactions downloaded from http://www.bri.nrc.ca/wang.
table s <dig>  detailed analysis result of the kegg network.
it includes information about essential genes, disease genes, drug targets, nru/nrd genes, and perturbation-sustainable probabilities in the kegg network.
table s <dig>  detailed analysis result of the wang network.
it includes information about essential genes, disease genes, drug targets, nru/nrd genes, and perturbation-sustainable probabilities in the wang network.
additional file 2: figure s <dig>  comparison between groups of nfd and non-nfd genes in random networks with respect to the proportions of essential genes, disease genes, and drug targets.
in each subfigure, a set of  <dig> random networks were generated by rewiring the interactions of the signaling networks such that the in-degree and the out-degree of all nodes are conserved.
result of random networks shuffled from kegg network.
the average numbers of nfd and non-nfd genes were  <dig> and  <dig>  respectively.
the average proportions of essential genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of disease genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of drug-targets in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
result of random networks shuffled from wang network.
the average numbers of nfd and non-nfd genes were  <dig> and  <dig>  respectively.
the proportions of essential genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of disease genes in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
the proportions of drug-targets in the nfd and the non-nfd groups were  <dig>  and  <dig> , respectively.
figure s <dig>  changes in the proportion of functionally important genes over the threshold value of the perturbation-sustainable probability in random networks.
in each subfigure, a set of  <dig> random networks were generated by rewiring the interactions of the signaling network such that the in-degree and the out-degree of all nodes are conserved.
given a threshold value β, the y-axis values indicate the average proportions of essential genes, disease genes, and drug targets over the set of candidate genes whose perturbation-sustainable probability is larger than or equal to β in random networks.
results in random networks shuffled from kegg network.
for a reliable comparison, the maximal β was set to  <dig>  which generates  <dig> candidate genes on average.
results in random networks shuffled from wang network.
the maximal β was set to  <dig> , which results in  <dig> candidate genes on average.
abbreviations
fblfeedback loop
nfdno-fbl-in-downstream
nfuno-fbl-in-upstream

 it is well known that bio-molecular networks can keep their regulatory functions robust against various types of external or internal perturbations. for instance, the fate decision mechanism in a bacteriophage life cycle, the chemotaxis process in escherichia coli, and segmental polarization in drosophila melanogaster were shown to be robust against noisy environments. it is more interesting that the dynamics of a biological network can be highly related to its structural characteristics. in particular, many recent studies have shown that a feedback loop, a circular chain of interactions, can play an important role in controlling the robustness or susceptibility of networks. for instance, the negative fbl between mdm and p maintains an optimal level of p and creates appropriate dynamics of p expression level changes for a given level of dna damage. the xenopus cell cycle is also robustly controlled against a certain level of perturbation with the help of several fbls. it was shown that a high proportion of coherently coupled fbls can enhance the robustness of a network against state perturbations. the number of fbls involved at a node was also found to be positively correlated with the node’s functional importance. those simulation studies, however, cannot fully explain how the fbls influence the network robustness. hence, there is a pressing need to more rigorously analyze the relationship between fbl structures and network dynamics. to measure network robustness, i herein use a synchronous boolean network model in which a node state is represented by a boolean value, and the states of all nodes are synchronously updated at every discrete time step. every network state moves to another state, and a series of consecutive transitions are represented by a network state trajectory that eventually converges to a fixed-point or cyclic attractor. the attractor can describe various dynamic behaviors in a biological system, such as multi-stability and oscillations. if a node state is perturbed, the trajectory might converge to a different attractor. therefore, a network is considered robust if the attractor does not change against a perturbation. some tools have been proposed to quantify the network robustness by simulating the state transitions after randomly initializing the node states. they have a limitation in network size for analysis, though, due to the exponential complexity of attractor computation. therefore, it is a critical issue to find analytic results that can identify trivial parts that do not require further computation of state transitions. in this paper, i focus on the effects of an fbl on boolean converging dynamics. a state of a node is propagated to other nodes along a path in a chain of consecutive interactions. therefore, the state cannot be fed back to the original node if it is not involved in an fbl. in other words, the current state of a node will eventually disappear unless a downstream path constructs an fbl. from that idea, i developed an fbl-based notion to classify nodes in a network. in particular, i defined two sets of nodes, no-fbl-in-upstream and no-fbl-in-downstream, according to whether the upstream and downstream paths, respectively, involve any fbls and proved two theorems regarding nfu and nfd nodes. one is that every nfu node is always frozen irrespective of the initial states of other nodes. this implies that the converging values of all nfu nodes are eventually fixed to a value determined by the upstream source nodes. it also means that a network is likely to be susceptible to a perturbation subject to the source nodes. the other is that a network is robust against an arbitrary perturbation subject to a non-source nfd node. in other words, a network state eventually converges to the same attractor despite a state perturbation subject to a non-source nfd node. inspired by those results, i further developed a perturbation-sustainable probability which indicates how likely it is that a perturbation effect will be sustained through a network state trajectory and showed that it can adequately identify functionally important genes, such as essential, disease-associated, and drug-target genes, in large human signaling networks. taken together, all of these results will promote understanding of the effects of fbls on boolean converging dynamics and reduce the computational costs of state transition-based simulation tools. methods structural classification of nodes in a network in this study, a biological network is represented by a directed graph g where v = {v  v  ⋯, vn} is a set of nodes and e = {e  e  ⋯, ea} is a set of directed edges; an edge e ∈ e is an ordered pair of nodes where vi, vj ∈ v. i use some notions from graph theory, including fbl and upstream/downstream paths, to represent the biological networks as follows. definition a node u is an input node of v if there exists an interaction from u to v  ∈ e). in addition, in-degree of v means the number of input nodes of v. definition a node v is a source node if in-degree of v is zero. it is assumed that the state of a source node is fixed to its initial value over all the time. definition given a network g, a path p of a length l is represented by a sequence of ordered nodes u1u2 ⋯ ul +  with interactions from ui to ui +   ∈ e for∀ i ∈ {    ⋯, l}) with no repeated nodes except u and ul +  in addition, p is called a feedback loop if u1 = ul +  definition given a network g, an upstream path p = u1u2 ⋯ ul +  of a node v ∈ v is a path in which the last node ul +  is v. note that if p is a feedback loop, then it is both an upstream and downstream path of v. in addition, p = u1u2 ⋯ ul +  is a maximal upstream path if there is no longer path such as wu1u2 ⋯ ul +  for some w ∈ v. based on those terms, i define no-fbl-in-upstream and no-fbl-in-downstream nodes as follows: definition given a network g, a node v is called a no-fbl-in-upstream node if there is no upstream path p = u1u2 ⋯ ulv such that for some i ∈ {    ⋯, l}, ui is involved in any feedback loop. figure  shows an example of nfu and nfd nodes in a network. this network contains five nfu nodes v  v  v  v and v and four nfd nodes v  v  v and v note that v  v and v are both nfu and nfd nodes. on the other hand, it also contains five nodes that are neither nfu nor nfd nodes because an fbl is both upstream and downstream of each of them. in particular, note that v is not directly involved in an fbl. in this paper, i will show that the nfu and nfd nodes can induce interesting dynamic properties in a perturbation analysis.fig. an example of nfu and nfd nodes in a network. every node is classified into one of four categories: “nfu but not-nfd”, “nfd but not-nfu”, “nfu and nfd”, and “neither nfu nor nfd” a perturbation analysis in a boolean network model to define the robustness or sensitivity of a network, i use a synchronous boolean network model used in previous studies. in a boolean network g, each vi ∈ v has a value of or that represent the possible states of the corresponding elements. for example, the values and represent the “turn-on” and “turn-off” states of a gene, respectively. a directed interaction can represent a positive or negative relationship from vi to vj. the value of each variable vi at time t +  is determined by the values of ki other variables vi vi ⋯,viki with an interaction to vi at time t by a boolean update function fi:01ki→ where fi is a constant value if vi is a source node. all the boolean variables are synchronously updated by a set of update functions f = {f  f  ⋯, fn}, and each update rule can be written as vit+1=fivi1t,vi2t,⋯,vikit. many studies have been performed to elucidate the dynamic behaviors of biological networks. in particular, i address robustness against perturbations in terms of boolean dynamics. in a boolean network g, a network state at time t is represented by an ordered list v =  ∈ {  1}n. then, for a subset u = {u  u  ⋯, um} ⊆ v, a subset state of u at time t denoted by vu =  ∈ {  1}m is an ordered list consisting of values u through um at time t. a state trajectory of v starts from an initial state and eventually converges to either a fixed-point or limit-cycle attractor. these attractors can represent diverse biological network behaviors, such as multi-stability and oscillation. this notion of an attractor introduces robustness in terms of the boolean network dynamics as follows. if a network sustains an attractor against a perturbation, it is called robust against the perturbation. this concept has been widely used. here, i consider an initial-state perturbation. given an initial state v =  at t =  an initial-state perturbation subject to node vx ∈ v represents a situation in which v is mutated to v' =, i.e., the corresponding initial value is switched to vx¯ ). an initial-state perturbation represents the abnormal status of a protein or gene caused by a mutation. the attractors to which v and v' will converge can be compared to each other. the network is called robust or sensitive against the perturbation according to whether the attractors are the same as or different from each other, respectively. based on this concept, i define some terms more rigorously with respect to the boolean dynamics, as follows. definition the sequence of states to which v eventually converges is called the attractor induced from v, which is denoted by an ordered list of network states ζ =  where v = v for ∀ t ≥ τ, and v ≠ v for ∀ i ≠ j ∈ {τ, τ +   …, τ + p − 1}. in addition, for a subset u ⊆ v, ζ =  represents the states sequence of u in the attractor induced from v. definition for u ⊆ v, ζ is frozen if there exists a time step τ such that v = v for ∀ v ∈ u and ∀ t ≥. definition given two attractors with a same length, ζ =  and ζ =, they are equivalent to each other if there exists a time step offset t ≥  such that v = v' mod p) for ∀ i ∈ {    …, p − 1}. definition consider an arbitrary initial state v =  and its perturbed state at vx ∈ v, v' =. the boolean network is called robust against the perturbation subject to vx if ζ is equivalent to ζ. otherwise, it is called sensitive or susceptible. datasets of signaling networks and functionally important genes in this study, i derive an estimated probability with which a perturbation effect is sustained in a network. to show the usefulness of it, i used two large-scale human signaling networks. one is the signaling network of genes and interactions constructed in a previous study by integrating all the human signaling pathways in the kegg database. the other signaling network consists of genes and interactions downloaded from http://www.bri.nrc.ca/wang. in this work, i call them the kegg and wang networks, respectively. in addition, i considered essential, disease, and drug-targeted genes to represent functionally important genes. by using the deg database, i found and essential genes included in the kegg and wang networks, respectively. i also found and disease genes in the kegg and wang networks, respectively, using the omim database. finally, i identified and drug target genes in the kegg and wang networks, respectively, using the drugbank database.  dynamic properties of nfu nodes in this section, i show that nfu nodes are eventually frozen in boolean network dynamics. a boolean network g with a set of update functions f is given. lemma 1 given an initial state v and a node vk ∈ v, let u = {u  u  ⋯, um} be the set of input nodes of vk. if ζ is frozen, then ζvvk is also frozen. proof for ∀ ui ∈ u, there exists a time step τi such that ui = ui for ∀ t ≥ τi since ζvui is frozen. let τ=maxi∈12…mτi. then, vk = fk, ⋯, um) = fk, ⋯, um) = vk for ∀ t ≥ τ. thus, ζvvk is also frozen ■ lemma 2 an initial state v and a node v ∈ v are given. if every maximal upstream path of v includes at least one node u where ζ is frozen, then ζ is also frozen. proof let p  p  ⋯, pm be the list of maximal upstream paths of v, and let ui ∈ pi be the node where ζvui is frozen. then consider a sub-path pi' of pi starting from ui and ending at v. define w = {w ∈ v|w ∈ pi' for some i} and let l be the length of the longest path from w to v. assuming that l = maxw ∈ wl, w can be divided into l +  disjoint subsets w  w  ⋯ and wl where wk = {w ∈ w|l = k}. then ζ for ∀ w ∈ w is frozen by mathematical induction with respect to l, as follows. when k = l, it is obvious that ζ of every w ∈ wl is frozen because w ∈ {u  u  …, um}. assume that ζ of every w ∈ wk +  is frozen and consider an arbitrary element w' ∈ wk. then every input node of w' is an element of wk +  by lemma ζvw' is frozen. thus, ζ of every w ∈ wk is also frozen. by mathematical induction, ζ of every w ∈ w is frozen. therefore, ζ is also frozen because v ∈ w■ lemma provides a sufficient condition for the frozenness of a node. this can be extended to the case of nfu nodes as follows. theorem 1 an initial statev is given. if v ∈ v is an nfu node, then ζ is frozen. proof by the definition of nfu nodes, every maximal upstream of v starts with a source node u whose ζ is frozen. by lemma ζ is also frozen ■ this theorem implies that the states of nfu nodes are dependent on the states of source nodes, and this might make the network tend to be susceptible to perturbations subject to source nodes. corollary an initial state v is given. if there is no fbl then ζ is frozen. proof since there are no fbls, every v ∈ v is an nfu node. by theorem it follows that ζ is always frozen irrespective of the initial states ■ theorem and its corollary explain the effect of fbls on the frozenness of the converging state sequences. more specifically, every nfu node is frozen to a value determined by the set of source nodes included in its upstream paths. i also note that this result is strongly related to previous studies based on synchronous or asynchronous boolean network models. in particular, the corollary corresponds to a previous result having stated that the boolean dynamics converges to a unique fixed point in an acyclic boolean network. it is also relevant to the previous results showed that limit-cycle attractors can be induced by negative feedback loops. in addition, theorem can reduce the computation of attractors in a large scale network by easily obtaining the converging values of the nfu nodes. dynamic properties of nfd nodes in the lemmas and a theorem of this section, i investigate the effect of fbls on robustness. i consider an arbitrary initial state v =  and a perturbed state at vx ∈ v from v, v' =  in the following lemmas and and theorem i denote the value of a node w ∈ v at time t in the trajectories starting from v and v' by v{w} and v{w}', respectively. lemma 3 let v be an initial state, v' a perturbed state at vx ∈ v from v, and w ∈ v an arbitrary node. if there is no path from vx to w then v{w} = v{w}' for ∀ t ≥  proof the state value of node w is updated irrespective of that of node vx because there is no path from vx to w. thus, the lemma holds ■ lemma 4 let v be an initial state, v' a perturbed state at vx ∈ v from v, w ∈ v an arbitrary node. let y = {y ∈ v|y is included in some path from vx to w} and l the length of a longest path from vx to y ∈ y. if vx is a non-source node and no node in y is involved with any fbl, then v{w} = v{w}' for ∀ t ≥ l +  proof by mathematical induction with respect to l, i show that for every y ∈ y, v{y} = v{y}' for ∀ t ≥ l +  as follows. when l =  it is obvious that y = vx. then vvxt=vvx't for ∀ t ≥  because vx is a non-source node and involved with no fbl. to prove the inductive step, i assume that the property holds for l ≤ k −  consider an arbitrary y ∈ y such that l = k and let u be the set of input nodes of y. for every u ∈ u, there are two cases to consider: either u ∈ y or u ∉ y. in case of u ∈ y, it is obvious that l ≤ k −  by the definition of l. by the induction hypothesis, v{u} = v{u}' for ∀ t ≥ l +  in case of u ∉ y, it means that there is no path from vx to u. then v{u} = v{u}' for ∀ t ≥  by lemma from both cases, for ∀ u ∈ u, v{u} = v{u}' for ∀ t ≥ k. then v{y} = v{y}' for ∀ t ≥ k +  thereby showing the property holds when l = k. since w ∈ y, the lemma holds ■ theorem 2 letv be an initial state, v' a perturbed state at vx ∈ v fromv, and w ∈ v an arbitrary node. if vxis an nfd and non-source node, then the network is robust against a state perturbation subject to vx. proof i show that there exists a constant time t such that v{w} = v{w}' for ∀ t ≥ t in the following three cases. case that = vx: because w is an nfd and non-source node, v{w} = v{w}' for ∀ t ≥  case that w is not connected by any path from vx: by lemma v{w} = v{w}' for ∀ t ≥  case that w is connected by at least one path from vx: let y = {y ∈ v|y is included in some path from vx to w} and l be a longest length of those paths, respectively. because vx is an nfd node, no node included in y is involved with any fbl. by lemma v{w} = v{w}' for ∀ t ≥ l +  by,, and, there exists a constant time t such that v{w} = v{w}' for ∀ t ≥ t and ∀ w ∈ v. accordingly, the attractors starting at v and v' are equivalent to each other. therefore, the network is robust against the state perturbation subject to vx■ theorem indicates that biological networks might be robust against perturbations subject to nfd nodes. to support this result, i compared nfd and non-nfd gene groups with respect to the proportions of essential genes, disease genes, and drug targets in two human signaling networks, the kegg and wang networks. as shown in fig.  the proportions of essential genes, disease genes, and drug targets among nfd genes were significantly smaller than those among non-nfd genes in both networks. i assume that essential genes, disease genes, and drug targets are likely to be susceptible to mutations, perturbations, or other external changes. in this regard, the relatively low proportions of essential genes, disease genes, and drug targets in the nfd group in the large-scale signaling networks support theorem in addition, i further examined the proportions of essential genes, disease genes, and drug targets in nfd group in random networks to examine if the observed result is specific to the signaling networks. i created each set of random networks by rewiring the interactions of the kegg ) and wang ) networks so that the in-degree and the out-degree of the nodes are conserved, and observed that there is little difference between the nfd and non-nfd groups with respect to the proportions of essential genes, disease genes, and drug targets. this implies that the functionally important genes in the real signaling networks are not randomly distributed in terms of nfd classification.fig. comparison between groups of nfd and non-nfd genes in signaling networks. a result in kegg network with nfd genes and non-nfd genes. the proportions of essential genes in the nfd and the non-nfd groups were and, respectively. the proportions of disease genes in the nfd and the non-nfd groups were and, respectively. the proportions of drug-targets in the nfd and the non-nfd groups were and, respectively. b result in wang network with nfd genes and non-nfd genes. the proportions of essential genes in the nfd and the non-nfd groups were and, respectively. the proportions of disease genes in the nfd and the non-nfd groups were and, respectively. the proportions of drug-targets in the nfd and the non-nfd groups were and, respectively. in both networks, all the proportions for the nfd group were significantly smaller than those for the non-nfd group estimation of sustainability of a perturbation effect in the previous section, theorem showed that a network state is robust against a perturbation as long as the perturbation effect is not sustained by downstream fbls. in other words, the existence of downstream fbls is a necessary condition to make a network susceptible to a perturbation. inspired by that result, i have derived an estimated probability that a perturbation effect will be sustained. given a node vx ∈ v subject to a perturbation, lemma shows that only downstream paths of vx need to be considered, and lemma shows that only those involved with an fbl need to be considered. i first estimate the probability with which a perturbation subject to vx is sustained through a single path involved with a fbl. figure  shows an example of a downstream path p = vxu1u2 ⋯ ul of vx which includes an fbl, and i consider v and v' which are an initial state and a perturbed state at vx ∈ v from v, respectively. it is said that the effect of a perturbation starting at vx at the initial time is sustained through propagations in a sequence of u  u  ⋯, ul if vuii≠vui'i for ∀ i ∈ {  ⋯, l}. herein, it is assumed that a probability with which ui is differently updated by the flipped value of ui −  denoted by prvuii≠vui'i|vui−1i−1≠vui−1'i− is the inverse of the in-degree of ui because of the following reason. let w=w w ⋯,wdi be the set of input nodes of ui where di is the in-degree of ui. by assuming that the input nodes have an even degree of influence on updating ui, i.e., pry|x1=⋯=pry|xdi where y and xk denote two events vuii≠vui'i and vwki−1≠vwk'i− respectively. it is also assumed that ui is always differently updated given a perturbation has occurred at one of the input nodes. accordingly, pry|uk∈1⋯dixk=pry|x1+⋯+pry|xdi= and thus pr = 1/di. note that ui − 1 ∈ w because ui −  is one of the input nodes of ui. with this result, the probability with which the perturbation subject to vx is sustained through a path p can be derived as follows:fig. an example of a downstream path with a feedback loop. a node v x is subject to a state perturbation, and the perturbation effect can be sustained at u with a probability of the inverse of the in-degree of u this propagation is continued along the path p = v x u 1 u 2 ⋯ u l involved with a fbl prp=∏i=1l1/di,ifanfblisinvolved, otherwise let p  p  ⋯, pm be the set of all downstream paths of vx. then i define the perturbation-sustainable probability γ, the probability that the perturbation subject to vx will be sustained through at least one fbl, as follows: γvx=maxi∈1⋯mprpi. if a gene with a relatively high γ value is subject to a perturbation, the network is likely to induce an abnormal dynamics due to the well conserved perturbation effect. in this regard, the perturbation-sustainable probability can indicate how much a gene is functionally or dynamically important in a signaling network. to show the usefulness of this probability, i examined the relationship between γ and the proportions of putatively susceptible genes in human signaling networks. given a threshold value β, the proportions of essential genes, disease genes, and drug targets among the set of genes such that {vx|γ ≥ β} are plotted against the threshold value in the kegg and wang networks. as shown in the figure, the genes with a high perturbation-sustainable probability are more likely to be essential genes, disease genes, and drug targets in both networks. this implies that the perturbation-sustainable probability can adequately identify the functionally important genes in human signaling networks. in addition, it is notable that the relation of the perturbation-sustainable probability to the functionally important genes was not observed in the random networks created by rewiring the interactions of the signaling networks. as in the results of additional file 2: figure s this also implies that the functionally important genes in the real signaling networks are not randomly distributed in terms of nfd classification. taken together, it is interesting that such a simple topological measurement of genes based only on fbls can efficiently predict the functionally important genes in human signaling networks.fig. changes in proportions of functionally important genes over the threshold value of the perturbation-sustainable probability. given a threshold value β, the y-axis values indicate the proportions of essential genes, disease genes, and drug targets over the set of candidate genes whose perturbation-sustainable probability is larger than or equal to β. the larger the value of β, the smaller the number of candidate genes is. a results of essential genes, disease genes, and drug targets in the kegg network. for a reliable comparison, the maximal β was set to which generates candidate genes. b results of essential genes, disease genes, and drug targets in the wang network. the maximal β was set to, which results in candidate genes discussion in this study, i did not address the dynamics of non-nfu and non-nfd nodes, i.e., nodes that are involved in fbls, and the analysis of their dynamics remains an open problem. in addition, the update-rule perturbation, another well-known type of perturbations, was not considered in this study because it influences the network robustness in a different way than the initial-state perturbation by changing the state transition diagram. therefore, a future study should include analyses of genes that are neither nfu nor nfd nodes, and analysis of robustness against update-rule perturbations. finally, it should be noted that the analyses in this study might not be effective for other types of biological networks than the signaling networks. for example, nfu/nfd classification was not meaningful in the large-scale gene regulatory networks because most genes were classified to nfd nodes. this implies that another method to further classify nfd nodes is required for analysis of those networks.  it is well known that biological networks can keep their regulatory functions robust against external or internal perturbations. more interestingly, the network robustness is highly related to the network’s structural characteristics, including fbls. however, previous results have been presented mainly through simulation and experiment studies because of the complexity of real biological networks. that raised a pressing need to develop various analytical approaches to validate the promising conjectures. in this paper, i used a synchronous boolean network model in which a node state is represented by a boolean value and updated by a logical rule. a network is considered robust if the attractor does not change against a state perturbation. based on that assumption, i created a novel concept to characterize the nodes with respect to fbl structures: no-fbl-in-upstream and no-fbl-in-downstream. this fbl-based characterization is different from other fbl-based measures in that it focuses on involvement with fbls in the upstream or downstream paths, not with the node itself. based on that notion, i proved two simple but useful theorems. one is that an nfu node is always frozen irrespective of the initial states of other nodes. thus, the converging dynamics of an nfu node can be simply determined. the other is that a network is robust against an arbitrary perturbation subject to a non-source nfd node. this result shows that a network state eventually converges to the same attractor despite a perturbation subject to non-source nfd nodes. note that the two theorems hold for arbitrary update functions as well as initial states. in addition, the second theorem led me to develop a function to approximately compute the perturbation-sustainable probability. i verified its effectiveness by showing that the higher the probability, the larger the proportion of essential, disease-associated, and drug-target genes in human signaling networks. i believe these results will promote understanding of the effects of fbls on network dynamics and reduce the cost of computing robustness in existing tools which simulate a network state trajectory. additional files additional file 1: table s dataset of kegg network. it consists of genes and interactions constructed by integrating all the human signaling pathways in the kegg database. table s dataset of wang network. it consists of genes and interactions downloaded from http://www.bri.nrc.ca/wang. table s detailed analysis result of the kegg network. it includes information about essential genes, disease genes, drug targets, nru/nrd genes, and perturbation-sustainable probabilities in the kegg network. table s detailed analysis result of the wang network. it includes information about essential genes, disease genes, drug targets, nru/nrd genes, and perturbation-sustainable probabilities in the wang network. additional file 2: figure s comparison between groups of nfd and non-nfd genes in random networks with respect to the proportions of essential genes, disease genes, and drug targets. in each subfigure, a set of random networks were generated by rewiring the interactions of the signaling networks such that the in-degree and the out-degree of all nodes are conserved. result of random networks shuffled from kegg network. the average numbers of nfd and non-nfd genes were and respectively. the average proportions of essential genes in the nfd and the non-nfd groups were and, respectively. the proportions of disease genes in the nfd and the non-nfd groups were and, respectively. the proportions of drug-targets in the nfd and the non-nfd groups were and, respectively. result of random networks shuffled from wang network. the average numbers of nfd and non-nfd genes were and respectively. the proportions of essential genes in the nfd and the non-nfd groups were and, respectively. the proportions of disease genes in the nfd and the non-nfd groups were and, respectively. the proportions of drug-targets in the nfd and the non-nfd groups were and, respectively. figure s changes in the proportion of functionally important genes over the threshold value of the perturbation-sustainable probability in random networks. in each subfigure, a set of random networks were generated by rewiring the interactions of the signaling network such that the in-degree and the out-degree of all nodes are conserved. given a threshold value β, the y-axis values indicate the average proportions of essential genes, disease genes, and drug targets over the set of candidate genes whose perturbation-sustainable probability is larger than or equal to β in random networks. results in random networks shuffled from kegg network. for a reliable comparison, the maximal β was set to which generates candidate genes on average. results in random networks shuffled from wang network. the maximal β was set to, which results in candidate genes on average. abbreviations fblfeedback loop nfdno-fbl-in-downstream nfuno-fbl-in-upstream 
many previous studies through simulations or experiments have shown that feedback loop structures play an important role in controlling the network robustness without fully explaining how they do it. this implies that a network state eventually sustains the attractor despite a perturbation subject to a non-source nfd node. hence, there is a pressing need to more rigorously analyze the influence of fbl structures on network robustness. taken together, these results will promote understanding of the effects of fbl on network robustness in a more rigorous manner. based on those definitions, i first prove that every nfu node is eventually frozen in boolean dynamics. thus, nfu nodes converge to a fixed value determined by the upstream source nodes. biological networks keep their functions robust against perturbations. inspired by this result, i further propose a perturbation-sustainable probability that indicates how likely a perturbation effect is to be sustained through propagations. i show that genes with a high perturbation-sustainable probability are likely to be essential, disease, and drug-target genes in large human signaling networks. in this paper, i propose a novel node classification notion based on the fbl structures involved. more specifically, i classify a node as a no-fbl-in-upstream or no-fbl-in-downstream node if no feedback loop is involved with any upstream or downstream path of the node, respectively. boolean dynamicsrobustnessperturbationsfeedback loopsignaling networkshttp://dx.doi.org/ /501100002568university of ulsan research fundkwon yung-keun issue-copyright-statement© the author 2016 second, i prove that a network is robust against an arbitrary state perturbation subject to a non-source nfd node.
 biological networks keep their functions robust against perturbations. many previous studies through simulations or experiments have shown that feedback loop structures play an important role in controlling the network robustness without fully explaining how they do it. hence, there is a pressing need to more rigorously analyze the influence of fbl structures on network robustness.  in this paper, i propose a novel node classification notion based on the fbl structures involved. more specifically, i classify a node as a no-fbl-in-upstream or no-fbl-in-downstream node if no feedback loop is involved with any upstream or downstream path of the node, respectively. based on those definitions, i first prove that every nfu node is eventually frozen in boolean dynamics. thus, nfu nodes converge to a fixed value determined by the upstream source nodes. second, i prove that a network is robust against an arbitrary state perturbation subject to a non-source nfd node. this implies that a network state eventually sustains the attractor despite a perturbation subject to a non-source nfd node. inspired by this result, i further propose a perturbation-sustainable probability that indicates how likely a perturbation effect is to be sustained through propagations. i show that genes with a high perturbation-sustainable probability are likely to be essential, disease, and drug-target genes in large human signaling networks.  taken together, these results will promote understanding of the effects of fbl on network robustness in a more rigorous manner. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords boolean dynamicsrobustnessperturbationsfeedback loopsignaling networkshttp://dx.doi.org/ /501100002568university of ulsan research fundkwon yung-keun issue-copyright-statement© the author 2016 