Cited By
View all- Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers C(2024)Non-negotiating Distributed ComputingStructural Information and Communication Complexity10.1007/978-3-031-60603-8_12(208-225)Online publication date: 27-May-2024
How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning
Pages 413 - 424
Abstract
In the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e., a three-colored triband, in a distributed manner. To solve a generalized version of the problem in a distributed computational setting, we consider two models: a biologically-inspired version that relies on morphogens (diffusing proteins acting as chemical signals) and a more abstract version based on reliable message passing between cellular agents.
Much of developmental biology research focuses on concentration-based approaches, since morphogen gradients are an underlying mechanism in tissue patterning. We show that both model types easily achieve a French ribbon - a French flag in the 1D case. However, extending the ribbon to the 2D flag in the concentration model is somewhat difficult unless each agent has additional positional information. Assuming that cells are identical, it is impossible to achieve a French flag or even a close approximation. In contrast, using a message-based approach in the 2D case only requires assuming that agents can be represented as logarithmic or constant size state machines.
We hope that our insights may lay some groundwork for what kind of message passing abstractions or guarantees, if any, may be useful in analogy to cells communicating at long and short distances to solve patterning problems. We also hope our models and findings may be of interest in the design of nano-robots.
References
[1]
Afek Y, Alon N, Barad O, Hornstein E, Barkai N, and Bar-Joseph Z A biological solution to a fundamental distributed computing problem Science 2011 331 6014 183-185
[2]
Alberts, B.: Molecular Biology of the Cell. CRC Press, Boca Raton (2017)
[3]
Ancona, A., Bajwa, A., Lynch, N., Mallmann-Trenn, F.: How to color a french flag-biologically inspired algorithms for scale-invariant patterning. arXiv e-prints p. 1905.00342 (2019)
[4]
Dessaud E, McMahon AP, and Briscoe J Pattern formation in the vertebrate neural tube: a sonic hedgehog morphogen-regulated transcriptional network Development 2008 135 15 2489-2503
[5]
Driever W and Nüsslein-Volhard C A gradient of bicoid protein in drosophila embryos Cell 1988 54 1 83-93
[6]
Flajolet P Approximate counting: a detailed analysis BIT 1985 25 1 113-134
[7]
Green JBA and Sharpe J Positional information and reaction-diffusion: two big ideas in developmental biology combine Development 2015 142 7 1203-1211
[8]
Gregor T, Bialek W, van Steveninck RRDR, Tank DW, and Wieschaus EF Diffusion and scaling during early embryonic pattern formation Proc. Natl. Acad. Sci. 2005 102 51 18403-18407
[9]
Habermann, N.: Parallel neighbor-sort (or the glory of the induction principle). Carnegie-Mellon University, Technical report (1972)
[10]
Jaeger J and Martinez-Arias A Getting the measure of positional information PLoS Biol. 2009 7 3 e1000081
[11]
Miller JF Deb K Evolving a self-repairing, self-regulating, french flag organism Genetic and Evolutionary Computation – GECCO 2004 2004 Heidelberg Springer 129-139
[12]
Morgan TH “Polarity” considered as a phenomenon of gradation of materials J. Exp. Zool. 1905 2 495-506
[13]
Morris R Counting large numbers of events in small registers Commun. ACM 1978 21 10 840-842
[14]
Nüsslein-Volhard C and Wieschaus E Mutations affecting segment number and polarity in drosophila Nature 1980 287 5785 795-801
[15]
Patten I and Placzek M The role of sonic hedgehog in neural tube patterning Cellular Molecular Life Sci. CMLS 2000 57 12 1695-1708
[16]
Stumpf HF Mechanism by which cells estimate their location within the body Nature 1966 212 5060 430-431
[17]
Summerbell D, Lewis JH, and Wolpert L Positional information in chick limb morphogenesis Nature 1973 244 5417 492-496
[18]
Turing AM The chemical basis of morphogenesis Philos. Trans. R. Soc. Biol. Sci. 1952 237 641 37-72
[19]
Wolpert L The french flag problem: a contribution to the discussion on pattern development and regulation Towards Theoret. Biol. 1968 1 125-133
[20]
Wolpert L Positional information and the spatial pattern of cellular differentiation J. Theor. Biol. 1969 25 1 1-47
[21]
Zadorin AS et al. Synthesis and materialization of a reaction–diffusion french flag pattern Nat. Chem. 2017 9 10 990-996
Index Terms
- How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning
Index terms have been assigned to the content through auto-classification.
Recommendations
How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning
Structural Information and Communication ComplexityAbstractIn the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e., a three-colored triband, in a distributed manner. To solve a ...
Frankl---Füredi---Kalai Inequalities on the ź-Vectors of Flag Nestohedra
For any flag nestohedron, we define a flag simplicial complex whose f-vector is the ź-vector of the nestohedron. This proves that the ź-vector of any flag nestohedron satisfies the Frankl---Füredi---Kalai inequalities, partially solving a conjecture by ...
Relationships Among Flag f-Vector Inequalities for Polytopes
We examine linear inequalities satisfied by the flag $f$-vectors of polytopes. One source of these inequalities is the toric $g$-vector; convolutions of its entries are non-negative for rational polytopes. We prove a conjecture of Meisinger about a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jan 2021
652 pages
ISBN:978-3-030-61791-2
DOI:10.1007/978-3-030-61792-9
© Springer Nature Switzerland AG 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 05 January 2021
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
Cited By
View all- Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers C(2024)Non-negotiating Distributed ComputingStructural Information and Communication Complexity10.1007/978-3-031-60603-8_12(208-225)Online publication date: 27-May-2024
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in