Find a network with locally-monotonic functions and motif-avoidant attractor...

[daemontus]

... or prove that such network cannot exist.

[kyuhyongpark]

I modified an example that Jordan gave me long time ago.

A = not E or (A and B and C) B = not F or (A and B and C) C = not D or (A and B and C) D = A E = B F = C

This one is locally monotonic, but has trap avoidant attractor in plain async.

Simply speaking, if we have any system that has a trap-avoidant attractor in the asynchronous update, we can add a linear chain so that it is locally monotonic as well. The delay is intrinsic in plain async update, and hence adding a delay node does not change its dynamics. The only exception is when adding the delay makes the network linear-cuttable. Then the trap-avoidant attractor will be destroyed. For example, the only part that is not linear-cuttable in the above model is the self loops. If we add delay nodes for the self loops,

A = not E or (G and B and C) B = not F or (A and H and C) C = not D or (A and B and I) D = A E = B F = C G = A H = B I* = C

we get a linear-cuttable version, which does not have trap avoidant attractors in plain async.

[kyuhyongpark]

I noticed that even the example in the Science Advances paper is locally monotonic.

A= not A and not B or C B= not A and not B or C C*= A and B

[kyuhyongpark]

I think the above one can be represented as a threshold function, so it proves that models using threshold functions can have trap avoidant attractors.

[giang-trinh]

I ran bench_attractor_search.py on these above models. The results confirm Kyu's claims.

Model 1

A, (!A & !B) | C
B, (!A & !B) | C
C, A & B

is locally-monotonic and it has one minimal trap space (a fixed point) and one motif-avoidant attractor.

Model 2

A, !E | (A & B & C)
B, !F | (A & B & C)
C, !D | (A & B & C)
D, A
E, B
F, C

is locally-monotonic and it has also one minimal trap space (a fixed point) and one motif-avoidant attractor.

Model 3

A, !E | (G & B & C)
B, !F | (A & H & C)
C, !D | (A & B & I)
D, A
E, B
F, C
G, A
H, B
I, C

is locally-monotonic and it has only one minimal trap space (a fixed point).

In addition, model 4

A, !A | !B
B, !A | !B

is locally-monotonic and it has one minimal trap space {A = *, B = *} and an attractor {00, 01, 10}. This case is not faithful (i.e., the attractor does not include all states represented by the minimal trap space containing it).

Model 5

xalpha, !xbeta | Z2
xbeta, xgamma | Z2
xgamma, xalpha & !Z2
Z1, !(xalpha & xbeta & !xgamma)
xa, !xb | Z1
xb, xc | Z1
xc, xa & !Z1
Z2, !(xa & xb & !xc)

is locally-monotonic. It has only one minimal trap space where all variables are free. However, it has two attractors contained in this minimal trap space. This case is non-univocal (i.e., a minimal trap space contains two or more attractors).

In summary, a locally-monotonic model under the fully asynchronous update can have motif-avoidant attractors, non-faithful, and non-univocal attractors.

[jcrozum]

A smaller version of the example from @kyuhyongpark:

A, !B | A & C
B, !C | A & B
C, !A | B & C

There are 2 attractors:

{'A': 'X', 'B': 'X', 'C': 'X'}
{'A': 1, 'B': 1, 'C': 1}

The steady state is only reachable from itself. The oscillation has 000 in its basin and has STG:

 __________________________
 |                        |
 V                        |
010->011->001->101->100->110

Note that all regulations are monotonic, and all self-loops are positive.

[kyuhyongpark]

@giang-trinh I noticed that the model 4 is faithful, as the number of oscillating variables (2) equals the dimension of the trap space (2). Another way to put it is that model 4 is faithful because the smallest subspace containing the attractor is the smallest trap space as well. Faithfullness do not require the attractor to visit all states inside the smallest trap space. See the abstract of this paper

[giang-trinh]

Thank you for your notice. Following Definition 1 of this paper, model 4 is actually faithful.

[jcrozum]

I think we have the examples we need for now, so I'm closing this issue.