research-article

Free access

Distributed information processing in biological and computational systems

Authors:

Saket Navlakha,

Ziv Bar-JosephAuthors Info & Claims

Communications of the ACM, Volume 58, Issue 1

Pages 94 - 102

https://doi.org/10.1145/2678280

Published: 23 December 2014 Publication History

All formats PDF

Abstract

Exploring the similarities and differences between distributed computations in biological and computational systems.

References

[1]

Afek, Y. et al. Beeping a maximal independent set. Distributed Computing; Lecture Notes in Computer Science. D. Peleg, Ed. (2011). Springer-Verlag, Berlin Heidelberg, 32--50.

Digital Library

Google Scholar

[2]

Afek, Y. et al. A biological solution to a fundamental distributed computing problem. Science 331, 6014 (2011), 183--185.

Crossref

Google Scholar

[3]

Aida, K., Natsume, W. and Futakata, Y. Distributed computing with hierarchical master-worker paradigm for parallel branch and bound algorithm. In Proceedings of the 31^st International Symposium on Cluster Computing and the Grid. IEEE Computer Society, Washington, DC, 2003.

Digital Library

Google Scholar

[4]

Anastasi, G., Conti, M., Di Francesco, M. and Passarella, A. Energy conservation in wireless sensor networks: A survey. Ad Hoc Netw. 7, 3 (May 2009), 537--568.

Digital Library

Google Scholar

[5]

Angluin, D. Local and global properties in networks of processors (extended abstract). In Proceedings of the 12^th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 1980, 82--93.

Digital Library

Google Scholar

[6]

Aspnes, J. and Ruppert, E. An introduction to population protocols. Middleware for Network Eccentric and Mobile Applications. B. Garbinato, H. Miranda, and L. Rodrigues, Eds. Springer-Verlag, Berlin, Heidelberg, 2009, 97--120.

Google Scholar

[7]

Attiya, H., Bar-Noy, A. and Dolev, D. Sharing memory robustly in message-passing systems. JACM 42, 1 (Jan. 1995), 124--142.

Digital Library

Google Scholar

[8]

Babaoglu, O., Binci, T., Jelasity, M. and Montresor, A. Firefly-inspired heartbeat synchronization in overlay networks. In Proceeding of the First International Conference Self-Adaptive and Self-Organizing Systems (2007), 77--86.

Digital Library

Google Scholar

[9]

Beauquier, J., Blanchard, P., Burman, J. and Delaët, S. Tight complexity analysis of population protocols with cover times--the Zebranet example. Theor. Comput. Sci. 512 (Nov. 2013), 15--27.

Digital Library

Google Scholar

[10]

Bryant, B. Chromatin computation. PLoS ONE 7, 5 (2012), e35703.

Crossref

Google Scholar

[11]

Buesing, L., Bill, J., Nessler, B. and Maass, W. Neural dynamics as sampling: A model for stochastic computation in recurrent networks of spiking neurons. PLoS Comput. Biol. 7, 11 (Nov. 2011), e1002211.

Crossref

Google Scholar

[12]

Bushman, F. et al. Host cell factors in HIV replication: meta-analysis of genome-wide studies. PLoS Pathog. 5, 5 (May 2009), e1000437.

Crossref

Google Scholar

[13]

Cardelli, L. and Csikasz-Nagy, A. The cell cycle switch computes approximate majority. Sci Rep. 2:656 (2012).

Crossref

Google Scholar

[14]

Chazelle, B. Natural algorithms and influence systems. Commun. ACM 55, 12 (Dec. 2012), 101--110.

Digital Library

Google Scholar

[15]

Cheong, R., Rhee, A., Wang, C.J., Nemenman, I. and Levchenko, A. Information transduction capacity of noisy biochemical signaling networks. Science 334, 6054 (Oct. 2011), 354--358.

Crossref

Google Scholar

[16]

Chittka, L., Skorupski, P., and Raine, N.E. Speed-accuracy tradeoffs in animal decision-making. Trends Ecol. Evol. 24, 7 (July 2009), 400--407.

Crossref

Google Scholar

[17]

Cornejo, A. and Kuhn, F. Deploying wireless networks with beeps. In Proceedings of the 24^th International Conference on Distributed Computing (2010). Springer-Verlag, Berlin, Heidelberg, 148--162.

Digital Library

Google Scholar

[18]

Cuntz, H., Forstner, F., Borst, A. and Hausser, M. One rule to grow them all: A general theory of neuronal branching and its practical application. PLoS Comput. Biol. 6, 8 (2010).

Crossref

Google Scholar

[19]

