（分析化学专业论文）复杂网络理论和细胞自动机在生物信息学中的应用研究.pdf

四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研塞 摘要 复杂网络理论和细胞自动机在生物信息学中的 7 应用研究 分析化学专业 博士生刁元波指导教师李梦龙教授 随着生命科学和生物技术的迅猛发展，生物信息数据资源的增长呈现爆炸 之势，同时计算机运算能力的提高和国际互联网络的发展使得对大规模数据的 贮存、处理和传输成为可能，为了快捷方便地对己知生物学信息进行科学的组 织、有效的管理和进一步分析利用，一门由生命科学和信息科学等多学科相结 合特别是由分子生物学与计算机信息处理技术紧密结合而形成的交叉学科 生物信息学( b i o i n f o r m a t i c s ) 应运而生，并大大推动了相关研究的开展。 生物信息学自产生以来大致经历了前基因组时代、基因组时代和后基因组 时代三个发展阶段。前基因组时代的标志性工作包括生物数据库的建立、检索 工具的开发以及d n a 和蛋白质序列分析等；基因组时代的标志性工作包括基因 识别与发现、网络数据库系统的建立和交互界面工具的开发等；后基因组时代 的标志则是大规模基因组分析、蛋白质组分析以及各种数据的比较与整合。本 文尝试把复杂理论引入生物信息学领域，针对后基因组时代的几个重要问题进 行了探讨，并得到了有意义的结果。 复杂系统的典型特征是非线性，也可理解为“整体大于部分之和”。这种非 线性的分子基础在于各种生物大分子，基因及蛋白质之间频繁而复杂的相互作 用。在大多数情况下，这些生物大分子并非独立完成其功能，而是以物理或化 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 学方式有着直接或间接的相互作用。这些相互作用产生了各种各样的生物网络， 例如代谢网络，基因调控网络和信号转导网络等等。可以认为，所有的生命活 动都依赖于这些生物网络的结构和功能。 其中，生物网络的构建是网络静态统计分析、动态分析、重要节点分析、 网络调控策略发现、数值实验和仿真等工作开展的基础。本文使用简单对象传 输协议( s o a p ) ，从网络数据库跹g g 提供的网络服务( w e bs e r v i c e ) 获取细胞 信号转导数据，然后把它们转换成邻接矩阵，使用相关矩阵运算，最后构建了 人类的细胞信号网络的无向图，一共包括9 3 1 个节点，6 7 9 8 条边。对其的静态 几何分析结果表明，它不是一个随机网络，而是一个无尺度网络，其度分布符 合幂律分布p ( k 卜k _ f ，幂指数 r 大约为2 2 。 鉴于本文构建的细胞信号网络不是一个随机网络，为了搜索其中存在的有 意义的社区结构，我们比较了以层次聚类算法为代表的聚集算法、以g i r v a n n e w m a n ( g n ) 算法为代表的分离算法和o u i m c r a 的模拟退火算法。结果表明， 传统的聚集算法适用范围最小，可靠程度最低，准确性也最差，而模拟退火算 法在适用范围、可靠程度和准确性方面均显著优于其余两种算法。因此本文选 用模拟退火算法研究了细胞信号网络的拓扑结构，并讨论了具体社区结构的生 物意义及其在基础研究和药物设计方面的潜在影响。 本文的第二部分使用细胞自动机构建了生物序列的离散模型，对细胞信号 网络中具有关键作用的跨膜蛋白进行了拓扑结构预测。细胞自动机是d 维空间 中一组细胞单元组成的阵列，每个细胞单元处于状态空间中的某种状态，各细 胞单元下一时刻的转移状态根据相应的邻域函数规则和各时间阶的领域状态配 置进行更新。本文构建了一种基于细胞自动机的新方法用来预测跨膜蛋白的拓 扑结构。首先，根据a 螺旋和b 一圆桶类跨膜蛋白的结构特征确定了滑动窗口 的长度为2 0 个氨基酸残基，然后把扫描蛋白质序列所得到的片段根据优化的二 进制编码规则转化成o l 序列，再用细胞自动机来推导伪氨基酸组成；最后，使 用扩大的协方差判别算法来预测跨膜蛋白的拓扑结构。所得结果表明本方法能 够同时对a 螺旋和b 一圆桶类跨膜蛋白进行预测，并能在j a c k - k n i f e 交叉验证下 取得较高的准确率，明显优于h m m t o p 、t m p r c d 和p k e d - t m b b 这3 种跨膜 蛋白预测算法。另外，本方法只需要输入蛋白质的一级序列，不用额外输入参 数、注释和序列比对信息，非常适合于大规模、高遁量、自动化的基因组搜索 i 四) t i 大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 和注释工作。同时，这种方法也可用于提高蛋白质其他许多特征的预测精度， 如亚细胞定位，酶家族分类，三级结构预测等。 关键词：复杂系统无尺度网络信息理论细胞自动机细胞信号网络 m 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 a b s t r a c t s t u d yo na p p l i c a t i o n so fc o m p l e xn e t w o r ka n d c e l l u l a ra u t o m a t ai nb i o i n f o r m a t i c s m a j o ra n a l y t i c a lc h e m i s t r y d o c t o r a lc a n d i d a t ed i a oy u a n b o s u p e r v i s o r p m f l im e n g l o n g a l o n g w i t ht h e r a p i dd e v e l o p m e n t o fm o d e r n b i o l o g i c a lt e c h n i q u e s ， b i o i n f o n n a t i ed a t aa n dh 嚣a 田缁i n c r e a s ea te x p l o s i o ns p e e d m e a n w h i l e , t h e i m p r o v e m e n to f c o m p u t a t i o nc a p a b i l i t ya n dd e v e l o p m e n to f w o r l d - w i d e - w e bm a ：k ci t p o s s i b l ef o rt h ep r e s e r v a t i o n , d i s p o s a la n dt r a n s m i s s i o no f m a s sd a t a f o rt h er a t i o n a l o r g a n i z a t i o n , e f f e c t i v em a n a g e m e n ta n df u r t h e ru t i l i z a t i o no fk n o w nb i o l o g i c a l i n f o r m a t i o n s ，ad i s c i p l i n ei n t e r c r o s s e db yl i f es c i e n c ea n di n f o r m a t i o ns c i e n c ec o m e s i n t ob e i n ga n dg r e a t l yp r o m o t e sr e l e v a n tr e s e a r c hf r o mm o l e c u l a rb i o l o g ya n d c o m p u t e r - b a s e di n f o r m 蜘m a n a g et e c h n i q u e f r o mi t sb o r n ，b i o i n f o r m a t i c se x p e r i c n c c st h r e ee r a sn a m e db e f o r e - g e n o m i ce r a , g e n o m i c 啪a n dp o s t - g e n o m i ce r a , r e s p e c t i v e l y 1 h er e p r e s e n t a t i v ew o r ko f b e f o r e g e n o m i c e r a c o m p r i s e s t h ef o u n d a t i o no f b i o l o g i c a ld a t a b a s e ，t h e d e v e l o p m e n to f i n d e x i n gt o o l sa n dd n a o rp r o t e i n ss e q u e n c ea n a l y s i s ；t h es y m b o lo f g e n o i m ce 豫i n c l u d e st h ed i s c o v e r ya n di d e n t i f i c a t i o no fg e n e s t h ef o u n d a t i o no f w e bd a t a b a s es y s t e ma n dt h ed e v e l o p m e n to fi n t e r f a c e t o o l s ；t h es i g no f p o s t - g e n o m i ce r ai sm a s ss c a l ea n a l y s i so fg e n o m i ，p r o t e i n o m i c sa n dc o m p a r i s o n o ri n t e g r a t i o no fb i o i n f o r m a t i c sd a t a t h i s p r e s e n t a t i o na t t e m p t st oi n t r o d u c e i v 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 c o m p l e xt h e o r yi n t ob i o i n f o r m a t i c sd o m a i na n dg e t ss i g n i f i c a n tr e s u l to ns e v e r a l i m p o r t a n tq u e s t i o n so f p o s t - g e n o m i c s 弧 1 1 1 ec h a r a c t e r i s t i co fc o m p l e xs y s t e mi sn o n l i n e 锄 i t y , w h i c ha l s om e a l 篮q t h e w h o l ei sn o te q u a lt ot h es u mo fi t s p a r t s ”t h et o o l e c u l a rf o u n d a t i o no ft h i s n o n l i n e a r i t y i st h e g e n e r i c a n di n t r i c a t ei n t e r a c t i o n s a m o n g a l ls o r t so f b i o - m a c r o m o l e c u l e s ，g e n e sa n dp r o t e i n s i nm o s tc a s e s ，t h e s eb i o - m a c r o m o l e c u l e s n e v e rb e h a v eo rp e r f o r mt h e i rb i o l o g i c a lf u n c t i o n sa l o n e ，b u th a v em a n yd i r e c to r i n d i r e c tr e l a t i o n sb e t w e e ne a c ho t h e r , w h i c hc o u l db ei np h y s i c a lo rc h e m i c a lm a n n e r i ti st h e s er e l a t i o n st h a tb r i n ga b o u tv a r i o u sb i o l o g i c a ln e t w o r k s s u c ha sm e t a b o l i c n e t w o r k , g e n er e g u l a t i o nn e t w o r k , a n ds i g n a lt r a n s d u c t i o nn e t w o r k , e t c u l t i m a t e l y , a l la c t i v i t i e so f l i f ef a l lb a c k 也e s en e t w o r k si nt h e i rs t r u c t u r ea n df u n c t i o n a si sk n o w n , t h ec o n s t r u c to f b i o l o g i c a ln e t w o r ki st h e 掣 o u n d w o r ko f n e t w o r k s t a t i cg e o m e t r i ca n a l y s i s ，由，n a m i c a la n a l y s i s ，i m p o r t a d ：tv e r t e xa n a l y s i s ，n e t w o r k r e g u l a t i o ns t r a t e g yd i s c o v e r y , d i g i te x p e r i m e n ta n ds i m u l a t i o n , e t c t h r o u g hs i m p l e o b j e c ta c c e s sp r o t o c o l ( s o a p ) ，w ee m p l o yt h ew e bs e r v i c ep r o v i d e db yk e g gt o e x t r a c tt h es i g n a lt r a n s d u c t i o nd a t ao fh o m os a p i e n s b yt r a n s f o r m i n gt h e mi n t o n e i g h b o rm a t r i x e sa n dt h e nc o m b i n i n gt h e s en e i g h b o rm a t r i x e st h r o u g hm a t r i x o p e r a t i o n , w ec o n s t r u c ta nu n d i r e c t e dg r a p ho ft h ec e l l u l a rs i g n a l i n gn e t w o r ko f h o m os a p i e n s ，w h i c hc o n t a i n s9 3 1n o d e sa n d6 7 9 8l i n k sa l t o g e t h e r c o m p u t i n gt h e d e g r e ed i s t r i b u t i o n , w ef i n di ti sn o tar a n d o mn e t w o r k , b u tas c a l e f r e en e t w o r k f o l l o w i n gap o w e r - l a wo f p ( k 卜k w i t h 丫a p p r o x i m a t e l ye q u a lt o2 2 s i n c et h i sn e t w o r ki sp r o v e nn o tt ob ear a n d o mn e t w o r k , i ti so fs i g n i f i c a n c et o i n v e s t i g a t et h ep o s s i b l ee x i s t e n tc o m m u n i t ys t r u c t u r e a m o n gt h r e eg r a p hp a r t i t i o n a l g o r i t h m s ，t h eg u i m e r a ss i m u l a t e da n n e a l i n gm e t h o di sc h o s e nt os t u d yt h ed e t a i l s o ft o p o l o g ys t r u c t u r ea n do t h e rp r o p e r t i e so ft h i sc e l l u l a rs i g n a l i n gn e t w o r k , a si t s h o w st h eb e s tp e r f o r m a n c e t or e v e a lt h eu n d e r l y i n gb i o l o g i c a li m p l i c a t i o n s ，f t l r t h e r i n v e s t i g a t i o ni sc o n d u c t e do na dh o cc o m m u m t y f i n a l l y , t h ep o t e n t i a li m p a c to nt h e b a s i cr e s e a r c ha n dd r a gd i s c o v e r yi sd i s c u s s e d i nt h ep a r tt w oo f t h i sd i s s e r t a t i o n , w e 璐ee e l l u l a ra u t o m a t a ( c a ) t oc o n s t r u c ta d i s c r e t em o d e lo fb i o l o g i c a ls e q u e n c ea n dp r e d i c tt h et o p o l o g ys t r u c t u r eo f v 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 t r a n s m e m b r a ep r o t e i s ，w h i c hp l a yc r i t i c a lr o l e si nt h ec e l l u l a rs i g n a l i n gn e t w o r k s c a i sad y n a m i c a ls y s t e md i s c i 哦ei nb o t h t i m ea n ds p a t i a l s p r e a di nr e g u l a rl a t t i c e , e a c h c e l la d o p t e df i n i t ed i s c 眈s t a t ea n du p d a t e ds y n c h r o n o u s l ya c c o r d i n gt oe x p l i c i t l o c a lr u l e t h ee v o l u t i o no fe n t i r ed y n a m i c a ls y s t e mw a si m p l e m e n t e dt h r o u g h s i m p l ea n de x a c ti n t e r a c t i o n sb e 嘶嘲t h o s ec e l l s t h ec h a r a c t e r i s t i co fw h i c hw a s d i s c r e t ei nt i m e , s p a t i a la n ds t a t o 。e v e r yv a r i a b l eo n l ya d o p t e df i n i t es t a t e , a n dt h e s t a t et r a n s f o r m i n gr o l ew a sl o c a lb o t hi nt i m ea n ds p a t i a l 田地p r e s e n ts t u d yi s t o d e v e l o pa ni n t e g r a t i v em e t h o df o rp r e d i c t i n gt h e t o p o l o g yo f t r a n s m e m b r a n ep r o t e i n s0 1 1t h eb a s eo fc a f i r s t ，s c a n n i n gt h er e q u e s t e d p r o t e i ns e q u e n c ew i t haf i x e d - s i z ew i n d o wo f2 0a m i n oa c i d sr e s i d u e s ；t h e n , t h e s e g m e n t st h u so b t a i n e da r ot r a n s f o r m 践li n t ob i n a r ys e q u e n c e sb ya ne n c o d i n g p r o c e d u r e ，u p o nw h i c ht h ec e l l u l a ra u t o m a t a a l ea p p l i e dt od o i r ep s e u d oa m i n oa c i d c o m p o n e n t s ；f i n a l mt h ea u g m e n t e dc o v a r i a n t - d i s c r i m i n a n ta l g o r i t h mi s u s e dt o p r e d i c tt h et o p o l o g yo fr e q u e s t e dp r o t e i n t h er e s u l ts u g g e s t st h i sm e t h o di s a n e f f e c t i v et o o lf o rt h ep r e d i c t i o no fb o t ha - h e l i c a la n d b - b a r r c lp r o t e i n sw i 血h i g h a c c u r a c y , v m i d a t e db y j a c k k n i f ec r o s s - v a l i d a t i o nt e s t m o r e o v e r , b a s e ds 0 1 e l yo nt h e a m i n oa c i ds e q u e n c e , t h i sm e t h o dd o e sn o tr e q u i r ea n yo t h e ra n n o t a t i o n so i s 蛤q u e n c e a l i g n m e n ti n f o r m a t i o n , w h i c hi n d i c a t e st h a tt h ec u r r e n ta p p r o a c hm i g h tb eaq u i t e p o t e n t i a lh i 班t h r o u g h p u tt o o l i n d e a l i n g w i t hp r o b l e m ss u c ha l i k ei nt h e p o s t - g e n o m i ce r a m e a n w h i l e i td o e sn o te s c a p eo u ra t t e n t i o nt h a tt h ep o s s i b l eu s a g e o ft h i sm e t h o do ni m p r o v i n gt h ep r e d i c t i o nq u a l i t yf o ras e r i e so fo t h e rp r o t e i n a t t r i b u t e s ，s u c ha ss u b c e l l u l a rl o c a l i z a t i o n , a f l z y t n of a m i l yd a s s e s ，gp r o t e i nc o u p l e d r e c e p t o rc l a s s i f i c a t i o n , a n dp r o t e i nq u a t e r n a r ys t r u c t u r et y p e s ，a m o n gm a n yo t h e r s k e y w o r d ：c o m p l e ，【s y s t e m ，s c a l e - f r e en e t w o r k , i n f o r m a t i o nt h e o r y , c e l l u l a r a u t o m a t a , c e l l u l a rs i g n a l i n gn e t w o r k v i 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得四川大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 本学位论文成果是本人在四川大学读书期间在导师指导下取得的，论文成 果归四川大学所有，特此声明。 本文作者：1 麦i 健 指导教师： 1 们。) 年月p 日 拇 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 1 研究背景和意义 绪论 线性系统与非线性系统有着本质区别。线性系统的总体行为是其各部分的行 为之和，而非线性系统整体行为要大于其部分行为之和。线性系统遵循“叠加 原理”。可以把复杂的线性系统分解为若干更简单的部分，然后独立地分折它们。 一旦人们理解了不同部分，就可结合起来理解整个线性系统。即：研究线性系 统可用分析方法，分析方法有效。 非线性系统不遵循叠加原理，即使人们把它分解为更简单的组件，分别对各 组件研究透彻，也不能保证通过组合方式，即可理解非线性系统。非线性系统的 关键特征是非线性系统的行为是其各组件交互作用的表现。若各组件独立考虑， 则这种基于交互作用的性质则消失。因此人们研究非线性系统时，往往用与“分 析方法”相反的方法一“综合法”。 复杂系统是相对于牛顿时代以来构成科学研究焦点的简单线性系统而言的， 与简单系统相比，两者具有根本性的不同。简单系统通常具有较小规模的元素 数量，元素间仅存在简单的耦合作用。而复杂系统具有较大规模的元素数量， 元素间具有较强的耦合作用，一般情况下元素具有智能性、抽象性和适应性， 因此也常常将元素称为“主体( a g e n t ) ”。主体可以按照各自的规则作出决策， 随时准备根据接收到的信息修改自身的行为规则；对系统主体的理解建立在主 体的抽象性基础之上，即抽取其影响系统本质的特征进行描述，这也是主体得 以存在的前提。在复杂系统中，主体往往只知道周围一部分其他主体的行为， 但无法知道系统中全部主体的行为，因此复杂系统中的主体只能根据局部信息 而非全局信息作出决策并修改自己的行为规则。 ( 1 ) 复杂系统所包含的主体是复杂系统的基本组织条件，其数量以及相互 之间的耦合强度是复杂系统分类的重要指标。按照钱学森等人对系统 的分类( 表1 ) ，中等规模的以及主体间存在较强耦合作用的系统便 称为复杂系统，如果系统规模巨大，则为复杂巨系统。 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 表1 复杂系统的分类 杂弋 小 出 大 弱简单系统简单系统简单巨系统 强简单系统复杂系统复杂巨系统 ( 2 ) 复杂系统中主体具有智能性和适应性。系统内部的主体能够根据环境 的信息作出行为决策，调整自己的行为规则，包括发现新的规则( 进 化) 。通过主体问相对低等的智能行为，系统在整体上显现出更高层 次、更复杂、更智能、更协调的有序性。这也是对系统科学中的层次 性、反馈、涌现、自组织、目的性等概念的进一步发展。 ( 3 ) 复杂系统中主体的抽象性。对复杂系统的理解与研究是建立在对系统 中主体抽象的基础之上的。正是对复杂系统中主体的特征进行了抽 象，从而产生了系统建模的可能，没有了抽象性，系统将无法理解， 复杂系统也就失去了意义。 ( 4 ) 主体行为的局部信息。在复杂系统中，没有哪个主体能够知道其他所 有主体的状态和行为，每个主体只可能从主体集合众一个相对较小的 子集合中获取信息，处理“局部信息”，做出相应的决策。系统的整 体行为，出自这些主体间的竞争、协作等局部相互作用。 从系统的角度讲，复杂系统一般具有开放性、不确定性、非线性、涌现性以 及不可预测性，在这些特征的综合作用下，在更高的层次上表现出规律性；对 复杂系统的预测是很困难的，往往存在“蝴蝶效应( 混沌现象) ”。因此系统本 身的演化又常常表现出反直觉的特征( 图1 ) 。 1 1 复杂系统理论在生物学中的应用 上个世纪的生物学家采用的研究方法是还原论的方法。他们力图将复杂的生 物体分解成若干简单的部分，直至分解的结果对研究条件来说已经足够简单了， 再对那些相对简单的生物体组成部分进行研究。例如，在研究蛋白质的性质和 功能时，人们使用生物或化学方法将要研究的目标蛋白质从生物体内提取出来， 通过各种化学或物理试验来研究其特性。但是，这样获得的实验数据是该蛋白 2 四川大学博士学位论文 。 复杂网络理论和细胞自动机在生物信息学中的应用研究 质在脱离了生物体环境以及存在相互作用的其他蛋白质，而仅仅在特定实验条 件下表现出的部分性质。所以，从很大程度上来讲这样获得的生物信息是局部 的、片面的，同时也是零散的。 老三论( 系统论、新三论( 突变论、协 信息论和控制论) 同论、耗散结构论) jj 现代系统科学非线性科学 ij 复杂系统理论 0 1 人工生命 i lji 细胞自动机群体智能进化算法 图1 复杂系统理论框架 到了上个世纪年代，随着高通量实验技术的发展和人类基因组计划的启 动，生命科学从基因组到蛋白质组各个层次都积累了海量的生物数据。同时， 随着生物信息学的兴起，人们从这些海量的生物数据中不断提取有意义的生物 信息。虽然，生物信息学家在挖掘这些海量生物数据方面做了大量的工作，积 累了大量有用信息。然而，想要研究生物体的内在机理并造福人类，这些已有 的知识还是远远不够的。因为生物体本身是一个具有高度复杂性的系统，根据 目前局部的、片面的、零散的生物信息我们无法获得生物体作为一个复杂系统 应有的往质和功能。从而，人们认识到目前采用的还原论方法可能无法满足科 学研究的需要。于是，一些走在该领域前沿的科学家们认识到，有必要将目前 已掌握的生物信息整合起来，站在生物系统整体的高度考察生物体作为一个复 杂系统应具有的性质和功能，也就是整合论的研究观点。生物学研究由分解转 向了整合，研究的构架也由单一的生物学实验室转变为大科学工程与传统生物 3 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 学实验室相结合的模式。生物学与数学、物理、计算机科学将更紧密地交叉， 使生物学由描述性科学发展为定量预测的科学。在人类基因组计划带动下出现 的系列组学( o m i c s ，主要有基因组学、转录组学、蛋白质组学、代谢组学、 相互作用组学和表型组学等) ，逐步把分子生物学时代推向系统生物学时代。 在2 0 0 0 年，由日本科学家k i t a n o 和美国科学家h o o d 教授共同发起在日 本东京召开了第一届国际系统生物学大会。这次会议的召开标志着系统生物学 的诞生。从此，系统生物学的思想得到了生物学界的广泛认同，包括哈佛大学 在内的很多知名大学、研究机构纷纷成立了系统生物学系或研究小组，开展系 统生物学研究。诸如s c i e n c e 和n a t u r e 等权威学术刊物也对系统生物学的发展 十分关注，其中s c i e n c e 在2 0 0 2 年3 月刊出了一期系统生物学专刊，该专集 导论中的第一句话这样写道：“如果对当前流行的关键词进行一番统计分析，那 么人们会发现，系统一词高居在排行榜榜首”。 1 2 人工生命 生命现象的奥秘和生物的智能行为一直被科学家所关注，生物系统是一个 典型的复杂系统。群体进化论、随机漂变等学说是基于生物学基础的理论学说， 然而它们所揭示的规律在自然科学和社会科学方面都具有普遍的意义。随着进 化，生物日趋复杂，其形态、遗传信息等等都更加丰富和高级。进化遵循着简 单的规则，这些简单的规则促使生物系统自组织，自适应；随机的因素使得确 定性的进化趋势有着不确定的进化途径。进化、遗传、新陈代谢等起源于生物 学的概念，已经具有了更广泛的意义。实际上，社会、经济、文化等系统也具 有类似生物系统的特征，它们都是开放的、宏观有序的、随机的、具有自组织 和自调控等功能的进化中的复杂系统。近些年来，生物学、信息学、系统学、 物理学、数学、认知科学等学科的交叉渗透，对生命系统做了不同的定义。正 是这些不同领域科学的发展和互相推动，促使人们从更广阔的角度来讨论生命， 用人工的方法去研究生命，从而诞生了人工生命这一独立的学科。 一般来说，人工生命是研究那些具有生命特征的人工系统。实际上，目前 已有许多数字和机械的系统符合这种要求。人工生命考察生命的形式化基础， 重视生命的信息本质。从这种意义上讲，人工生命的开拓者把地球上的生命仅 4 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 仅看成是一种具有特定载体( 蛋白质) 的特定生命形式，地球上的生命进化也 仅仅代表一种特定的进化途径。他们认为可以用别的物质来构造另类载体的生 命形式赋予其生命的特征。因此，人工生命以计算机为媒介模拟生命或具有 生命特征的行为，包括那些自组织、自学习以及信息的复制与传播行为。其意 义在于： 1 ) 由于人工生命是计算机与生命科学及有关学科相互渗透交叉形成的，因 此研究人工生命的计算理论与算法，有助于揭示生命的全貌，及探索生命的起 源，为生物学研究提供新的途径。 2 ) 在人工生命的研究中，许多算法是仿效自然界生物体的信息处理方法( 如 遗传算法、细胞自动机、人工神经网络等) 。他们不仅效率高，而且可应用于科 学和工程的许多实际领域，产生巨大的经济效益。 人工生命的研究提供了用计算机再现生态系统及其复杂性、模拟进化过程 的有效方法，使之有可能对“未知、未来”的生命现象进行探讨。仅从这一方 面考虑，其研究也具有深远的意义。 2 本文主要研究内容 本文的内容安排如下： 首先是绪论，对本研究的背景与意义作综述，然后进一步介绍相关研究领域 的现状，提出本研究的特色和内容。 第一章介绍复杂理论，对其起源和内涵作了综述，然后介绍其研究工具 复杂网络。首先介绍了复杂网络的静态统计分析，包括度分布，聚集度和聚集 系数，平均最短路径，顶点和边的介数，度相关性等；然后介绍了复杂网络的 演化机制和模型，包括规则网络，随机网络，小世界网络，无尺度网络和演化 网络。复杂网络是对复杂系统的一般抽象和强有力的描述方式，可以加深我们 对系统结构的深入了解；反过来，复杂网络的研究成果对探索复杂系统又具有 一定的启发和借鉴意义。 第二章讨论了使用人类细胞信号转导数据构建完整信号网络的方法，并对其 进行了静态几何分析。结果表明它不是一个随机网络，其内部存在有意义的社 区结构。在比较了以层次聚类为代表的聚集算法、以g i r v a n - n e 砌a n 算法为代 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 表的分离算法和g u i m e r a 提出的模拟退火算法以后，选择了其中性能最好的一 种对信号网络的拓扑结果进行了分析。并讨论了相关的生物意义。 第三章讨论人工生命。人工生命研究具有自然生命系统行为特征的人造系 统，是用信息概念和计算机建模来研究一般的生命和地球上特有的生命。本章 讨论了人工生命的起源、内涵和特征，介绍了人工生命的主要研究内容，包括 细胞自动机，以人工脑为代表的虚拟器官，以人工鱼为代表的虚拟生物，能够 竞争计算机资源的数字生命，数字社会和数字生态环境。以及与这些虚拟生命 相对的实体人工生命进化机器人。本章还讨论了人工生命与人工智能的关 系，以及人工生命研究对发展人工智能的指导作用。结合本文第一章，可以看 出，人工生命与复杂系统的研究是相辅相成的，而且人工生命的研究本身就是一 种复杂性的研究，并为复杂系统的研究提供了实验工具和新的思想方法。本章最 后详细讨论了细胞自动机，介绍了其定义、特征和实现方法。 第四章讨论了信息理论和细胞自动机在生物序列分析中的应用。跨膜蛋白是 一类结构独特的蛋白质，在各种细胞中普遍存在，它们是各种信号分子如神经 递质、肽类激素和细胞因子的受体，构成了各种离子跨膜通道，还是呼吸链和 营养物质运输的关键组成部分。本章通过构建基于细胞自动机和l z 复杂度的离 散模型，对跨膜蛋白的结构进行了高精度的预测。在第二章大规模生物网络的 构建、拓扑分析的基础上，为接下来的网络重要节点分析、数值实验和仿真进 行了技术准备。 最后是结论部分，总结了全文的工作，并对下一步的研究方向进行了展望。 四川大学博士学位论文复杂网络理论和细胞自动机在生物信息学中的应用研究 1 引言 第一章复杂理论 2 0 世纪4 0 年代，系统论、信息论、控制论、运筹学等理论相继创立这 个时期的代表性人物有维纳( n o r b e r tw i e n e r ) 、韦弗尔( w w e a v e r ) 、冯诺依 曼( y o nn e u a n n ) 等。其中，冯诺依曼指出“阐明复杂性和复杂化概念应当 是2 0 世纪科学的任务，就像1 9 世纪的熵和能量概念一样。 在这之后的2 0 年中，对复杂性的探索进展不大。相反，系统科学却在这一 时期得到了迅速发展，其理论成果基本上都是关于线性系统的理论。7 0 年代以后， 科学研究的问题越来越复杂，例如生命的起源和进化、意识的本质、免疫系统、 生态安全等，而线性系统理论却不能给以满意解答，这迫使科学家不得不建立 新的科学体系【旧。对复杂性的探索因而重新高涨起来，并且在8 0 年代出现了 新的生机。其标志是于1 9 8 4 年在美国新墨西哥州成立的s a n t af e 研究所。该 所聚集了一批物理学家、理论生物学家、计算机专家和经济学家等，专门开展 对复杂性问题的跨学科的研究。分形、混沌和自组织临界性等概念和理论在这 一时期先后被提出。 到了2 0 世纪末，复杂性研究已经渗透到从技术科学到基础科学，再到自 然哲学的各个方面，新的理论和研究成果不断提出，处处是一派欣欣向荣的景 象。特别是1 9 9 9 年s c i e n c e ( 2 8 4 卷) 出版了复杂系统( c o m p l e xs y s t e m s ) 的专集，组织了一批在物理、化学、经济、生态、地理、气象、神经科学等领域 的知名学者探讨各自领域的复杂性。这标志着复杂性研究已经成为现代科学关 注的中心议题之一。 冯诺依曼提出的“阐明复杂性和复杂化概念”的科学任务在2 0 世纪并未 实现。在新的世纪里，它仍然是摆在众多科学家面前的一项艰巨的任务。但是， 随着科学计算能力的不断提高和数值试验的广泛开展，科学家们正在从不同方 向，不同层次努力推动复杂性研究向纵深发展。 7 四川大学博士学位论文 复杂网络理论和细胞自动机在生物信息学中的应用研究 2 复杂系统 系统是由相互关联，相互制约，相互作用的部分所组成的具有某种功能的有 机整体。按照系统的复杂程度，系统可分为简单系统和复杂系统。复杂系统是 由具有许多不同状态的大量基本单元在非线性作用下形成的有机整体，其最大 的特点是。复杂性”。复杂系统涵盖极广，几乎无处不在，如：生物系统、交通 系统、经济系统、环境系统、生态系统、工程系统、社会系统和复杂工业生产 系统等等。 目前对于简单系统已有相应的研究方法，而且理论上也有了很大的进展。但 由于复杂系统是涉及多个学科的- - n 崭新的科学，在2 0 世纪从未对其复杂性进 行过系统深入的研究。研究复杂性的科学方法到底是什么，目前仍处于探索和 研究之中。所以，复杂性科学将是2 1 世纪的科学，是一门具有重大理论及实际 意义并亟待开展研究的崭新科学 目前对于什么是复杂系统，尚没有统一的定义，但复杂系统的基本特点应包 括以下几个方面： ( 1 ) 系统由大量的作用者( a g e n t ) 或单元组成。少量的单元形成不了复杂 系统。例如，经济系统，只有几种简单商品形成不了市场，达不到繁荣；神经 网络，由亿万个神经元组成，人脑中大约有1 0 0 0 亿个神经细胞。又如金融股市 的股民、角马群、蚁群等等，其中的单元都有一定的数量 ( 2 ) 系统是开放的，受外界影响。 ( 3 ) 在特定条件下，作用者相互作用。 ( 4 ) 相互作用开始，将有微小变化。但系统能自组织，自加强，自协调， 并随之扩大、发展，发生质变。这种质变，在复杂系统中称为涌现或“突现” ( e m e r g e n