基于生物细胞的膜计算模型研究_生物科学

1

内容提要

膜计算旨在从生物细胞中抽象计算模型，具有良好的分布式结构和强大的并行性。本书是基于生物学中的细胞进化机制，以形式语言与自动机理论为基础，重点研究建立更加符合生物...

2

前　言

膜系统也称为P系统，是一类分布式并行计算模型，由欧洲科学院院士Gheorghe Pǎun于1998年提出，正式论文于2000年发表。2003年，美国科学情报研究...

3

第1章　绪　论

本章首先从实现计算机的计算模型出发，概述膜计算研究背景、意义，包括膜计算的国内外研究现状以及本书涉及的几类膜计算模型。接着，对膜计算中的相关定义和概念等内容进行...

5

1.1　概述

人类在漫长的历史中不断寻找一种智能的机器来实现计算。最早，人们使用手工计算，例如古代罗马人使用石子来计数；在我国，上千年前就发明了算盘作为计算工具，用该工具计算...

6

1.2　研究进展

本节从膜计算发展历程出发，简单介绍膜计算的研究现状，对相关膜计算模型进行重点说明和具体描述。...

7

1.2.1　膜计算简介

人体的构造是非常奇妙的，即使通过最先进的科技手段，也未能完全了解其中的奥秘。但人类机体活动又具有复杂而协调的动作：头脑作为总部的办公处，传达着各种复杂的命令；皮...

8

1.2.2　膜计算模型介绍

下面就本书涉及的两类膜系统（类细胞膜系统和类组织膜系统）做简单介绍。 1.2.2.1　类细胞膜系统类细胞膜系统主要包括转移P系统、转运P系统和活性膜P系统等。...

9

1.3　膜计算中的相关定义及概念

本节内容主要对膜计算中涉及的相关定义和概念，如描述膜计算模型的形式语言、证明计算通用性的注册机以及涉及鲁棒膜系统的时间无关概念进行概述。...

10

1.3.1　形式语言与注册机

一个有穷非空的字符集合V称为字母表。字母表中的元素称为字符。V中一个长度有限的序列称为一个字符串。不含任何字符的空串记为λ。来自V的所有字符串记为V*；来自V中...

11

1.3.2　时间无关模式

生物实际对应膜系统有三个重要的组成要素：膜结构、对象多重集以及进化规则。作为最核心的要素进化规则，标准膜系统中都假定其中每条规则的执行时间为一个单位时间。也就是...

12

1.3.3　时间无关模式下求解NP难问题

定义1.5：对于一个二元组的判定性问题X＝（IX，θX），IX是有限字母表上的一个语言，它的元素称为例子。θX是IX上的全局布尔函数。Π＝｛Π（n）|n∈N｝表...

13

1.4　计算复杂性

一般说来，证明一个算法的正确性，通常要使用形式化证明方法和推理证明。而其中一个重要工作就是分析算法的复杂度。在计算机科学研究领域，计算复杂性理论中的时间复杂度反...

14

1.5　膜算法

目前，膜计算应用研究中发展得最好的领域是采用膜系统设计优化算法（也称为膜算法）求解实际应用中的问题［38］。与其他从生物行为和生物特征中抽象出智能算法一样，膜算...

15

参考文献

［1］Turing A.On computable numbers，with an application to the entscheidungs probl...

16

第2章　基于促进剂的时间活性膜P系统

活性膜P系统作为一类受生物启发的计算模型，其中的每条规则在系统运行过程中都具有相同的执行时间。基于该模型，SAT问题获得了有效求解［1-5］。另外，有学者提出一...

17

2.1　基于促进剂的时间活性膜P系统构建

在本章中我们提出了时间活性膜P系统的一个新变体，将其称为基于促进剂的时间活性膜P系统。在该系统中，规则的执行可以通过膜中的促进剂进行调控。另外，原始的活性膜P系...

18

2.2　基于促进剂的时间活性膜P系统求解SAT问题半统一解

定义2.3：SAT问题可简单表述为，给定一个CNF的布尔公式，判定是否存在一组变量赋值使得该布尔公式的值为真。众所周知，SAT问题是一个NP完全问题，包含n个...

19

2.3　基于促进剂的时间活性膜P系统求解SAT问题统一解

定理2.2：SAT问题可以通过一族膜上仅带有两类电荷、使用促进剂的时间活性膜P系统且具有a、b、c、e类规则在多项式RS步内通过膜分裂以统一方式解决。证明：对...

20

2.4　系统计算效率分析

在以上基于促进剂的时间活性膜P系统对SAT问题采用半统一和统一的方法进行求解后，本小节将分别对半统一方法和统一方法的计算效率进行分析，指出系统使用的计算资源，并...

21

2.4.1　半统一方法

对于具有n个变量和m个子句的SAT问题，构造ΠSAT-semi（m，n）半统一算法的必要资源可以表示如下。（1）物质的数量：2m＋5n＋3；（2）初始膜的数...

22

2.4.2　统一方法

对于具有n个变量和m个子句的SAT问题，构造ΠSAT-uniform（m，n）的统一算法必要资源可以表示如下：（1）物质的数量：7mn＋2m＋4n＋3；（2...

23

2.5　基于促进剂的时间活性膜P系统通用性证明

下面，通过模拟注册机证明基于促进剂的时间活性膜P系统是计算通用的，即计算能力与图灵机等价或不低于图灵机。定理2.3：证明：注册机的指令包括加法指令、减法指令...