Destexhe, A. and Contreras, D. Neuronal computations with stochastic network states. Science 314, 5796 (Oct. 2006), 85--90.

Crossref

Google Scholar

[20]

Emek, Y. and Wattenhofer, R. Stone age distributed computing. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (2013). ACM, New York, NY, 137--146.

Digital Library

Google Scholar

[21]

Falik, O., Mordoch, Y., Quansah, L., Fait, A. and Novoplansky, A. Rumor has it…: Relay communication of stress cues in plants. PLoS ONE 6, 11 (2011), e23625.

Crossref

Google Scholar

[22]

Feinerman, O. and Korman, A. Theoretical distributed computing meets biology: A review. Distributed Computing and Internet Technology. C. Hota and P. Srimani, Eds. Lecture Notes in Computer Science 7753 (2013), 1--18. Springer-Verlag, Berlin Heidelberg, 1--18.

Crossref

Google Scholar

[23]

Feinerman, O., Korman, A., Lotker, Z. and Sereni, J-S. Collaborative search on the plane without communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (2012). ACM, New York, NY, 77--86.

Digital Library

Google Scholar

[24]

Gitter, A. et al. Backup in gene regulatory networks explains differences between binding and knockout results. Mol. Syst. Biol. 5, 276 (2009).

Crossref

Google Scholar

[25]

Gupta, I., Chandra, T.D., and Goldszmidt, G.S. On scalable and efficient distributed failure detectors. In Proceedings of the 20^th Annual ACM Symposium on Principles of Distributed Computing (2001). ACM, New York, NY, 170--179.

Digital Library

Google Scholar

[26]

Hsiao, T.L. and Vitkup, D. Role of duplicate genes in robustness against deleterious human mutations. PLoS Genet. 4, 3 (Mar. 2008), e1000014.

Crossref

Google Scholar

[27]

Hu, T., Genkin, A. and Chklovskii, D.B. A network of spiking neurons for computing sparse representations in an energy-efficient way. Neural Comput 24, 11 (Nov. 2012), 2852--2872.

Digital Library

Google Scholar

[28]

Hu, Z. and Li, B. Fundamental performance limits of wireless sensor networks. Ad Hoc and Sensor Networks (2004), 81--101.

Google Scholar

[29]

Ioannou, C.C., Guttal, V. and Couzin, I.D. Predatory fish select for coordinated collective motion in virtual prey. Science 337, 6099 (Sept. 2012), 1212--1215.

Google Scholar

[30]

Jakovcevski, M. and Akbarian, S. Epigenetic mechanisms in neurological disease. Nat. Med. 18, 8 (Aug. 2012), 1194--1204.

Crossref

Google Scholar

[31]

Jongeneel, C.V. et al. An atlas of human gene expression from massively parallel signature sequencing (MPSS). Genome Res 15, 7 (July 2005), 1007--1014.

Crossref

Google Scholar

[32]

Kitano, H. and Oda, K. Robustness trade-offs and host-microbial symbiosis in the immune system. Mol. Syst. Biol. 2:2006.0022 (2006).

Crossref

Google Scholar

[33]

Kuhn, F., Lynch, N., and Oshman, R. Distributed computation in dynamic networks. In Proceedings of the 42^nd ACM Symposium on Theory of Computing (2010). ACM, New York, NY, 513--522.

Digital Library

Google Scholar

[34]

Levy, S., Kafri, M. Carmi, M. and Barkai, N. The competitive advantage of a dual-transporter system. Science 334, 6061 (Dec. 2011), 1408--1412.

Crossref

Google Scholar

[35]

Li, K., Thomas, K., Torres, C., Rossi, L. and Shen, C-C. Slime mold inspired path formation protocol for wireless sensor networks. In Proceedings of the 7^th International Conference on Swarm Intelligence (2010). Springer-Verlag, Berlin, Heidelberg, 299--311.

Digital Library

Google Scholar

[36]

Luby, M. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the 17^th Annual ACM Symposium on Theory of Computing (1985). ACM, New York, NY, 1--10.

Digital Library

Google Scholar

[37]

Lynch, N.A. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA, 1996.

Digital Library

Google Scholar

[38]

Mehta, P. and Schwab, D.J. Energetic costs of cellular computation. In Proceedings of the Natl. Acad. Sci. 109, 44 (Oct. 2012), 17978--17982.

Crossref

Google Scholar

[39]

Métivier, Y., Robson, J., Saheb-Djahromi, N. and Zemmari, A. An optimal bit complexity randomized distributed mis algorithm. Distributed Computing 23, 5-6 (2011), 331--340.

