（模式识别与智能系统专业论文）数据挖掘的建模及在生物信息学中的应用研究.pdf

j 支互二謦堕主兰堡笙苎 数据挖掘的建模及在生物信息学中的应用研究 摘要 近十几年，随着科学技术的飞速发展，经济和社会都取得了极大的 进步，与此同时，在各个领域产生了大量的数据。为了从如此大量的数 据中发现有价值的知识及规律，人们结合统计学、数据库、机器学习等 技术，提出数据挖掘技术来解决这一难题。 聚类分析是数据挖掘研究中的重要内容，成为各学科研究中的重要 工具。但在现实生活中，常常遇到高维数据集的处理且在大多数情况下， 这些数据集对于各个聚类存在属性不平衡的现象。根据这一点，本文提 出在核特征空间中的属性加权核聚类算法，实验表明新聚类算法能很好 地反映各属性对于各个聚类的重要性，因而取得了比传统聚类算法更好 魄结果。传统聚类算法的应用对象往往局限于单一独立的数据集，但在 很多情况下一个数据集要和其他数据集相互发生关联。基于信息理论， 本文提出的合作聚类算法反映了数据集间的相互作用关系，结果表明聚 类结果将受到其他数据集的影响。在人类世界中，人眼是最有效的获取 知识的器官，也是最有效的聚类机制。因此模仿人眼的工作原理将为研 究聚类分析提供一个非常好的平台。本文通过模拟人眼非均匀采样的特 点，提出一新颖的视觉聚类分析算法，该算法对于解决聚类分析结果评 价的有效性等有着重要的参考意义。 随着生物科学技术在近几年的发展，产生了大量的生物数据。利用 传统的生物实验方法将不能满足目前处理如此多生物数据的需要。在这 种情况下，生物信息学应运而生。生物信息学是计算机科学与生物科学 的交叉学科，成为目前研究的热点。诸多数据挖掘技术，如聚类分析、 机器学习等，也成为生物信息研究中的重要内容。文章在分析了前人利 用“无监督”模糊c 均值聚类算法在预测分析蛋白质结构方面的缺陷的 基础上，提出了一种“有监督”的聚类算法用来预测蛋白质结构。实验 表明，利用了训练数据类别标号的“有监督”聚类算法的分类精度比“无 监督”聚类算法有很大提高。通过这一点表明，在缺乏数据样本类别标 号时，“无监督”聚类算法是一种优秀的分析工具，但如果先验知识预 先知道训练样本的类别标号，采用“有监督”的学习算法将更加有效。 在蛋白组学的研究中，一个重要的课题是如何离散化蛋白序列，从而能 为计算机所识别处理。诸多实验表明，伪氨基酸离散模型比传统2 0 d 氨基酸离散模型包含更多的序列顺序信息，因而大大地提高了各类算法 在蛋白质属性上的预测分析精度。但如何确定伪氨基酸成分的维数一直 是困扰各位研究人员的问题。本文提出了集成分类器框架方案，通过集 成多个不同维数的伪氨基酸离散化模型，解决了维数选择问题，大量实 验表明在大多数情况下，由于从不同角度抓住问题的核心，集成分类器 比任何单一维数的分析精度都要高。随着生命科学、生命数据库的发展， 近几年g e n eo n t o l o g y ( g o ) 数据库得到了长足的发展。g o 数据库是 一综合多种不同数据库的蛋白表达数据库。本文利用g o 蛋白的离散模 型预测分析蛋白亚细胞位置，由于g o 离散模型更能反映蛋白亚细胞位 置的特性，因此取得了比其他离散化模型更好的效果。另外，本文所建 立的数据集覆盖了目前该领域研究中最多的亚细胞位置，大大扩大了该 项研究的实际应用意义。为了更好地使广大生物学家应用本文生物信息 学研究的成果，文章建立了多个在线生物信息预测分析网站，经不完全 统计，已有来自美国、英国、荷兰、澳大利亚以及中国等世界各地的研 ，j f 克童声謦堡主兰垡堡奎： 究科学家通过互联网访问并使用所建立的在线生物信息服务网站，为科 学研究的快速发展提供了强有力的支持。 本文的创新性表现在： ( 1 ) 提出高维核空间属性加权核聚类算法。并从理论上证明了收敛 性： ( 2 ) 讨论了合作聚类模型，该模型在研究实际社会中的关联模型上 有重要意义： ( 3 ) 通过模拟生物人眼非均匀采样的特点，提出一种新颖的视觉聚 类算法： ( 4 ) 提出基于“有监督”聚类算法的蛋白结构预测模型； ( 5 ) 提出集成分类器框架模型，有效地解决了伪氨基酸蛋白离散模 型的维数选择问题；通过在诸多应用对象、算法上的实验表明， 该框架是切实可行的； ( 6 ) 采用新型的g o 蛋白离散模型分析预测蛋白亚细胞位置。该文 所研究的细胞位置数目是目前该研究领域最多的，进一步加强 了该研究的实际应用意义；另外，本文的研究涵盖了多个应用 对象，如人类细胞、植物细胞、细菌细胞以及病毒等； ( 7 ) 为了进一步加速研究成果的转化及应用，建立了多个在线生物 服务网站。通过互联网，世界各地的科学家可以在线使用生物 信息预测服务。 关键词；数据挖掘，聚类分析，生物信息学，机器学习，模糊c 均值， 信息理论，采样定理，证据理论，集成分类器，蛋白结构预测， 膜蛋白识别，细胞网络 i d j j i f 麦童声事堡主兰垒兰塞 r e s e a r c h e so nd a l am i n i n gm o d e l i n gt h e o r i e s a n di t sa p p l i c a t i o n si nb i o i n f o r m 嗡t i c s a b s t 雕忆t i nt h ep a s td e c a d e s ，l a r g ea m o u n to fd a t ai so b t a i n e dw i t ht h ef a s t d e v e l o p m e n t o fs c i e n c e ，e c o n o m i ca n ds o c i e t y h o wt of i n dv a l u a b l e k n o w l e d g ea n dr u l e sf r o mt h e s ed a t ai s ac r i t i c a lp r o b l e m d a t am i n i n g r e s e a r c h e sa r ep r o p o s e dt os o l v et h i sp r o b l e m ，w h i c hc o m b i n e ss t a t i s t i c s ， d a t a b a s e ，m a c h i n el e a r n i n gt e c h n i q u e se r e c l u s t e r i n ga n a l y s i si so n eo ft h em o s ti m p o r t a n tr e s e a r c ha r e a si nd a t a m i n i n g i nt h er e a lw o r l d ，w eo f t e nh a v et od e a lw i t ht h eh i 曲- d i m e n s i o n a l d a t a s e t ，i nw h i c h , d i f f e r e n ta t t r i b u t e sw i l lc o n t r i b u t ed i f f e r e n t l yt oe a c h c l u s t e ri nm o s tc a s e s c o n s i d e r i n gs u c h - ap r o b l e m , ak i n do fa t t r i b u t e w e i g h t e df i l z z yk e r n e lc l u s t e r i n ga l g o r i t h mi sp r o p o s e d t h i sn e wk e r n e l c l u s t e r i n ga l g o r i t h mc a nr e f l e c tp r o p e r l yt h ea t t r i b u t ei m p o r t a n c ef o re a c h c l u s t e ra n dh e n c ec a l l y i e l dm u c hh i g h e rc l u s t e r i n ga c c u r a c yt h a n t h e c o n v e n t i o n a lc l u s t e r i n ga l g o r i t h m s a n o t h e rt h i n gw eo f t e ne n c o u n t e ri nt h e r e a lw o r l di st h a to l l ed a t a s c ti si n d e p e n d e n to fo t h e r sb u ta l s oc o o p e r a t ew i t h o t h e r s 砒t h es a m et i m e b a s e do ns u c hc o o p e r a t i v ec o n s t r a i n t s ，n e w i n f o r m a t i o nb a s e dc o l l a b o r a t i v ec l u s t e r i n ga l g o r i t h mi sp r o p o s e d s u c h c o l l a b o r a t i v ec l u s t e r i n ga l g o r i t h mc o n s i d e r st h ei n f l u e n c ef r o mo t h e r d a t a s e t sa n dt h ec o r r e s p o n d i n gc l u s t e r i n gr e s u l t sw i l lb em o r ef l e x i b l e e y e s v a b s t r a c t a r et h em a i no r g a n st h a th u m a nu s et og r o u po b j e c t sa n df i n dt h ei m p o r t a n t i n h e r e n tr e l a t i o n sb e t w e e nt h eo b j e c t s s o ，d e s i g n i n gt h ec l u s t e r i n gm e t h o d s t h r us i m u l a t i n gt h ev i s u a ls y s t e m sw i l lh e l pt os o l v es o m eb a s i cp r o b l e m s w i t ht h ec o n v e n t i o n a lc l u s t e r i n ga l g o r i t h m s b ys i m u l a t i n gt h eu n e v e n s a m p l i n gm e c h a n i s mo fh u m a ne y e s ，an e wv i s u a lc l u s t e r i n ga l g o r i t h mi s p r o p o s e d ，w h i c hw i l lp r o v i d es o m en e wi d e a si n t h e c l u s t e r i n ga n a l y s i s r e s e a r c h e s w i t ht h ef a s td e v e l o p m e n to fb i o l o g ys c i e n c e ，w ea r en o wf a c e dw i t h a l le x p l o s i o no fb i o l o g yd a t a i ti si m p o s s i b l et ok n o wa l lt h ed a t ab a s e do n t h ec o n v e n t i o n a lb i o l o g ye x p e r i m e n t s s u c hag a pc a l l sf o rf a s ta n da c c u r a t e s o l u t i o n sf r o mb i o i n f o r m a t i c s b i o i n f o r m a t i c si san e wa n dh o tr e s e a r c ha r e a , c o m b i n i n gc o m p u t e rs c i e n c ea n db i o l o g ys c i e n c e m a n y d a t a m i n i n g t e c h n i q u e s ，s u c h a sc l u s t e r i n ga n a l y s i s ，h a v eb e e nu s e dt oa n a l y z et h e b i o l o g yd a t a w eh a v ep r o p o s e dt ou s e “s u p e r v i s e dc l u s t e r i n ga l g o r i t h m t o p r e d i c tp r o t e i ns t r u c t u r e s ，w h i c hi sd e m o n s t r a t e dab e t t e rc h o i c et h a nt h e u n s u p e r v i s e d m e t h o db e c a u s ei ti n c o r p o r a t e st h ec l a s sl a b e li n f o r m a t i o ni n t h et r a i n i n gd a t a s e t i nt h ep r o t e o m i c sr e s e a r c h e s ，o n eo ft h ei m p o r t a n ts t e p s i st od i s c r e t et h ep r o t e i ns e q u e n c e t h es 0 一c a l l e dp s e u d oa m i n oa c i d c o m p o s i t i o n ( p s e a a ) i sd e m o n s t r a t e d t ob em o r ee f f e c t i v et h a nt h e c o n v e n t i o n a l2 0 - da m i n oa c i d ( a a ) c o m p o s i t i o nb e c a u s ep s e a ai n c l u d e s m o r es e q u e n c eo r d e ri n f o r m a t i o n h o w e v e r , h o wt os e l e c tt h ed i m e n s i o no f p s e a ai sac r i t i c a lp r o b l e ma n di nt h ep a s tr e s e a r c h e si tw a sd e t e r m i n e db y t r i a la n de r r o rm e t h o d s s u c hd i m e n s i o ns e l e c t i o ns t e pi sv e r yu n c o n s t a n t a n df o r d i f f e r e n ta p p l i c a t i o n sa n da l g o r i t h m s ，w ew i l lh a v ed i f f e r e n t s e l e c t i o n s w ep r o p o s e dt ou s ee n s e m b l ec l a s s i f i e rt os o l v et h i sp r o b l e m ，着支互z 謦坚主兰篁望苎 e n s e m b l ec l a s s i f i e rf u s e sm a n yi n d e p e n d e n tc l a s s i f i e r s ，w o r k i n gi nd i f f e r e n t d i m e n s i o n s f u r t h e re x p e r i m e n t ss h o wt h a tm u c hh i g h e rp r e d i c t i o na c c u r a c y c a nb eo b t a i n e di nm o s tc a s e sb e c a u s ee n s e m b l ec l a s s i f i e rc a nc a t c ht h e c o r e sf r o md i f f e r e n ts i d e s e n s e m b l ec l a s s i f i e ri sav e r ye f f e c t i v ea n d f l e x i b l em e t h o dt os o l v et h ed i m e n s i o ns e l e c t i o n p r o b l e m i np s e a a c o m p o s i t i o n i nt h ep a s tf e wy e a r s ，w i t ht h ed e v e l o p m e n to fl i f es c i e n c e ，g e n e o n t o l o g y ( g o ) d a t a b a s ew a sc o n s t r u c t e da n db e c a m em o r ea n dm o r e i m p o r t a n ti nl i f es c i e n c er e s e a r c h e s b a s e do nt h eg od i s c r e t em o d e l ，w e h a v e d e v e l o p e d s e v e r a l p r e d i c t o r s f o r t h e p r e d i c t i o n o ft h e p r o t e i n s u b c e l l u l a rl o c a t i o n sf o rh u m a n , p l a n t ，b a c t e r i ae t c v a r i o u se x p e r i m e n t s h a v ed e m o n s t r a t e dt h a tg od i s c r e t em o d e li sak i n do fh i g h e rl e v e ld i s c r e t e m o d e la n db e t t e rp r e d i c t i o na c c u r a c yi so b s e r v e da c c o r d i n g l y f u r t h e r m o r e , t h eb e n c h m a r kd a t a s e t sc o n s t r u c t e dc o v e rt h em o s ts u b c e l l u l a rl o c a t i o n si n t h i s l i t e r a t u r et i l ln o w , w h i c hc a ng r e a t l yi m p r o v et h ep r a c t i c a b i l i t yo ft h e d e v e l o p e dp r e d i c t o r s i no r d e rt os i m p l i f yt h eu s eo fo u rb i o i n f o r m a t i c s r e s e a r c hf r u i t s ，s e v e r a lo n - l i n eb i o i n f o r m a t i c sp r e d i c t i o nw e bs e r v e r sa r e c o n s t r u c t e d , w h i c hc a nb ea c c e s s e dt h r ui n t e r n e t t i l ln o w , m a n yb i o l o g y s c i e n t i s t sf r o mu s a , e n g l a n d ，h o l l a n d , a u s t r a l i aa n dc h i n ae t ch a v ev i s i t e d a n du s e do u rw e bs e r v e r s w eb e l i e v et h a ts u c hak i n do fe a s y t o u s ew e b s e r v e r sw i l lp r o m o t et h ed e v e l o p m e n to f b i o l o g ys c i e n c eg r e a t l y n e wc o n t r i b u t i o n so f t h i sp a p e ra r ea sf o l l o w s ： ( 1 ) n e wa t t r i b u t ew e i g h e df u z z yk e r n e lc l u s t e r i n ga l g o r i t h mi sp r o p o s e d a n di t sc o n v e r g e n c ep r o p e r t yi st h e o r e t i c a l l yp r o v e d ； ( 2 ) c o l l a b o r a t i v ec l u s t e r i n gm o d e li sd i s c u s s e d , w h i c hi sav e r y v i i a b s t r c t i m p o r t a n tm o d e li nt h er e a lw o r l d ； ( 3 ) b ys i m u l a t i n gt h em e c h a n i s mo f h u m a ne y e s ，ak i n do fan e wv i s u a l c l u s t e r i n ga l g o r i t h mi sp r o p o s e d ； ( 4 ) w ep r o p o s et h e “s u p e r v i s e d c l u s t e r i n ga l g o r i t h mt op r e d i c tt h e p r o t e i ns t r u c t u r e s ； ( 5 ) e n s e m b l ec l a s s i f i e r i s p r o p o s e df o rp r o t e o m i c sr e s e a r c h e s ，w h i c h c a l le f f e c t i v e l ys o l v et h ed i m e n s i o ns e l e c t i o np r o b l e mi nt h ep s c a a d i s c r e t em o d e l v a r i o u se x p e r i m e n t sd e m o n s t r a t et h ef e a s i b i l i t yo f e n s e m b l ec l a s s i f i e r ； ( 6 ) s e v e r a lp r e d i c t o r s a r ed e v e l o p e db a s e do ng od i s c r e t em o d e lt o p r e d i c tt h ep r o t e i ns u b c e l l u l a rl o c a t i o n sf o rh u m a nc e l l ，p l a n tc e l l ， b a c t e r i ac e l le t c t h es t r i n g e n tb e n c h m a r kd a t a s e t sc o n s t r u c t e di n t h i sp a p e rc o v e rt h em o s ts u b c e l l u l a rl o c a t i o n si nt h i sl i t e r a t u r et i l l n o w ； ( 7 ) 。t h e s i m p l e - t o u s e o n l i n eb i o i n f o r m a t i c sw e bs e r v e r s a r e c o n s t r u c t e d ，w h i c hc a ng r e a t l yp r o m o t et h ed e v e l o p m e n to fl i f e s c i e n c e k e y w o r d s ：d a t am i n i n g ，c l u s t e r i n ga n a l y s i s ，b i o i n f o r m a t i c s ，m a c h i n e l e a r n i n g , f u z z y c - m e a n s ，i n f o r m a t i o nt h e o r y , s a m p l i n gt h e o r y , e v i d e n c e t h e o r y , e n s e m b l ec l a s s i f i e r , p r o t e i n s t r u c t u r e p r e d i c t i o n , m e m b r a n ep r o t e i n t y p er e c o g n i t i o n ，c e l l u l a r n e t w o r k 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：i 彩扣八 日期：叫年f 月) ，日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关都门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口 本学位论文属于 不保密 ( 请在以上方框内打“”) 年解密后适用本授权书。 学位论文作者签名：彩杉；吵a 八 指导教师签名： 他 日期：矽d ( 年i 惆) f 日日期：旷，6 年f f 月，7 - 日 1 1 数据挖掘 ，声麦至z 挚堕圭竺垡丝兰 第一章引言 近十几年，随着科学技术的飞速发展，经济和社会都取得了极大的进步，与此 同时，在各个领域产生了大量的数据，如人类对太空的探索、银行每天的巨额交易 数据。显然在这些数据中蕴涵着大量的信息，如何处理这些数据得到有益的信息， 人们进行了很多的研究探索。计算机技术的迅速发展使得处理数据自动化成为可能， 这也推动了数据库技术的极大发展，但是面对不断增加如潮水般的数据，人们不再 满足于数据库的查询功能，提出了深层次问题：能不能从数据中提取信息或知识为 决策服务。也就是说如何从底层的数据转变成一种知识( 图1 1 ) 。就数据库技术而 言已经显得无能为力了，同样，传统的统计技术也面临着极大的挑战。这就急需有 新的方法来处理这些海量般的数据。于是，人们结合统计学、数据库、机器学习等 技术，提出数据挖掘f l 2 来解决这一难题。 图1 - 1 数据金字塔 f i g u r e1 1 d a t ap y r a m i di nt h er e a lw o r l d 数据挖掘的历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度很快，加 之它是多学科综台的产物，目前还没有一个完整的定义，人们提出了多种数据挖掘 的定义，例如： s a s 研究所( 1 9 9 7 ) ：“在大量相关数据基础之上进行数据探索和建立 第一章引言 相关模型的先进方法”。 b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大量的数 据中发现有意义的新关系、模式和趋势的过程”。 h a n de ta l ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价 值信息的过程”。 我们认为：数据挖掘就是从大量的数据中挖掘出可能有潜在价值的信息的技 术。这些信息是可能有潜在价值的，能够支持决策，可以为企业带来利益，或者为 科学研究寻找突破口。 现今资料流通量之巨大已到了令人i 疆舌地步，就实际限制而言，便遇到了诸如 巨量的纪录，高维资料等传统分析技术上的困难。这些困难让我们不得不利用d a t a m i n i n g 技术。图1 2 为从海量的数据中通过数据挖掘等技术形成知识的过程。 图1 2 数据转化成知识过程 f i g u r e1 - 2 t h ep r o c e s so f m i n i n gk n o w l e d g ef r o mt h el a wd a t a 数据挖掘综合了多个学科技术，有很多的功能，当前的主要功能如下： 1 ) 分类：按照分析对象的属性、特征，建立不同的组类来描述事物 例如：银行部门根据以前的数据将客户分成了不同的类别，现在就 可以根据这些来区分新申请贷款的客户，以采取相应的贷款方案。 ，芦交童声謦堡圭兰焦垒塞 2 ) 聚类：识别并分析内在的规则，按照这些规则把对象分成若干类。 例如：将申请人分为高度风险申请者、中度风险申请者、以及低度 风险申请者等。 3 ) 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发 生的这样一种联系。例如：每天购买啤酒的人也有可能购买香烟， 可能性有多大，可以通过关联的支持度和可信度来描述。与关联不 同，序列是一种纵向的联系。例如：今天银行调整利率，明天股市 的变化。 4 ) 预测：把握分析对象发展的规律，对未来的趋势做出预见。例如： 在蛋自质生物信息学中，根据已有的蛋自质结构知识，对新发现或 合成的蛋白质预测其规律等。 5 ) 偏差的检测：对分析对象中少数的、极端的特例的描述，揭示内在 的原因。例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银 行为了稳健经营，就要发现这5 0 0 例的内在因素，减小以后经营的 风险。 作为一门处理数据的新兴技术，数据挖掘有许多的新特征。首先，数据挖掘面 对的是大量的数据，这也是数据挖掘产生的原因。其次，数据可能是不完全的、有 噪声的、随机的、有复杂的数据结构、以及高维的。最后，数据挖掘是i 午多学科的 交叉，运用了统计学、计算机、数学等学科的技术。以下是常见的算法和模型： ( 1 ) 传统统计方法：抽样技术：我们面对的是大量的数据，对所有的数 据进行分析是不可能的也是没有必要的，就要在理论的指导下进行合 理的抽样，多元统计分柝：因子分析，聚类分析等。统计预测方 法，如回归分析，时间序列分析等。 ( 2 ) 利用模糊集合理论，对实际阅题进行模糊判断、模糊决策、模糊模式识 别、模糊簇聚分析。 ( 3 ) 可视化技术：用图表等方式把数据特征直观地表述出来，如直方图等。 可视化技术面临的一个难题是高维数据的可视化。 第一章引言 ( 4 ) 决策树：利用一系列规则划分，建立树状图，可用于分类和预测。常 用的算法有c a r t 、c h a i d 、i d 3 、c 4 5 、c 5 o 等。 ( 5 ) 神经网络：模拟人的神经元功能，经过输入层、隐藏层、输出层等， 对数据进行调整、计算，最后得到结果。用于分类和回归。 ( 6 ) 遗传算法：基于自然进化理论，模拟基因联合、突变、选择等过程的 一种优化技术。 ( 7 ) 关联规则挖掘算法：关联规则是描述数据之间存在关系的规则，形式 为“a l a 2 a n b l 八b 2 b n ”。一般分为两个步骤： 求出大数据项集。用大数据项集产生关联规则。 最后需要强调的是，数据挖掘是一个以人为中心的，需要人的指导和于预的过程。 它的各个环节；挖掘目标( 知识发现的范围) 的确定、挖掘方法的选择和调整、挖 掘结果的评估和应用，都将由人进行。 1 2 生物信息学 生物特征识别翻译自“b i o m e t r i c s ”，也译作生物统计学或生物测量学 “b i o m e t r i c s ”或“b i o m c t r y ”最早出现于2 0 世纪初，特指利用统计和数学的方法 分析生物领域数据的学科。比如利用统计方法分析小麦品种与产量的关系；不同治 疗方法的疗效；水源质量对身体健康的影响。这些研究都属于生物特征识别的研究 范畴。近年来，“b i o m e t r i c s ”也指称新诞生的、使用生物性状来识别个体的新技术， 比如视网膜、虹膜扫描、人脸识别、手势识别等技术。在最近的生物特征识别会议 上也以把生物序列分析与生物数据类型预测列为该学科的研究内容。 世纪之交，人类基因组计划取得根本性进展，特别是在2 0 0 0 年的第一个春天， 人类首次获得自身基因组的全部序列，意味着人类基因组研究将全面进入信息提取 和数据分析的全面阶段，现在已进入后基因组时代，分子生物信息的研究、开发和 应用，已经成为当前一个前沿领域和研究热点。- - f - 新兴的边缘学科一生物信息学 应运而生。 4 爵芙耋走学 博士学位论文 生物信息学硼是一门生物学与信息科学交叉而形成的年轻学科，旨在运用信息 学、物理学、化学、数学、计算机科学、系统科学的理论和方法来研究生物系统和 生物过程的信息量和信息流，包含着基因组信息的获取、存储、分配、分析和解释 的所有方面。其中基因组信怠学、结构生物信息学和神经信息学是较热门的分支。 生物信息学由数据库、应用软件和因特n - - 大要素组成。生物信息学研究在国外开 展得比较早，在我国还处于起步阶段，一般生物信息学研究涉及比较基因组学、大 规模基因组测序中的信息分析、新基因和新s n p 的发现、菲编码区信息分析、遗传 密码起源和生物进化、蛋白质结构与功能预测、生物大分子的结构模拟与药物设计、 生物数据库及可视化应用软件的研究与开发等。其中蛋白质结构与功能预测是生物 信息学研究的重要方面。 目前，生物信息学已成为分子生物学研究中一个非常重要的辅助手段，是对海 量数据分析和处理的不可缺少的必备工具，主要集中在以下层面： ( 1 ) 生物数据的获取、分析和数据库的构建 核酸：序列同源性比较，分子进化树的构建，结构信息( 碱基组成 和分布、酶切位点、重复片段、模式序列m o t i f 等) 分析。开放阅 读框分析及外显予预测，基因预测，r n a 的二级结构分析预测， 表达谱分析，以及基因调控网络分析等；大规模测序所得数据的拼 接、注释、存储和管理。 蛋自质：序列同源性比较，分子进化树的构建，理化性质计算，模 式序列搜寻，抗原性分析，二级结构预测和高级结构的模拟，蛋白 质功能分析，氨基酸残基的特性分析，蛋白组学方法研究等。 公共数据；目前有大量的、公开的、功能未知的序列数据，有选择 性地对这些数据进行分析，有可能得到有潜力的序列，找到隐藏在 海量数据中的有用信息，加快生物学实验的进程。 ( 2 ) 指导分子生物学实验 依据对实验数据的分析所得的结论来设计下一阶段的实验；或利用软件来设计实 验，例如：基因芯片中的探针设计、克隆策略设计；模拟内切酶图谱或蛋白酶对相 第一章引言 应的底物分子切割后的电泳行为等。 ( 3 ) 有效地管理海量实验数据 一个规范的实验室，实现实验室的信息化管理，用计算机来管理实验数据是必 要的，这能促进对实验得到的大量生物数据的有效分析。理想的此类软件应该提供 从试剂、实验材料的管理到最后结果的注释输出等全过程的支持。 当前一些发达国家的政府、科研机构均非常重视，纷纷建立相应的机构或部门 进行这方面的研究、开发和服务。如美国国家生物信息中心( n a t i o n a lc e n t r eo f b i o t e c h n o l o g yl n f o r m a t i o n ，n c b i ) 、欧洲分子生物学| 卅络( e u r o p e a nm o l e c u l a r b i o l o g y n e t w o r k ，e m b n e t ) 。另外一些生物公司亦非常重视生物信息学并组建相关的部门 来从事相应的研发和应用。 在我国，生物信息学随着人类基因组研究的展开才刚刚起步，但己显露出蓬勃 发展的势头。许多科研单位已经开始或准备开始从事这方面的研究工作。北京大学 的生物信息研究团队建立起了e m b l 的镜像数据库，并提供部分的检索服务 ( h t t p ：w w w i p c p k u e d u c n m i r r o r m i r r o r h t m lh t t p ：w w w e b i p k u e d u c n ) 。在复旦大 学遗传学研究所，为克隆新基因而建立的一整套生物信息系统也已初具规模。中科 院上海生化所、生物物理所等单位在结构生物学和基因预测方面也有相当的基础。 在生物信息学中，特别是蛋白质功能预测和序列分析的问题中，最有挑战性的 问题就是如何从长短不一、纷繁复杂的序列中提取与其功能和与二级、三级结构相 对应的特征，该问题已成为生物信息发展的一个瓶颈。再加上生物实验非常耗时、 昂贵而且结果不是非常可靠，更增加了特征提取的难度。 诚如以上所言，生物信息学的研究范围十分广泛，本文主要针对蛋白组学中的 若干重点问题展开了研究，如蛋白结构预测、膜蛋白类型预测、蛋白亚细胞定位以 及蛋白折叠预测分析等。 1 3 预备知识 1 3 i 聚类分析理论 聚类分析是数据分析、理解与数据可视化的有效工具【1 0 ，8 9 1 ，是数据挖掘建模技 ，i 寅童工謦 博士学位论文 术的重要研究内容。给定一个数据集f = x ，x ，x 。c ，聚类分析的目的在于 根据某种相似性原则将r 分成c 个类别。聚类分析是统计理论、数据挖掘和模式识 别领域中的一个重要问题 i o - 2 “，已经在众多领域得到了广泛的应用；在商业竞争中， 聚类分析能帮助商家在客户数据库中根据客户的购物模式发现不同的组别，从而更 优地决策；在信息迅速增长的今天，聚类算法能有效的进行文本分类；作为数据挖 掘的有效工具，聚类分析能帮助理解数据的不同分布，观察各个类别的不同性质， 从而对其中感兴趣的类别进行进步的分析；另外，聚类分析在生物信息处理、模 式识别等领域同样有着重要的应用价值。鉴于聚类算法的重要理论与应用价值，许 多学者对聚类算法展开了深入的研究，提出了多种实用的聚类算法，按不同的分类 性质，大致可以把目前的聚类算法分成( 图1 3 ) ：( 1 ) 基于分割的聚类算法5 1 ； ( 2 ) 层次聚类算法i l 卫】，包括自上而下、自下而上两种层次聚类算法；( 3 ) 基于密 度的聚类算法【2 3 1 ；( 4 ) 基于网格的聚类算法【2 4 l ；( 5 ) 基于模型的聚类算法【2 5 闽。对 于常用的基于分割的聚类算法而言，其一般的方法是用c 个类中心向量 v ，u = l ，2 ，c ) r “来代表每个类，根据相似性原则把样本1 1 分到第，类别中。 图1 - 3 聚类算法分类 f i g u r e1 - 3 c l u s t e r i n ga l g o r i t h m 为了达到有效的聚类，我们常常可定义一个目标函数，： #r ，= 厂( x 。，v ，) d 2 ( x 。，v ) ( 1 1 ) - lj t i 第一章引言 这里，( k ，v ，) 表示根据概率论或模糊集合论而定义的某相似度量，d 2 ( x ，v j ) 表示在样本x t 与中心v ，间的距离度量，k 为样本数目。聚类的任务就是寻找 v i ，v 2 ，v c ，使得，达到最小如果，( x 。，v ，) 是某个概率相似性度量，则其聚类算 法被称作概率聚类算法；如果，( x 。，v ，) 是某个模糊相似性度量，则其聚类算法被称 作模糊聚类算法。 1 3 2 机器学习 机器学习所关注的问题是：机器学习算法程序如何随着经验积累自动提高性 能。近年来，机器学习被成功地应用于很多领域，从检测信用卡交易欺诈的数据 挖掘程序，到获取用户阅读兴趣的信息过滤系统，再到能在高速公路上自动行驶的 汽车，以及当前计算机科学领域内的研究热点如语音识别、人脸检测与识别、指纹 识别、手写体识别、多媒体及文本检索、网络管理及网络安全等，甚至到模仿人类 行为的智能机器人研究等。 目前，机器学习有多种定义形式，还没有一个被普遍接受的统一