（发酵工程专业论文）复杂生物网络可视化方法研究.pdf

摘要摘要生物网络是系统生物学研究的重要内容。快速增长的网络数据和纷繁复杂的研究极大促进了可视化技术的发展，需要设计快速的画图算法布局网络数据和开发便利的可视化软件系统以帮助直观理解复杂生物网络的抽象结构和洞察其中隐含的生物学意义。为实现生物网络画图，必须提供合适的画图算法。一般画法如分层布局，环布局、力导向布局算法，对于节点数较少、拓扑结构较简单的网络效果较好，对于拥有大量节点和连接的复杂生物网络，这些算法的效果不佳。网格布局具有能生成紧凑整齐的布局，同时节点在布局中的几何位置分布与生物功能模块有很好的对应关系等优点而受到广泛关注。该算法需要较大的内存和较多的运行时间，在复杂生物网络实时可视化和互动分析应用中受到较大的限制。k a 幻和k o i i m a 等提出在目标函数中增加“交叉罚分”和“增加生物学属性”等方法改进网格布局算法，加快布局过程，然而，这些算法仍然需要较长的布局时间，需要研究新的快速网格布局算法以实现复杂生物网络的实时可视化。复杂生物网络可视化软件系统提供图形用户界面，用来直观显示算法布局结果和方便用户交互式操作，较为流行的系统包括c y t o s c a p e ，s a n t ，c e l li l l u s t r a t o r ，c a d l i v e等等。为较好地整合和分析网络，复杂生物网络可视化过程中经常需要对网络进行数值分析，然而，上述系统大多以建模为目的，没有提供通用的网络数值分析工具的支持，不方便研究者可视化分析复杂网络数据。在复杂生物网络视图中，众多的节点和节点之间不均匀的连接，通常造成很高的视觉复杂度。如何在有限的图形用户界面空间恰当显示节点的注释，从而方便用户全面直观获取网络信息是非常重要的问题。基于以上分析，本文主要开展了以下工作：a )提出一种快速网格布局算法。在相对较小的内存空间和较少的布局时间代价下，能获取较高质量的布局，布局结果具有与生物学意义相吻合的模块结构，这使得在互动环境中，对典型的复杂生物网络实时可视化成为可能。b ) 开发了一个复杂生物网络可视化软件系统l u c i d d r a w 。将快速网格布局算法实现为l u c i d d r a w 系统内核；为方便网络分析，该系统集成了方便、通用的网络分析工具一m a t l a b 。l u c i d d r a w 系统不仅设计了方便用户交互操作的可视化显示界面，还提供了控制快速网格布局算法参数的图形用户界面，用户能根据自己需要调整布局风格和快速网格算法参数。有关功能模块的生物学属性的信息也町以通过l u c i d d r a w 系统设置，用于影响算法布局。c 1 提出一种复杂网络图示背景下有效展示节点注释信息的解决方案，该方案通过三种标签，即内置标签、浮动标签和强制标签，方便用户获取节点的文字信息同时而不影j摘要响整体布局效果，其中节点的内置标签显示与否随布局图形当前的放大率级别而发生变化，在尽量不增加视觉复杂度的前提下，显示尽可能多的内置标签。本文以绿浓杆菌( 户傩他泐册p a 0 1 ) 的代谢网络为例说明l u c i d d r a w 在具体问题中的应用。在l u c i d d r a w 布局结果中，该网络中毒力因子功能子系统和其他功能模块的关系直观展示出来，另外，l u c i d d m w 直观布局图对于确定一些未指定的反应所属的功能模块，能够提供进一步的线索和参考。关键词：复杂生物网络：图论画法；力导向布局；网格布局；l u c i d d r a wi ia b s t r a c ta b s t r a c tb i o l o g i c a ln e t 、v o r k sp l a ya ne s s e n t i a lr o i ei ns y s t e m sb i o l o g y r a p d l yg r o w i n gn e m o r kd a t aa n dv e r s a t i l er e s e a r c ha c t i v i t i e sp r o m o t eg r e a t i yt h ed e v e l o p m e n to fv i s u a l i z a t i o nt e c h n i q u e 锄dc a l lf o r 亿s ta i g o r i t h m st od r a wn e t w o r k sa n dc o n v e n i e n tv i s u a i i z a t i o nt o o l st oa i di n t u i t i v e i yp e r c e i v i n ga b s t l a c ts t r u c t u r e so fn e “v o r k sa n dg a i n i n gi n s i g h t si n t ot h e如n c t i o n a li m p i i c a t 幻n so fn e t w o r k s i t i sn e c e s s a r yt 0d e s i g ns u i t a b i ea l g o r i t h m st od r a wb i o l o g i c a ln e t w o r k s g e n e r a ld r a w i n gm e t h o d ss u c ha sh i e m r c h i c a ll a y o u t ，c i r c u l a ri a y o u t ，f o r c e d i r e c t e dl a y o u ta r es u i t a b l ef o rb i o l o g i c a in e m o r k so ff e w e rn o d e sa n ds i m p i et o p o l o g i c a ls t r u c t u r ea n du s u a l l yn o ta d e q u a t et op r o d u c es a t i s f a c t o r yd r a w i n g sf o rc o m p l e xb i o c h e m i c a in e t 、v o r k so fl a r g ea m o u n to fn o d e sa n dc o n n e c t i o n s g r i dl a y o u tm e t h o d sd r a wm a n yc o n c e m sf o rh a v i n ga d v a n t a g e si ng e n e r a l i n gc o m p a c tl a y o u t sw i t hb i o l o g i c a l l yc o m p r e h e n s i b l em o d u l e so fb i o l o g i c a ln e t w o r k s t h em a i ni s s u e so fg r i di a y o u tm e t h o d sa r et h eh i g hc o m p u t a t i o n a lc o s t 锄dl a r g ec o m p u t e rm e m o r yr e q u i r e m e n t ，w h i c hs e r i o u s i yl i m i tt h ea p p l i c a t i o n si ni n t e r a c t i v er e a l t i m ev i s u a l i z a t i o n 觚a l y s e so fc o m p l e xb i o l o g i c a ln e t w o r k s s o m ei m p r o v e da l g o r i t h m sp r o p o s e db vk a t oa n dk o i i m at r i e dt os p e e du pl a y o u tp r o c e s s e sb yt h em e t h o do fa d d i n gc r o s sc o s t sa n db i o l o g i c a la t t r b u t e si nc o s t 如n c t i o n s ，b u tt h e ys t i l ln e e dr e i a t i v e l yl o n gl a y o u tt i m e i ti sn e c e s s a 吖t 0d e v e l o pn e wf a s tg r i dl a y o u tm e t h o d st o h i e v en e a rr e a l t i m ev i s u a l i z a t i o nf o rc o m p l e xb i o l o g i c a ln e 姗o r i ( s t h ev i s u a l i z a t i o ns o f t 、a r es y s t e m sa r eu s e dt 0d i s p l a yl a y o u tr e s u l t si n t u i t i v e l y 锄do d c r a t ei n t e r a c t i v e l yt h r o u g ht h e 汀a p h i c a lu s e ri n t e r f a c e s t h es y s t e m ss u c h 弱。雌o s c a p e ，v i s a n t ，c e hi l l u s t r a t o r ，a n dc a d l i v ea r et h em o s tp o p u l a rv i s u a l i z a t i o ns y s t e m s 陀c e n t l y g e n e r a l l ys p e a k i n g ，i ti sv e wn e c e s s a 科t 0a n a l y z et l l ed a t ao fc o m p l e xn e t 、v o r k sd u r i n gv i s u a l i z a t i o np r ( c e s s e sf o rt h ep u r p l o s eo fi n t e g r a t i n ga n da n a i y z i n gn e t w o r k se f 矗c i e n t l y h o w e v e r t h em e n t i 伽e ds y s t e m sa r ed e s i g n e df o rm o d e li n g 狮ds p e c i f i cp u r i ) o s e s ，n e 帆o r ka n a l v s e sr e l a t e dn u m e r i c a im i l i t i e sa r en o tp r o v i d e d ，t h e r e f o r e ，i ti sn o tv e 眄c o n v e n i e n tf o rr e s e a r c h e r st 0a n a l y z et h ed a t ao fc o m p l e xb i o l o g i c a ln e t w o r i c s 1 nt h eg r a p h i c a iu s e ri n t e 血c e so fc o m p l e xb i o l o g i c a ln e t 、) v o r k s ，l a 唱e 锄o u n to fn o d e sa n d 明e v e nc o n n e c t i o n su s u a l i yc a u s eh i g h l yv i s u a ic o m p l e x 时h o wt od i s p l a yn o d ea n n o t a t i o ni n f o 啪a t i o ns u i t a b l yi nl i m i t e dv i s u a ls p a c er e m a i n s 绷e s s e n t i a lp r o b l e m ag o o ds o u i t i o nt 0t h ep r o b l e mw i l lh e l pu s e r si e 锄t h ei n f o n n a t i o n 觚dc h a r a c t e r i s t i c so fn e t 、) v o r | 匹c o m p i e t e i y 觚di n t u i t i v e i y t h i sp a p 町p r e s e n t st h ef o l l o w i n gw o r k sb a s e d 伽t h ea b o v e m e n t i o n e d 觚a l y s e s ：a ) af a s tg r i dl a y o u ta l g o r i t h mh a sb e e nd e s i g n e d 柚dw i t hi t ，t h eh i 曲q u a i l i t yl a y o u t sc a nb ep r o d u c e di nl e s sc o m p u t e rm e m o 叫a n dl o w e rc o m p u t a t i o n a lc o s t t h em o d u l es t r u c t u r e si nr e s u l td r a w i n g sa f eb i o i o g i c a lu n d e r s t a n d a b i e a l lt h e s ea d v a n t a g e se n a b l ev i s u a l i z a t i o no fc o m p j e xb i o 】0 9 i c a ln e 铆o r k si nn e a rr e a l - t i m ei ni n t e r a c t i v ev i s u a le n v i r o n m e n t b 1av i s u a l i z a t i o ns o r w a r es y s t e mf o rc o m p l e xb i o i o g i c a ln e t 、) v o r k sl u c i d d r a wh a sb e e nd e v e l o p e d t h ef a s tg r i dl a y o u ti si m p l e m e n t e da st h ec o m p u t a t i o nc o r co fl u c i d d r a wa n d ，m a t l a b ，ac o n v e n i e n t ，g e n e r a l p u r p 0 s en e t 、7 v o r ka n a i y s i st o o ii si n t e g r a t e d ，p r o v i d i n gu s e r sac o n v e n i e n tw a yt ov i s u a l l ya n a l y z ec o m p i e xn e 铆o r k s a ni n t e r a c t i v eg r a p h i c a lu s e ri n t e r f a c e sf o rv i s u a i i z a t i o ni sd e s i g n e di nl u c i d 【) r a w ，i na d d i t i o n ，g r a p h i c a iu s e ri n t e r f - a c ef o rc o n t r o l l i n ga i g o r i t h mp a r 锄e t e r si sp r o v i d e d u s e r sc a nm o d i 母i a y o u ts t y l e sa n da l g o r i t h md a 舢e t e r sa sw i s h l u c i d d r a wa l s oe n a b l e se 硒i n c o r p o r a t i o no fe x t r ab i o i o g i c a lm摘要i n f o 肿a t i o n ，i fa v a i l a b l e ，t 0i n f l u e n c et h eo u t p u tl a y o u t sw i t hp r e d e f i n e dn o d eg r o u p i n gf - c a t u r e s c ) as o l u t i o no fe f r e c t i v ed i s p l a y i n ga n n o t a t i o ni n f 0 r n l a t i o ni nt h ec o n t e x to fd r a w i n g so fc o m p l e xn e t w o r k si sp r e s e n t e d t h r e ek i n d so fl a b e l s ，i e ，e n g r a v e d ，f l o a t i n g ，锄dm a n d a t o 拶l a b e i s ，a r eu s e dt 0a i du s e r st og e tn o d ei n f o m l a t i o nc o n v e n i e n t l yw i t hm i n i m u mp e n u r b a t i o no ft h ew h o i ed r a w i n g d i s p l a y i n go fe n g r a v e dl a b e l si sd e p e n d e n to nt h ez o o ml e v e l ，w h i c hc a nd r a wm o r el a b e l sa sp o s s b l ew i m o u tc a u s i n gt 0 0m u c hv i s u a lc o m p l e x i 钟ac a s es t u d yf o ra n a l y z i n gp 粥n 曙打加册p a oli sg i v e nt oi i l u s t r a t et h ea p p l c a t i o no fl u c i d d r a w w i t ht h eh e l po fl u c i d d r a w t h er e l a t i o nb e t w e e nv i r u l e n c ef - a c t o rs y n t h e s i sa n do t h e r 如n c t i o n a ls u b s y s t e m sc a nb ev i e w e di n t u i t i v e l ya n dt h ed r a w i n g sc a na l s op r o v i d ec l u e sf o rf h r t h e ri n v e s t i g a t i o n st oc l e a rt h eu n c e r t a i n t yf o rs o m ep r e d i c t e dr e a c t i o n sw i t hu n k n o w na s s 远n m e n to f 角n c t i o n a ls u b s y s t e m s k e y w o r d s ：c o m p l e xb i o l o g i c a ln e t w o r k s ；g r a p hd r a w i n g ；f o r c e - d i r e c t e di a y o u t ；g r i dl a y o u t ；l u c i d d r a w目录目录摘要la b s t r ；l i 畦i i i目；2 i第一章绪论31 1 研究背景。31 1 1 概述31 1 2 复杂生物网络可视化研究现状41 2 本论文的主要研究内容：1 41 2 1 可视化研究中存在的问题及对策1 41 2 2 本论文的主要研究内容1 51 2 3 图形和页码对照表1 6第二章一种新的快速网格布局算法1 92 1 已有的网格布局算法分析1 92 1 1l i & k u r a t a 的工作1 92 1 2m i v 锄。小组的工作2 02 1 3b a r s k v 的工作2 22 2 目标函数及优化策略2 22 3 算法参数讨论2 82 4 算法时间复杂度3 32 5 与其他相关算法比较3 42 6 本章小结3 6第三章复杂生物网络可视化系统l u c i d d 随w 3 73 1l u c i d d m w 系统功能结构。3 73 1 1 功能结构图3 73 1 2 其他系统架构分析3 93 2 功能和实现i m a l l ，a bg u l 4 23 2 1 构建复杂生物网络4 33 2 2 实现算法参数控制4 73 3 功能和实现i i l u c i d d m wg u i 5 23 ：3 1l u c i d d 随wg u i 功能按钮5 23 3 2 实现三种节点标签5 43 4 本章小结6 0第四章l u c i d d m w 系统的可视化及其应用6 l4 1l u c i d d r a w 可视化效果分析。6 l4 2l u c i d d r a w 应用研究6 74 3 本章小结7 0第五章结论及迸一步研究方向7 l5 1 全文的主要结论7 15 2 进一步研究方向7 l5 3 本文主要的创新点7 2参考文献7 4附录一l u c i d d r a w 操作指南8 0附录二作者在攻读博士学位期间发表的论文8 4j s 【谢8 5江南大学博士学位论文2第一章绪论1 1 研究背景第一章绪论1 1 - 1 概述从2 0 世纪末到2 l 世纪初的十多年时间里，生命科学尤其是分子牛物学发生了令世人瞩目的巨大变化。一方面，由于基凶组测序、蛋白质组学的飞速发展，为生物学研究领域积累了大量的实验数据，如何挖掘出海量数据所蕴藏的生物基本规律成为生命科学研究的重点内容之一；另一方面，生物学系统的信息处理过程的研究开始从对单一信号传导途径的定性描述转移到对复杂蛋白质网络、基因调控网络、代谢网络的定量刻画，这些进展使人们相信2 1 世纪是生命科学的世纪，同时生物学家也逐步地将数学、物理学、化学、信息等定量学科引入到对生命科学的研究之中【l 】，并逐渐产生了一个研究复杂生物网络整体性质的交叉学科：系统生物学。由于同时期计算机领域所取得的巨大成就，对复杂生物网络采用计算机辅助建模日益成为系统生物学的研究热点。其中通过画图的方法直观展示网络并在此基础上实现可视化分析是研究复杂生物网络，辅助计算机建模的重要手段。生物网络的复杂性体现在两个方面：一是网络节点和节点之间的连接众多，典型的生物网络有数百至数万个节点以及平均每个节点几个至几十个连接；二是连接的高度不规则性，大多数节点只有很少连接，而少数节点则拥有众多连接【2 】。从信息学角度看，生物网络是复杂的高维数据结构。用二维图形表示网络结构，将这种复杂抽象的数据可视化，在计算机辅助建模和网络数据查询系统中是不可或缺的【3 5 】。一般来说，网络可视化系统要解决的基本问题是：自动布局算法( 画图算法) 的设计和可视化系统( 模拟平台) 的开发。一、自动布局算法是可视化问题的核心，主要研究如何将节点和边有序地布置到( 画到) 平面上的算法规则集。画图问题的由来及其发展历程。图是一种应用非常广泛的数据结构，可以用来表示各种复杂的系统模型，网络分析是其重要的应用之一，其中顶点表示系统中的元素，边表示元素之间的关系。将网络图形整齐、美观地画出来，对于正确理解和分析模型十分必要。根据具体应用和美学观点的不同，人们形成了各自不同的美观准则。通常，人们仍普遍接受以下美观准则：( 1 ) 尽可能将节点均匀地分布在有限区域中；( 2 ) 尽可能避免边的交叉；( 3 ) 尽可能使边长一致；( 4 1 反映图的内在对称性由于表示复杂系统模型的图形的节点数和边数都相当大，以致于用人j ：方法将图整齐、美观地画出来几乎是不可能的，因而采用计算机自动地画图，并设计恰当高效的3坚塑查堂堡主兰壁堡奎自动布局算法便成为一个十分重要的课题【6 】。为方便研究人员在这一领域的交流与合作，自1 9 9 2 年以来，国际上每年都要举行画图算法学术研讨会 7 。图的分类比较复杂，通常，按形状町分为：树形图、环形图等、按维度分为：平面图，3 d 图，按是否标记边方向可以分为有向图、无向图等等。通常，不同类型的图形有不同的拓扑特征，应当设计不同的画图策略和算法。二、可视化软件工具的开发需要设计出用户友好的计算机软件系统以直观显示算法的结果，软件系统和工具是可视化问题必需的载体。现存的网络可视化系统包括c y t o s c a p e 【8 1 4 】，s a n t 【1 5 - 1 9 】，v a n t e d 【2 0 】，p a t i k a 【2 l 】，p a t i k a w e b 【2 2 】，p 萄e k 【2 3 】，c a d l i v e 【2 4 2 7 】，y a n a s q u a r e 【2 8 】等等，上述系统较流行的是c y t o s c a p e ，洳t ，v a n t e d 等，其中c y t o s c a p e 的使用最为广泛，集成了包括力导向( 硒r c e - d i r e 曲e d ) 【2 9 ，3 0 】，分层布局( h i e r a r c h i c a ll a y o u t ) 【3 l ，3 2 1 等的布局算法；v i s a n t是近年来较为流行的基于i a v aa p p i e t 可视化系统，其突出的特点是系统软件架构非常紧凑，在线访问的速度非常快，已经实现了对k e g g 【3 3 3 6 】的在线可视化。1 1 2 复杂生物网络可视化研究现状由于在后基因组时代，基因组学研究和高通量实验技术推动着网络数据的迅速增长，极大地促进了生物网络特别是复杂生物网络的研究，通过画图的方法直观展示网络并在此基础上实现可视化分析是研究复杂生物网络的重要手段。复杂生物网络的可视化分析的一个主要目的是从宏观角度洞察复杂生物网络的全局特征，如模块或功能结构，再从微观角度把握其具体的网络连接之间的细节，有助于更准确地了解生命过程。复杂生物网络的可视化分析方法主要包括两个方面的内容，布局算法和可视化系统的研究。本节首先讨论布局算法的发展历史和现状。生命系统( 如细胞) 通常可以简化表示为各种网络，如代谢网络、基因调控网络、蛋白质相互作用网络等等，这些网络的数学模型是图，图的节点是蛋白质，基因，或代谢物，而图的边( 连接) 则用来表示这些节点之间的相互关系。网络是抽象的数据结构，为了更好地理解网络元件( 节点) 的组织结构特征及其与网络功能之问的关系，图形化的直观表示是必不可少的，然而，生物网络的复杂性为其可视化带来了很大困难。图1 1给出了从抽象数据结构到二维图形表示的一个简单例子，其中a ，b ，c ，d ，e 代表节点，如基因，蛋白质，代谢物。左图中，最左边一列表示源节点，“”后面的符号表示目标节点。右图中，节点间的带箭头的连线表示节点之间的关系，箭头标志了源节点到目标节点的方向。4第一章绪论图1 1 抽象数据的二维图形显示f i g 1 1t h e2 dg r a p h i c sd i s p l a yo fa b s t n l c td a t a 早期的可视化由手工方法实现布局，虽然可以美观准确地表示网络中各个元件之间的生物学关系，但需要大量的时间和人力，难以绘制拥有众多节点的大规模的复杂网络。随着生物学网络数据的迅速积累，对大规模复杂生物网络研究工具的需求也日益迫切，复杂生物网络的自动画图法吸引了研究者广泛关注【3 ，5 ，2 0 ，3 7 3 9 】。图论画法的研究有较长的历史【4 ，6 ，3 0 ，4 0 ，4 l 】，开发了大量针对特殊类型的图( 如树和平面图等) 的画法【6 ，4 1 】，而普适目的图论画图算法却不多，典型的画法可以利用免费的软件包如p 面e k ( h n p ：v l a d o f i t l f u n i 1 j s i p u b n e t 、v o d ( 昨a j e 和g r a p h v 泣【4 2 ，4 3 】( h t t p ：肌m 眦g r a p h v i z o r g ) 等方便地实现，其中g r a p h z 还被m a t l a b 的b i o i n f o m a t i c st o o l b o x 采用作为网络可视化的基本工具。一般来说，这些算法对于节点数较少、拓扑结构较简单的网络效果较好，对于节点多、连接不均匀的复杂生物网络，通用算法的效果不佳f 3 ，5 1 。对生物网络的自动画图法的需求主要来自两个方面，一是来自于生物网络数据库，如b i o c y c 【4 4 4 6 】的可视化用户界面，见图1 2 ；二是生物网络建模与模拟软图1 2b i o c y c 数据库的代谢网络图形表示f i g 1 21 1 1 eg r a p h i c sd i s p l a yo f m e t a b o l i cn e m o r k sj nb i o c y cd a 协b 私e ( h 钍p ：b i o c y c o r 雩r o v e i e w s w c b c e i o v s h t m i )5；lll；|i拼m 小m mm；绺戮黜嚣弧锄mmm搿磁江南大学博士学位论文件系统，如c e l li l l u s t r a t o r ，o s p r e y ，c y t o s c a p e ，p a t i k a ，p a t l k a w e b ，c a d l i v e ，v i s a n t 等。画图工具的核心是自动布局，以下评述近年来出现的典型的生物网络自动布局算法。一、布局算法目前很多面向生物网络的自动布局算法的目标是自动绘制代谢途径。作为整体代谢网络的子网络，代谢途径的复杂性很低，其节点和边的数目通常小于1 0 0 。很多代谢途径已有手工绘制的、静态图形表示，如最著名的代谢数据库系统k e g g 。图1 3 是k e g g中的静态图。随着代谢网络数据的迅速增长，手工绘图难以适应网络数据的迅速膨胀和数据库的频繁更新，自动画图在代谢途径数据库应用系统中的作用越来越重要【4 7 5 3 】。代谢途径具有比较明确的过程流向，清晰显示途径的整体流向是这类算法要解决的首要问题【4 ，5 】。分层布局算法【5 4 】首先计算节点的层次作为纵坐标，尽量使边的箭头方向一致以突出显示代谢过程的流向，然后确定横坐标，即调整相同层次上的节点位置，降低边的总长度同时减少边交叉使得总体布局清晰美观，如图1 4 所示。图1 3k e g g 数据库中的醣酵解人工绘制的代谢途径f i g 1 3s t a t i cm a po f g l y c o i y s i si nk e g g( h n p ：m 删g e n o m e j 眺e g 咖a t h w a y m a p m a p o o olo h t m i 2 0l0 4 2 2 )6第一章绪论誉鳓酗i ；i 莉蛙童霉雨蔷；订遥匿如理蠡刁两勃陋勃涎矗兰l洋动f 盈圜j：髓曼幽；懑斓幽幽鹾董蜘晒葶硐鳓蜒茧明渤谶鳓彘鳓峨鎏垣鳓幽蠢嘲商囟j 擞，一舰幽挺；鳓照r 一一了鹣一! 【鞘。尊l 俺鹌鸯毒研湮轫i 龋崩、哂套廊7 。濑图1 4 分层式布局算法绘制代谢途径的结果。f i g 1 4m e t a b o l i cp a t i l w a yi sd r a w nb yh i e m r c h i c a l l a y o t l t 代谢途径中另一个重要特点是常常包含圈( c y c l e ) 结构，这些圈与一系列循环反应相对应，具有重要的生物学意义，因此突出显示圈结构是代谢途径画法的另一主要目标。大多代谢途径画法都对圈进行特殊处理，如k a r p 等【4 4 ，4 5 】、b e c k e r 等【4 7 ，5 5 5 7 】、s c h r e i b e r 【4 】和w e g n e r 【5 】等提出的代谢途径画法都首先探查途径中的圈并对圈上的节点应用环布局( c i r c u l a rl a y o u t ) 算法，然后用分层算法或力导向算法计算其余节点的位置并将环布局整合到最终完整布局中。此类复合算法可以对含有简单环结构的代谢途径生成比较合理美观的布局。当处于环上的节点与其他节点的联系增多时，简单的环画法会导致很多的边交叉，使得视图难以理解。对环的更仔细处理，如使用节点生物学属性等额外信息作为约束，可以明显改善图形表示质量。然而，当许多代谢途径紧密耦合，集成为一个代谢网络时，各节点间的联系变得错综复杂，强调整体流向就失去了意义，这类方法就完全失效。这时忽略边的方向而将整个网络作为无向图进行布局，力图将功能联系紧密的节点布局在一起以突出功能模块就更有意义。生物网络的功能模块及其划分是系统生物学一个重要问题。许多实际的复杂网络有着共同的全局结构特征：如具有小世界【5 8 】和无标度【5 9 】的特征等等。这些具有相似的全局结构特性的网络却常常具有不同的局部结构特征，这些局部特征和功能模块关系密切。因此，理解网络的局部拓扑结构及其产生的机理，并探讨功能模块划分是非常重要的。以细胞网络为例，近年来的研究表明，细胞的功能是以一种高度模块化的方式实现的【l ，6 0 ，6 l 】。一般而言，模块( m o d u l e ) 是指一组物理上功能上连接在一起的、共同完成一个相对独立功能的节点的集合。例如，相对同定的蛋白质蛋白质和蛋白质r n a联合体就是许多基本生物功能的核心。在细胞代谢网络重构过程中，研究者也会将复杂的代谢网络依据一定的规则划分为数个或数十个子模块，每个模块都能完成相对独立的细胞子功能。从复杂生物网络中寻找和划分网络功能模块常常采用聚类算法【6 2 ，6 3 】等等。江南大学博士学位论文生物网络可视化通过适当的布局算法设置节点在视图中的几何位置，使用图形符号直观显示网络的拓扑结构，其关键是网络节点布局，即根据网络的拓扑结构计算出各节点的几何位置。合理的网络布局应当有较少的边交叉，尽可能使节点问的关系清晰明嘹，节点问几何位置的远近尽可能反映拓扑关系的亲疏。符合这些条件的布局通常能够将生物网络中的节点在几何上划分为一些相对独立的集团，同一集团内的节点之间联系紧密，而属于不同集团的节点之间则联系稀疏，这样的集团往往对应着有生物学意义的功能模块。因此，设计良好的生物网络可视化算法也可以产生有生物学意义的功能模块，一个好的布局算法同时也是一个复杂网络结构分析辅助工具。对于拓扑结构比较简单的网络( 如代谢途径) ，可以采用分而治之的策略进行布局【4 7 】，通过将某些有特殊意义的子网络( 如圈) 作为超节点简化网络，计算简化网络的布局后适当整合各子网络的布局即可实现网络的自动画图。对于大规模的复杂生物网络，分而治之策略难以奏效，因为复杂生物网络的拓扑联系错综复杂，各种子网络紧密耦合，很难通过合并节点得以有效简化。在这种情况下，另一类可行的不依赖拓扑结构简化的布局方法就成为目前复杂生物网络自动画图的主要方法，即力导向布局。一：唾厂二窖 ?- ：产一1 ，三耋黥、。寥篆羹一_ i ， 3 ，_ 图1 5 采用c ”o s c a p c 中的f o r d i r e c t e d 算法绘制的代谢网络的布局结果。( 代谢网络数据取自于k e g g 数据库，包含t y r o s n em e t a b o l l s m 等5 个代谢途径。共2 5 7 个节点和2 8 9 条边，为了清晰显示视图，节点标签未显示)f i g 1 5am e t a b o l i cn e t w o r ki sd r a w nb yf o r c e d i r e c t e d ( 丁h en e t w o r kd a t ac o n s i s t i n go f5p a t h w a y si st a k e nf r o mk e g gi n c i u d i n gt y r o s i n em e t a b o l i s m ，t o t a i l y2 5 7n o d e sa n d 2 8 9e d g e s )力导向布局的基本思想是将所有节点看成相互排斥的粒子，将边看作节点间的相互吸引作用力。当这样的系统达到平衡时，没有联系的节点将互相远离，联系紧密的节点则倾向于聚集在一起。力导向布局算法通过搜寻系统的能量极小来确定系统平衡状态中粒子的位置，并将其作为节点在布局视图空间中的几何坐标。显然，粒子问相互作用的具体方式( 即力场) 决定了布局特点，已有的各种不同的力导向布局算法的主要区别就3第一章绪论在于力场函数的选择【6 4 ，6 5 】。在力场模型确定之后，力导向布局就转化为全局极小化问题。适合于复杂网络的力场模型通常导致复杂的、多极小目标函数，布局的优劣很大程度上取决于全局极小化方法的性能。一个采用力导向算法绘制代谢网络的布局如图1 5 所示。作为一种普适的布局方法，力导向算法的概念简单、易于实现，对许多类型的图能够生成基本符合一般美学标准( 如较少的边交叉、尽可能匀称的节点分布等) 的布局，因此被广泛关注。自然地，它也被用于复杂生物网络画图，如j u 等【6 6 ，6 7 】基于力导向算法设计的蛋白质相互作用网络的画图方法，可用于相互作用网络数据库可视化查询。b i o l a y o u t 6 8 1 采用力导向算法生成2 d 或3 d 布局显示大规模网络的拓扑结构，适用于具有明显集团结构的网络，如蛋白质序列相似性网络。最近开发的用于辅助分析蛋白质同源关系网络的可视化软件l g l 【6 9 】【7 0 】，也是基于力导向算法，对于具有明显树状结构的大型网络效果良好。当应用于一般的生物网络时，由于节点间的相互联系比树状结构复杂得多，因而难以取得满意效果。另外一个特殊目的的网络画图算法的例子是o s p 唧7 1 7 3 1 ，专门设计用于蛋白质相互作用网络的可视化，使用的布局方法产生大量的边交叉，不适合清晰显示生物网络的细致拓扑结构。由于力场模型中粒子间普遍存在的排斥作用，力导向倾向于产生开放延伸型布局，这很适合显示树状网络的分枝结构。对于复杂生物网络，力导向布局总是产生不均匀的边长分布，有些节点过于靠近，这都不利于产生紧凑、美观、易于理解的网络画图【3 ，4 7 】。因此，随着网络规模的不断扩大，一般的力导向布局算法适用范围受到很大限制。力导向算法不能产生紧凑布局的一个直接原因是布局中往往有节点过分靠近，必须使用足够的放大倍率才能使视图中节点的图形符号不重叠。另一个略微隐蔽的原因则在于一般力场模型只在直接相连的节点之间有吸引作用，其余所有作用都是排斥性的，这使得整体布局倾向于开放延伸。针对这些问题，一种新的基于离散坐标布局的力导向方法一网格布局算法( 鲥dl a y o u t ) 被提出【3 】：将节点放置在网格上避免节点重叠，同时根据网络的全局拓扑关系确定节点间相互作用的力场参数，较好地解决了连续力导向布局存在的问题。与力导向等算法相比，该算法的一个突出特点是目标函数非常简洁高效，对酵母细胞周期调控网络等实例的布局计算表明网格布局明显优于连续力导向布局，不仅能生成紧凑整齐的布局，同时节点在布局中的几何位置分布与生物功能模块有很好的对应关系。因此网格布局算法不仅能有效布局网络并给每个节点分配坐标，而且是区别于聚类算法划分模块的另一种的能从复杂生物网络中直接产生功能模块的新的有效算法。网格布局法的一个主要问题是计算量大，虽然没计了针对离散目标函数的快速搜索算法，对大型网络仍然需要耗费较多的时问才能生成满意的确i 局。减小计算量的一个有效策略是限制搜索空问，这可以通过利用额外的节点生物学属性实现，如将节点限制在特定的布局区域( 对应特定的细胞区室) 。通过随机采样的方式探索布局空间也可以明显提高计算速度【7 4 7 6 】，但这种改进方式显然是以牺牲布局质量为代价的。如何大幅度提高计算效率同时不明显降低布局质量仍然是这类布局算法的努力方向。网格布局算9江南大学博士学馕论文法通过合理安排节点的位置间接地减少边交叉，对于网络中连接稠密的区域，这种问接方式可能会导致较多交叉。k a t 0 等【7 7 】提出了c b g r i d 算法对此加以改进，通过在目标函数中显式加入边交叉及边与节点交叉罚分项，可以大量减少边交叉及边与节点交叉，明显提高布局质量。同时，c b g r i d 还利用节点的额外信息( 分子的亚细胞定位) 作为约束，有效压缩搜索空间，提高计算效率。然而，引入交叉罚分所增加的计算复杂度依然阻碍网络算法在大规模网络中的应用。网格布局算法从一个随机的初始布局出发，通过移动节点不断改进布局，因此，如果有一个较好的初始布局作为出发点，就可以极大地缩减优化布局的搜索时间。基于这一思想，k0 1 j i m a 等【7 5 】提出了s c c b 盯i d 算法，借助速度较快的连续力导向算法产生较好的初始布局，明显提高了计算速度。s c c b g r i d 算法还可以更仔细地利用额外的生物学属性，如节点( 分子) 的亚细胞定位、分子类别( 蛋白质、m r n a 等) 以及功能信息。近来k q j i m a 又基于扫描计算( s w e e pc a l c u i a t i o n ) 策略提出一种新的快速网格算法，较大提高算法运行速度，可以用于生物数据库的实时可视化显示【7 6 】。利用生物学属性辅助网格算法