Digital Library

Google Scholar

[40]

Milo, R. et al. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (Oct. 2002), 824--827.

Crossref

Google Scholar

[41]

Mittal, P. and Borisov, N. Information leaks in structured peer-to-peer anonymous communication systems. In Proceedings of the Conf. on Computer and Communications Security (2008), ACM, New York, NY, 267--278.

Digital Library

Google Scholar

[42]

Navlakha, S. and Bar-Joseph, Z. Algorithms in nature: The convergence of systems biology and computational thinking. Mol. Syst. Biol. 7:546 (2011).

Crossref

Google Scholar

[43]

Navlakha, S., He, X., Faloutsos, C. and Bar-Joseph, Z. Topological properties of robust biological and computational networks. J R Soc Interface 11, 96 (2014).

Crossref

Google Scholar

[44]

Nusser-Stein, S. et al. Cell-cycle regulation of NOTCH signaling during C. elegans vulval development. Mol. Syst. Biol. 8:618 (2012).

Crossref

Google Scholar

[45]

Pecevski, D., Buesing, L. and Maass, W. Probabilistic inference in general graphical models through sampling in stochastic networks of spiking neurons. PLoS Comput. Biol. 7, 12 (Dec. 2011), e1002294.

Crossref

Google Scholar

[46]

Prabhakar, B., Dektar, K.N., and Gordon, D.M. The regulation of ant colony foraging activity without spatial information. PLoS Comput. Biol. 8, 8 (2012), e1002670.

Crossref

Google Scholar

[47]

Price, M.N. et al. Indirect and suboptimal control of gene expression is widespread in bacteria. Mol. Syst. Biol. 9:600, (2013).

Crossref

Google Scholar

[48]

Reid, C.R., Latty, T., Dussutour, A., and Beekman, M. Slime mold uses an externalized spatial "memory" to navigate in complex environments. In Proceedings of the Natl. Acad. Sci. 109, 43 (Oct. 2012), 17490--17494.

Crossref

Google Scholar

[49]

Scott, A., Jeavons, P., and Xu, L. Feedback from nature: An optimal distributed algorithm for maximal independent set selection. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing. ACM, New York, NY, 147--156.

Digital Library

Google Scholar

[50]

Shklarsh, A., Ariel, G., Schneidman, E. and Ben-Jacob, E. Smart swarms of bacteria-inspired agents with performance adaptable interactions. PLoS Comput. Biol. 7, 9 (Sept. 2011), e1002177.

Crossref

Google Scholar

[51]

Tang, J., Xue, G., Chandler, C., and Zhang, W. Interference-aware routing in multihop wireless networks using directional antennas. In Proceedings of the 24^th Annual Joint Conference of the IEEE Computer and Communications Societies (2005). IEEE, 751--760.

Google Scholar

[52]

Tero, A. et al. Rules for biologically inspired adaptive network design. Science 327, 5964 (2010), 439--442.

Crossref

Google Scholar

[53]

Tyson, J.J., Chen, K.C., and Novak, B. Sniffers, buzzers, toggles and blinkers: dynamics of regulatory and signaling pathways in the cell. Curr. Opin. Cell Biol. 15, 2 (Apr. 2003), 221--231.

Crossref

Google Scholar

[54]

Wakefield, E.D. et al. Space partitioning without territoriality in gannets. Science 341, 6141 (July 2013), 68--70.

Crossref

Google Scholar

[55]

Yu, H. and Gerstein, M. Genomic analysis of the hierarchical structure of regulatory networks. In Proceedings of the Natl. Acad. Sci. 103, 40 (Oct. 2006), 14724--14731.

Crossref

Google Scholar

[56]

Yu, H., Kim, P.M., Sprecher, E., Trifonov, V. and Gerstein, M. The importance of bottlenecks in protein networks: Correlation with gene essentiality and expression dynamics. PLoS Comput. Biol. 3, 4 (Apr. 2007), e59.

Crossref

Google Scholar

[57]

Zhong, Q. et al. Edgetic perturbation models of human inherited disorders. Mol. Syst. Biol. 5, 321 (2009).

Crossref

Google Scholar

Cited By

View all