24

参考文献

［1］Leporati A，Mauri G，Zandron C，et al.Uniform solutions to SAT and subset sum by...

25

第3章　膜上带蛋白的时间膜系统

活细胞内的很多生化反应会受到细胞膜上蛋白质的控制。受该生物过程启发，A.Pǎun等于2006年首次提出膜上带蛋白的膜系统［1］。作为类细胞膜系统中的一种变体，该...

26

3.1　膜上带蛋白的时间膜系统模型

定义3.1：在时间无关模式下，一个膜上带蛋白的识别膜系统可以定义成如下的形式：其中，O表示对象的字母表；P表示膜上蛋白质的字母表（O∩P＝Ø）；Σ⊆O表示输...

27

3.2　膜上带蛋白的时间膜系统求解SAT问题

定理3.1：SAT问题可以通过一族膜上带蛋白的时间膜系统使用a、c、d，以及f类规则在多项式RS步内通过基本膜分裂以统一的方式解决。证明：对于具有n个布尔变量...

28

3.3　触发型膜上带蛋白的时间膜系统求解SAT问题

在定义1.2中，膜上每种蛋白质的可达状态并没有做任何限定，即在系统计算过程中每种蛋白质的可达状态可能是无限多个。下面考虑触发型蛋白膜系统（膜上每一类蛋白质仅有两...

29

参考文献

［1］Pǎun A，Pǎun B.P systems with proteins on membranes［J］.International Journal o...

30

第4章　基于细胞分裂的类组织时间膜系统计算效率

类组织膜系统是一类受细胞之间物质交流启发而形成的生物计算系统。受到细胞可以通过有丝分裂进行繁殖的生物实际启发，文献［1］首次提出基于细胞分裂的类组织膜系统，可以...

《基于生物细胞的膜计算模型研究》简介

内容提要

前　言

目录

第1章　绪　论

1.1　概述

1.2　研究进展

1.2.1　膜计算简介

1.2.2　膜计算模型介绍

1.3　膜计算中的相关定义及概念

1.3.1　形式语言与注册机

1.3.2　时间无关模式

1.3.3　时间无关模式下求解NP难问题

1.4　计算复杂性

1.5　膜算法

参考文献

第2章　基于促进剂的时间活性膜P系统

2.1　基于促进剂的时间活性膜P系统构建

2.2　基于促进剂的时间活性膜P系统求解SAT问题半统一解

2.3　基于促进剂的时间活性膜P系统求解SAT问题统一解

2.4　系统计算效率分析

2.4.1　半统一方法

2.4.2　统一方法

2.5　基于促进剂的时间活性膜P系统通用性证明

参考文献

第3章　膜上带蛋白的时间膜系统

3.1　膜上带蛋白的时间膜系统模型

3.2　膜上带蛋白的时间膜系统求解SAT问题

3.3　触发型膜上带蛋白的时间膜系统求解SAT问题

参考文献

第4章　基于细胞分裂的类组织时间膜系统计算效率

《基于生物细胞的膜计算模型研究》简介

内容提要

前 言

目录

第1章 绪 论

1.1 概述

1.2 研究进展

1.2.1 膜计算简介

1.2.2 膜计算模型介绍

1.3 膜计算中的相关定义及概念

1.3.1 形式语言与注册机

1.3.2 时间无关模式

1.3.3 时间无关模式下求解NP难问题

1.4 计算复杂性

1.5 膜算法

参考文献

第2章 基于促进剂的时间活性膜P系统

2.1 基于促进剂的时间活性膜P系统构建

2.2 基于促进剂的时间活性膜P系统求解SAT问题半统一解

2.3 基于促进剂的时间活性膜P系统求解SAT问题统一解

2.4 系统计算效率分析

2.4.1 半统一方法

2.4.2 统一方法

2.5 基于促进剂的时间活性膜P系统通用性证明

参考文献

第3章 膜上带蛋白的时间膜系统

3.1 膜上带蛋白的时间膜系统模型

3.2 膜上带蛋白的时间膜系统求解SAT问题

3.3 触发型膜上带蛋白的时间膜系统求解SAT问题

参考文献

第4章 基于细胞分裂的类组织时间膜系统计算效率

前　言

第1章　绪　论

1.1　概述

1.2　研究进展

1.2.1　膜计算简介

1.2.2　膜计算模型介绍

1.3　膜计算中的相关定义及概念

1.3.1　形式语言与注册机

1.3.2　时间无关模式

1.3.3　时间无关模式下求解NP难问题

1.4　计算复杂性

1.5　膜算法

第2章　基于促进剂的时间活性膜P系统

2.1　基于促进剂的时间活性膜P系统构建

2.2　基于促进剂的时间活性膜P系统求解SAT问题半统一解

2.3　基于促进剂的时间活性膜P系统求解SAT问题统一解

2.4　系统计算效率分析

2.4.1　半统一方法

2.4.2　统一方法

2.5　基于促进剂的时间活性膜P系统通用性证明

第3章　膜上带蛋白的时间膜系统

3.1　膜上带蛋白的时间膜系统模型

3.2　膜上带蛋白的时间膜系统求解SAT问题

3.3　触发型膜上带蛋白的时间膜系统求解SAT问题

第4章　基于细胞分裂的类组织时间膜系统计算效率