How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning
© 2020, Springer Nature Switzerland AG. 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 versio...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137574 |
| _version_ | 1811082212749082624 |
|---|---|
| author | Ancona, B Bajwa, A Lynch, N Mallmann-Trenn, F |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ancona, B Bajwa, A Lynch, N Mallmann-Trenn, F |
| author_sort | Ancona, B |
| collection | MIT |
| description | © 2020, Springer Nature Switzerland AG. 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. |
| first_indexed | 2024-09-23T11:59:30Z |
| format | Article |
| id | mit-1721.1/137574 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:59:30Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1375742023-06-22T18:47:17Z How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning Ancona, B Bajwa, A Lynch, N Mallmann-Trenn, F Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2020, Springer Nature Switzerland AG. 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. 2021-11-05T18:43:11Z 2021-11-05T18:43:11Z 2020 2021-01-29T14:39:45Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137574 Ancona, B, Bajwa, A, Lynch, N and Mallmann-Trenn, F. 2020. "How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12118 LNCS. en 10.1007/978-3-030-61792-9_33 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing arXiv |
| spellingShingle | Ancona, B Bajwa, A Lynch, N Mallmann-Trenn, F How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title | How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title_full | How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title_fullStr | How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title_full_unstemmed | How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title_short | How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning |
| title_sort | how to color a french flag biologically inspired algorithms for scale invariant patterning |
| url | https://hdl.handle.net/1721.1/137574 |
| work_keys_str_mv | AT anconab howtocolorafrenchflagbiologicallyinspiredalgorithmsforscaleinvariantpatterning AT bajwaa howtocolorafrenchflagbiologicallyinspiredalgorithmsforscaleinvariantpatterning AT lynchn howtocolorafrenchflagbiologicallyinspiredalgorithmsforscaleinvariantpatterning AT mallmanntrennf howtocolorafrenchflagbiologicallyinspiredalgorithmsforscaleinvariantpatterning |