Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Turning block-sequential automata
networks into smaller parallel
networks with isomorphic limit dynamics
Pacôme Perrotin, Sylvain Sené
LIS
July 27, 2023

1/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Biological networks

2/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

context

The modelisation of neurological networks starts in the 40s (McCulloch1943)
The modelisation of gene regulatory networks starts in the 60s (Kauffman1969, Thomas 1973)
Both are applications of automata networks.

3/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

context

extracted from D. PA Cohen et al. “Mathematical modelling of molecular pathways enabling tumour cell
invasion and migration”. In: PLoS computational biology 11.11 (2015), e1004571.

4/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Automata networks

5/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
Let Σ be an alphabet. An Automata Network (AN) is a function
F : Σn → Σn , for some n ∈ N.

6/24

Biological networksAutomata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
Let Σ be an alphabet. An Automata Network (AN) is a function
F : Σn → Σn , for some n ∈ N.
Example : Σ = {0, 1}, n = 3.
110100111101010000011001

6/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
Let Σ be an alphabet. An Automata Network (AN) is a function
F : Σn → Σn , for some n ∈ N.
Example : Σ = {0, 1}, n = 3.
110100111
101010000011001

All functions applied in parallelfa (x) = xb ∨ ¬xcfb (x) = xa
fc (x) = xb

6/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
Let Σ be an alphabet. An Automata Network (AN) is a function
F : Σn → Σn , for some n ∈ N.
Example : Σ = {0, 1}, n = 3.
110
ab100

111
101010c000011001

All functions applied in parallelfa (x) = xb ∨ ¬xc
fb (x) = xa
fc (x) = xb

6/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
Let Σ be an alphabet. An Automata Network (AN) is a functionF : Σn → Σn , for some n ∈ N.
Example : Σ = {0, 1}, n = 3.
>
a>

110b>

100

111
101010<c000011001

Update schedule : ({a, b}, {c})fa (x) = xb ∨ ¬xc
fb (x) = xa
fc (x) = xb

6/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Definitions
110ab100

111
101010c000011001

fa (x) = xb ∨ ¬xc
fb (x) = xa
fc (x) = xb
The limit dynamics of F is the subgraph of the dynamics that contains
only the configurations x such that F k (x) = x for some k ∈ N∗ .
7/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Examples
110ab

100

111
101010c000011001

Updated in parallel.
fa (x) = ¬xb ∨ xc
fb (x) = xa
fc (x) = xb

8/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Examples
<a>

110b>

100

111
101010<c000011001

Update schedule ({a}, {b}, {c}).
fa (x) = ¬xb ∨ xc
fb (x) = xa
fc (x) = xb

8/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Examplesa10110001b

Updated in parallelfa (x) = ¬xa ∨ xb
fb (x) = xa

9/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Examples>a>10110001b<Update schedule ({b}, {a})fa (x) = ¬xa ∨ xb
fb (x) = xa

9/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

I Automata networks are dynamical systems
I Deciding if a network has a given attractor is NP-complete
I Various update schedules increase the combinatorial complexity of theobjects
I We would like to reduce this complexity in some cases

10/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelisation

11/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelization algorithmefa (x) = xa ∨ xd ∨ ¬xhb><<hfb (x) = ¬xa>

a>

c>
>

>

d({h}, {a, c, d, e}, {b})fc (x) = xb
fd (x) = xc
fe (x) = xa
fh (x) = xe

12/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelization algorithmefa (x) = xa ∨ xd ∨ ¬θhb><<hfb (x) = ¬θa>

a>

c>
>

>

d({h}, {a, c, d, e}, {b})fc (x) = xb
fd (x) = xc
fe (x) = xa
fh (x) = xe

12/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelization algorithme>>afa (x) = xa ∨ xd ∨ ¬xe

b
<>

>

hfb (x) = ¬θa>c>>d({a, c, d, e, h}, {b})fc (x) = xb
fd (x) = xc
fe (x) = xa
fh (x) = xe

12/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelization algorithm

>

e>

>

afa (x) = xa ∨ xd ∨ ¬xebc>>

hfb (x) = ¬(xa ∨ xd ∨ ¬xe )

>

>
>

>

fc (x) = xb
fd (x) = xc

dfe (x) = xa({a, b, c, d, e, h})fh (x) = xe

>

12/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Parallelization algorithm

efa0 (x) = xa ∨ xd ∨ ¬xebafb0 (x) = ¬(xa ∨ xd ∨ ¬xe )cfc0 (x) = xb
fd0 (x) = xc

hd({a, b, c, d, e, h})fe0 (x) = xa
fh0 (x) = xe

13/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

I Our contribution is an algorithm that simplifies the result of theparallelization.
I It operates following simple rules:
if two automata have the same local function (up to an operation) thenwe remove one of them,
I if an automaton has no influence over the network we remove it.
II In the worst case, running this algorithm requires solving a polynomial

amount of CoNP-complete problems.

14/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Size reduction algorithm

efa0 (x) = xa ∨ xd ∨ ¬xebafb0 (x) = ¬(xa ∨ xd ∨ ¬xe )
cfc0 (x) = xb
fd0 (x) = xchd({a, b, c, d, e, h})fe0 (x) = xa
fh0 (x) = xe

15/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Size reduction algorithm

efa0 (x) = xa ∨ xd ∨ ¬xeacfc0 (x) = ¬xafd0 (x) = xcd

fe0 (x) = xa({a, c, d, e})

16/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Size reduction algorithm

acd({a, c, d})fa0 (x) = xa ∨ xd ∨ ¬xc
fc0 (x) = xa
fd0 (x) = ¬xc

17/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Tangential cycles

18/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Tangencial cycles: definitions

Definition
Tangencial cycles are ANs composed of cycles which intersect on a segmentcalled the tangent.
Despite their simple definition, the behavior of tangencial cycles is mostly
not understood.

19/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Tangencial cycles: examples

efa (x) = xa ∨ xd ∨ ¬xhb><<hfb (x) = ¬xa

>

a>

c>
>

>

d({h}, {a, c, d, e}, {b})fc (x) = xb
fd (x) = xc
fe (x) = xa
fh (x) = xe

20/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Tangencial cycles: examples

efa0 (x) = xa ∨ xd ∨ ¬xeac

fc0 (x) = ¬xa
fd0 (x) = xc

dfe0 (x) = xa({a, c, d, e})21/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Tangencial cycles: results

I Bloc sequential tangencial cycles taken through our algorithm always

result in smaller parallel tangencial cycles.
I This implies that a complete characterisation of the parallel case isalso a complete characterisation of the bloc-sequential cases.
For example, the attractors of double disjunctive cycles are characterised inparallel (M. Noual. “Updating Automata Networks”. PhD thesis. École
Normale Supérieure de Lyon, 2012). Our contribution extends this result
to the bloc-sequential case.

22/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

Conclusion

23/24

Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

In conclusion,
I ANs are dynamical systems, we want to understand their limit

behaviour
I We are looking for cases where we can count attractors in polynomialtime
I Counting has nontrivial solutions even in the simplest families we know

In the future,
I We want to find more families that can be counted in polynomial time
I Candidates include intersections of more cycles, and chains of cycles

24/24Biological networks

Automata networks

Parallelisation

Tangential cycles

Conclusion

In conclusion,
I ANs are dynamical systems, we want to understand their limit

behaviour
I We are looking for cases where we can count attractors in polynomialtime
I Counting has nontrivial solutions even in the simplest families we know

In the future,
I We want to find more families that can be counted in polynomial time
I Candidates include intersections of more cycles, and chains of cycles

Thank you!

24/24