Amorphous computation, random graphs and complex biological networks

非晶计算、随机图和复杂生物网络

• 批准号: EP/D00232X/1
• 负责人: Netta Cohen
• 金额: $ 78.09万
• 依托单位: University of Leeds
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2006
• 资助国家: 英国
• 起止时间: 2006 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FD00232X%2F1
• 关键词: Amorphous; computation; random; graphs; complex

In this ``information age'', computation, communication and massive information handling have become the bread and butter of modern society. Internet networks, the web, and popular peer-to-peer networks are all examples of the transition we are witnessing from local, centralised computers to massive distributed networks of relatively low-power individual resources. These are our first glimpses of the amorphous computers of the future. More generally, amorphous computers include any large-scale network of computational units or processes that are connected through a flexible and constantly changing network of interactions. These may be swarms of microscopic robots or large sensor-arrays that monitor climate or pollution. The critically important feature common to these kinds of self-organising distributed systems is that the desired computation emerges and is not explicitly preprogrammed.The transition to amorphous computing brings with it enormous potential as well as risk (such as the virus epidemics that plague the internet). To exploit the advantages and avoid the dangers of amorphous computing, fundamentally new ways of coping with complexity are needed. To do so we plan to develop appropriate mathematical models and tools, on the one hand, and to derive appropriate engineering principles inspired by successful systems, on the other.One of the unifying features of amorphous computers is their active network structure. Thus, a natural mathematical entity for their description is the graph: a structure with nodes (processors) and edges (connections). Since by their very nature, the network structure of amorphous computers is non-prescribed, the study of random graphs is especially promising. To extend the theory of random graphs to real-world applications, new mathematics needs to be developed, including new families of random graphs, new tools for simulating their growth and dynamics and new methods for analysing the dynamics that takes place on these graphs. A key part of this proposal is the development of these tools and their application to specific models of amorphous computers, and ultimately to real systems (such as P2P networks and sensor arrays).One of the challenges of amorphous computing is to find useful analogies that provide insight into the requirements, capabilities and limitations of the systems at hand. In this proposal, we will draw inspiration from biological systems and the powerful computation they perform. Computational aspects of biological functions are found in almost any task: from evolution, though development, to information processing, and are evident on every level of organisation, including macro-molecules (e.g., protein folding), cells (e.g., regulatory networks of proteins and genes) and higher (neural networks and nervous systems). Built of microscopic, noisy and relatively unreliable components, biological systems are surprisingly effective and efficient. Unlike human-engineered computers, they are also dynamic and highly adaptive machines. They are typically distributed and decentralised, with each component following a set of local rules based on its environment to determine its actions. It is the emergence of a functional and coherent whole from an ensemble of simple and unreliable elements that we would like to capture for our own engineering purposes.

在这个“信息时代”，计算、通信和海量信息处理已成为现代社会的面包和黄油。互联网、万维网和流行的点对点网络都是我们目睹的从本地集中式计算机向功耗相对较低的单个资源的大规模分布式网络转变的例子。这是我们第一次看到未来的非晶态计算机。更一般地，无定形计算机包括通过灵活且不断变化的交互网络连接的计算单元或进程的任何大规模网络。这些可能是一群微型机器人或监测气候或污染的大型传感器阵列。这些类型的自组织分布式系统的共同的极其重要的特征是所需的计算出现并且没有明确地预先编程。向非晶计算的过渡带来了巨大的潜力和风险（例如困扰互联网的病毒流行） ）。为了利用非晶计算的优势并避免其危险，需要从根本上解决复杂性的新方法。为此，我们计划一方面开发适当的数学模型和工具，另一方面从成功系统的启发中推导出适当的工程原理。非晶计算机的统一特征之一是它们的主动网络结构。因此，描述它们的自然数学实体是图：具有节点（处理器）和边（连接）的结构。由于非晶计算机的网络结构本质上是非规定的，因此随机图的研究特别有前途。为了将随机图理论扩展到现实世界的应用，需要开发新的数学，包括新的随机图族、模拟其增长和动态的新工具以及分析这些图上发生的动态的新方法。该提案的关键部分是开发这些工具及其在非晶计算机特定模型中的应用，并最终应用于真实系统（例如 P2P 网络和传感器阵列）。非晶计算的挑战之一是找到有用的类比深入了解现有系统的要求、功能和限制。在这个提案中，我们将从生物系统及其执行的强大计算中汲取灵感。生物功能的计算方面几乎存在于任何任务中：从进化、发展到信息处理，并且在组织的各个层面上都很明显，包括大分子（例如蛋白质折叠）、细胞（例如蛋白质调控网络）和基因）和更高层次（神经网络和神经系统）。生物系统由微观、嘈杂且相对不可靠的组件组成，其效果和效率令人惊讶。与人类设计的计算机不同，它们也是动态且高度自适应的机器。它们通常是分布式和去中心化的，每个组件都遵循一组基于其环境的本地规则来确定其操作。它是从一组简单且不可靠的元素中出现的一个功能性且连贯的整体，我们希望将其捕获用于我们自己的工程目的。

项目成果

The Flip Markov Chain and a Randomising P2P Protocol

翻转马尔可夫链和随机 P2P 协议

• 发表时间: 2009
• 作者: Colin Cooper

COMPETITION AND THE DYNAMICS OF GROUP AFFILIATION

竞争和团体归属的动态

• DOI: http://dx.10.1142/s0219525910002712
• 发表时间: 2011
• 期刊: Advances in Complex Systems
• 影响因子: 0.4
• 作者: GEARD N

Developmental motifs reveal complex structure in cell lineages

发育图案揭示细胞谱系的复杂结构

• DOI: 10.1002/cplx.20341
• 发表时间: 2011-03-01
• 期刊: Complex.
• 作者: N. Geard;S. Bullock;Rolf Lohaus;R. B. Azevedo;Janet Wiles
• 通讯作者: Janet Wiles

Fluctuations, pauses, and backtracking in DNA transcription.

DNA 转录的波动、暂停和回溯。

• DOI: 10.1529/biophysj.107.105767
• 发表时间: 2008-01-15
• 期刊: Biophysical journal
• 影响因子: 3.4
• 作者: M. Voliotis;N. Cohen;C. Molina‐París;T. Liverpool
• 通讯作者: T. Liverpool

The flip Markov chain for connected regular graphs

用于连通正则图的翻转马尔可夫链

• DOI: http://dx.10.1016/j.dam.2018.06.019
• 发表时间: 2019
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Cooper C