Shaikhutdinov RMun GKopishev EBakirov AKabdushev SBaipakbaeva SSuleimenov I(2024)Effect of the Formation of Hydrophilic and Hydrophobic–Hydrophilic Associates on the Behavior of Copolymers of N-Vinylpyrrolidone with Methyl Acrylate in Aqueous SolutionsPolymers10.3390/polym1605058416:5(584)Online publication date: 21-Feb-2024
https://doi.org/10.3390/polym16050584
Függer MNowak TRybicki JKuznetsov PGelles ROlivetti D(2024)Majority Consensus Thresholds in Competitive Lotka-Volterra PopulationsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662823(76-86)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662823
Fabris MBellinazzi MFurlanetto ACenedese A(2024)Adaptive Consensus-Based Reference Generation for the Regulation of Open-Channel NetworksIEEE Access10.1109/ACCESS.2024.335772212(14423-14436)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3357722
Show More Cited By

Index Terms

Distributed information processing in biological and computational systems

Recommendations

Computational Electrostatics for Biological Applications: Geometric and Numerical Approaches to the Description of Electrostatic Interaction Between Macromolecules
Computational enzyme design
Synthesis, biological evaluation and molecular docking studies of novel benzimidazole derivatives

Display Omitted Novel synthesized compounds were found to have inhibitory potential against -amylase and -glucosidase.Docking Studies were carried out in the active site of the -glucosidase protein (PDB code: 3TOP) using SYBYL 7.3 software.Docking ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 58, Issue 1

January 2015

105 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2688498

Editor:
Moshe Y. Vardi
Association for Computing Machinery, New York, NY

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 December 2014

Published in CACM Volume 58, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
26,131
Total Downloads

Downloads (Last 12 months)329
Downloads (Last 6 weeks)39

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shaikhutdinov RMun GKopishev EBakirov AKabdushev SBaipakbaeva SSuleimenov I(2024)Effect of the Formation of Hydrophilic and Hydrophobic–Hydrophilic Associates on the Behavior of Copolymers of N-Vinylpyrrolidone with Methyl Acrylate in Aqueous SolutionsPolymers10.3390/polym1605058416:5(584)Online publication date: 21-Feb-2024
https://doi.org/10.3390/polym16050584
Függer MNowak TRybicki JKuznetsov PGelles ROlivetti D(2024)Majority Consensus Thresholds in Competitive Lotka-Volterra PopulationsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662823(76-86)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662823
Fabris MBellinazzi MFurlanetto ACenedese A(2024)Adaptive Consensus-Based Reference Generation for the Regulation of Open-Channel NetworksIEEE Access10.1109/ACCESS.2024.335772212(14423-14436)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3357722
Chen JGuo XCharbonneau DAzizi AFewell JKang Y(2024)Dynamics of Information Flow and Task Allocation of Social Insect Colonies: Impacts of Spatial Interactions and Task SwitchingBulletin of Mathematical Biology10.1007/s11538-024-01280-686:5Online publication date: 6-Apr-2024
https://doi.org/10.1007/s11538-024-01280-6
Garg SShiragur KGordon DCharikar M(2023)Distributed algorithms from arboreal ants for the shortest path problemProceedings of the National Academy of Sciences10.1073/pnas.2207959120120:6Online publication date: 30-Jan-2023
https://doi.org/10.1073/pnas.2207959120
Patitz M(2023)Implementing a Theoretician’s Toolkit for Self-Assembly with DNA ComponentsVisions of DNA Nanotechnology at 40 for the Next 4010.1007/978-981-19-9891-1_14(241-269)Online publication date: 5-Jul-2023
https://doi.org/10.1007/978-981-19-9891-1_14
Chatterjee SYadav S(2022)The Coevolution of Biomolecules and Prebiotic Information Systems in the Origin of Life: A Visualization Model for Assembling the First GeneLife10.3390/life1206083412:6(834)Online publication date: 2-Jun-2022
https://doi.org/10.3390/life12060834
Taubenfeld G(2022)Anonymous Shared MemoryJournal of the ACM10.1145/352975269:4(1-30)Online publication date: 16-Aug-2022
https://dl.acm.org/doi/10.1145/3529752
Suen JNavlakha S(2022)A feedback control principle common to several biological and engineered systemsJournal of The Royal Society Interface10.1098/rsif.2021.071119:188Online publication date: 2-Mar-2022
https://doi.org/10.1098/rsif.2021.0711
Raynal MTaubenfeld G(2022)A visit to mutual exclusion in seven datesTheoretical Computer Science10.1016/j.tcs.2022.03.030919(47-65)Online publication date: Jun-2022
https://doi.org/10.1016/j.tcs.2022.03.030
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF Chinese translation

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Computational Electrostatics for Biological Applications: Geometric and Numerical Approaches to the Description of Electrostatic Interaction Between Macromolecules

Computational enzyme design

Synthesis, biological evaluation and molecular docking studies of novel benzimidazole derivatives

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Digital Edition

Magazine Site

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations