（运筹学与控制论专业论文）生物信息数据挖掘中的若干方法及其应用研究.pdf

大连理丁大学博十学位论文 摘要 许多生物( 包括人在内) 的基因组测序已经完成或接近完成，在揭示这些巨量数据 所蕴涵的信息时，产生了- - f - 新的交叉学科一生物信息学，通过对生物学实验数据的获 取、加工、存储、检索与分析，进而达到揭示数据所蕴含的生物学意义的目的。数据挖 掘技术用于在数据库中发现潜在有用的知识，在生物信息学研究当中，j f 发挥着越来越 重要的作用，而且取得了丰硕的成果。本文探讨若干生物信息数据挖掘的方法及其应 用，主要工作如下： 1 用支持向量机和f d o d 两种方法对同源寡聚蛋白质进行了分类研究。g a r i a nr ， 和用决策树方法从蛋白质一级结构出发对同源二聚体和同源非二聚体进行了分类，证实 了蛋白质一级结构即氨基酸序列包含四级结构信息。本文用s v m 和f d o d 两种方法对 同源二聚体和同源非二聚体进行分类，利用原始序列的子序列分布作为特征向量。采用 和决策树方法同样的数据集，两种方法均大幅度提高了预测准确率。本文也对同源二聚 体、同源三聚体、同源四聚体和同源六聚体进行了分类，取得了好的结果。 2 构造了基于线性规划的p s v m 分类器。s c h 6 1 k o p fb 等提出的基于二次规划的 v 一支持向量机( y s v m ) 相比标准的s v m ，其优势在于可以控制支持向量的数目和误 差，但由于增加了模型的复杂性，限制了其应用。本文构造了一种基于线性规划的 v s v m 分类器，模型简单，参数r 具有明确的意义，同样可以控制支持向量的数目和 误差，可以直接利用比较成熟的线性规划算法。数值试验表明，本文提出的基于线性规 划的v s v m 的训练速度要比基于二次规划的v s v m 快得多，而分类效果两者相当。 3 提出了无参数鲁棒线性规划支持向量机分类的牛顿算法。m a n g a s a r i a nol 最近 提出的无参数鲁棒线性规划支持向量机克服了标准s v m 需要选取正则化参数等一些缺 点，其模型是一个线性规划。本文给出了这种线性规划的精确的最小2 一范数解，在此 基础上提出了快速的牛顿算法，此算法只需要一个线性方程组解算器。理论、数值实验 以及在癌症基因表达数据分类上的应用都表明了用牛顿算法实现的无参数鲁棒线性规划 支持向量机模型合理、简单，算法快速、容易实现。 4 用f d o d 方法对d n a 序列进行相似性分析。序列的比较是生物信息学中最常用 的研究手段之一，其根本任务是发现序列之间的相似性和不相似性。序列比对是序列比 较的主要方法，但有其不足之处，所以很多人寻求用其他方法来比较d n a 序列。本文 摘要 用f d o d 方法对d n a 序列进行相似性分析，只考虑了序列的级结构，同时在一定程 度上考虑了序列中的碱基顺序。用不同的子序列长度对1 1 个物种的g l o b i n 基因的第 一个外显子序列进行了相似性分析，证实了该方法是有效的。 5 提出了d n a 序列的一种新的2 一d 图形表示，给出了相应的数值刻划方法，并 应用到d n a 序列的相似性分析。d n a 序列的图形表示方法可以使我们更直观地观察 d n a 序列，加强对序列的比较、分析和识别。基于代数中的同态思想和核酸碱基的化 学结构分类提出了d n a 序列的一种新的简单直观的2 一d 图形表示方法，这种图形表示 方法能够反映碱基的分布情况；避免了序列几何图形表示方法中曲线的重叠和交叉；可 以导出相应的数值刻划。相似性分析的结果表明这种新的图形表示和数值刻划方法是合 理的和有效的。 关键词：生物信息学；数据挖掘；支持向量机：f d o d ；蛋白质；d n a ；图形表示 i i 大连理_ r ：大学博十学位论文 s t u d y o ns o m ed a t am i n i n gm e t h o d s f o r b i o l o g i c a li n f o r m a t i o n a n dt h e i ra p p l i c a t i o n a b s t r a c t t h es e q u e n c i n go fs e v e r a lg e n o r n e s ，i n c l u d i n gt h eh u m a ng e n o m e ，h a sp r o v i d e dav a s t a m o u n to f d a t aw h i c hm u s tb ee x p l o i t e d b i o i n f o r m a f i c si se s s e n t i a l l yt h es c i e n c eo f t a k i n gt h i s i nb i o i o f o r m a t i c sr e s e a r c h e r s s t u d y h o wt o c a p t u r e ，m a n a g e ，d e p o s i t ，r e t r i e v e ，a n a l y z e b i o l o g i c a l i n f o r m a t i o ne n a b l i n gt h ed i s c o v e r yo fe n c y c l o p e d i cb i o l o g i c a l k n o w l e d g e d a t a m i n i n gt e c k n o l o g y i su s e dt oe x t r a c tp o t e n t i a la n du s e f u li n f o r m m i o nf r o mt h ed a t a b a s e s , a n di s p l a y i n g a l li n c r e a s i n g l yi m p o r t a n tr o l ei nt h e s t u d yo f b i o i o f o r m a t i c sa n d b e a rf e r t i l ef r u i t s t h i s p a p e ri n v e s t i g a t e s8 0 m e d a t a m i n i n g m e t h o d sf o rb i o i n f o r m a t i c sa n dt h e i ra p p l i c a t i o n ，t h em a i n w o r ki ss u m m a r i z e da sf o l l o w i n g s ： 1 b o t hs u p p o r tv e c t o rm a c h i n ea n df d o d m e t h o d sa r ea p p l i e dt oc l a s s i f i c a t i o no f h o m o o l i g o m e r i cp r o t e i n s g a r i a nr u s e dd e c i s i o nt r e em e t h o dt od i s c r i m i n a t eb e t w e e nh o m o d i m e r s a n dn o n - h o m o d i m e r sf r o mt h ep r i m a r ys t r u c t u r ea n ds h o w e dt h a tp r o t e i np r i m a r ys e q u e n c e c o n t a i n sq u a t e r n a r ys t r u c t u r ei n f o r m a t i o n i nt h i sp r e s e n tw o r k ，s u p p o r tv e c t o rm a c h i n ea n d f d o dm e t h o d sa r ea p p l i e dt o d i s c r i m i n a t i n g b e t w e e nh o m o d i m e r sa n dn o n - h o m o d i m e r s ， w h e r ef o rt r a i n i n ga n d t e s t i n gp r o t e i np r i m a r ys e q u e n c e s ，t h e i rs u b s e q u e n c e d i s t r i b u t i o n sa c ta s i n p u tv e c t o r s t h ec l a s s i f i c a t i o nr e s u l t so f t h et w om e t h o d sa l em u c hb e t t e rt h a nt h a to ft h e p r e v i o u sm e t h o do i lt h es a i d _ ed a t as e t t h et w om e t h o d sa r ca l s oa p p l i e dt od i s c r i m i n a t i n g b e t w e e nh o m o d i m e r s ，h o m o t r i r n c r s ，h o m o t e t r a n l e r sa n dh o m o h e x a m e r s 丘d mt h e p r o t e i n p r i m a r ys t r u c t u r e ，a n dt h e r e s u l t sa r ea l s og o o d 2 an e wv s v mc l a s s i f i e rb a s e do nl i n e a rp r o g r a m m i n gi sp r o p o s e d t h ev s v m c l a s s i f i e r p r o p o s e d b y s c h n k o p f b h a s t h ea d v a n t a g e o f c o n t r o l l i n g n u m b e r s o f s u p p o r t v e c t o r s a n de r r o r sc o m p a r e dt or e g u l a rs v m ，h o w e v e r , i t sf o r m u l a t i o ni sm o r ec o m p l i c a t e d ，w h i c h c o n f m e si t sa p p l i c a t i o n s 。w ep r e s e n tan e wa n ds i m p l e rl ，一s v mc l a s s i f i e rb a s e do nl i n e a r p r o g r a m m i n g ，t h ep a r a m e t e r ya l s oh a si m p l i c i ts e n s eo fc o n t r o l l i n gn u m b e r so fs u p p o r t v e c t o r sa n de r r o r s f u r t h e r m o r ew ec a nu s ee f f e c t i v el i n e a rp r o g r a m m i n gs o l v e r sa v a i l a b l e n u m e r i c a lt e s t ss h o wt h a to u ry s v mb a s e do nl i n e a rp r o g r a m m i n gi sm u c hf a s t e rt h a n o r i g m a l v s v ma n d p e r f o r m sc o m p a r a b l y i na c c u r a c y 3 a n e w t o n m e t h o d f o r p a r a m e t e f l e s sr o b u s t l i n e a r p r o g r a m a r 曲gs u p p o r t v e c t o r m a b t 血l e i sp r e s e n t e d p a r a m e t e r l e s sr o b u s tl i n e a r p r o g r a m m i n gs u p p o r t v e c t o rm a c h i n ef o rc l a s s i f i c a t i o n ， i i i 摘要 r e c e n t l yp r o p o s e db ym a u g a s a r i a n0l ，s o l v e dt h i s i s s u eo fd e t e r m i n i n gt h es i z eo fr e a t p a r a m e t e r w e h a v ed i s c u s s e dt h el e a s t2 一n o n ns o l u t i o no ft h ep a r a m e t e r l e s sl i n e a r p r o g r a m m i n gp r o b l e m a n dt h e np r e s e n t e daf a s tn e w t o nm e t h o d t h ea l g o r i t h mr e q u i r e so n l ya l i n e a re q u a t i o ns o l v e r n l ct h e o r y n u m e r i c a lt e s l sa n da p p l i c a t i o nt og e n ee x p r e s s i o nd a t af o r c a l l c e l c l a s s i f i c a t i o nd e m o n s t r a t et h a ti ti ss i m p l e ，f a s ta n de a s i l ya c c e s s i b l e 4f d o di s a p p l i e d t o a n a l y n so fs i m i l a r i t i e s o fd n as e q u e n c e s c o m p a r i s o no f s e q u e n c e s i so n eo f t h em o s tc o n l r l l o ns t u d ym e a n si nb i o i n f o r m a t i c s c o m p a r i s o no f s e q u e n c e s a i m sa ta n a i y z i n gt h es i m i l a r i t ya n dd i s s i m i l a r i t yo fd n as e q u e n c e s i tm a i n l yd e p e n d s0 n s e q u e n c ea l i g n m e n t , w h i c hh a ss o m es h o r t c o m i n g s s op e o p l et r yt od e v e l o pn e w m e t h o d s f d o di su s e dt oa n a l y z et h es i m i l a r i t i e so fd n a s e q u e n c e sf r o mt h ep r i m a r ys t r u c t t t r e t h e e f f e c to fr e , d u eo r d e ra i o n gt h es e q u e n c ei st a k e ni n t oa c c o u n ti ns o m ee x t e n t f o rd i f f e r e n t l e n g t ho f s u b s e q u e n c e t h ea p p r o a c hi si l l u s t r a t e dt h r o u g ht h ee x a m i n a t i o no f s i m i l a r i t i e sa m o n g t h ec o d i n gs e q u e n c e so ft h ef i r s te x o no f 口一g l o b i ng e n eo f11d i f f e r e n ts p e c i e s 1 1 1 er e s u l t s d e m o n s w a t et h a tf d o dm e t h o di se f f e c t i v e 5 an o v d2 - 1 3g r a p h i c a lr e p r e s e n t a t i o no fd n a s e q u e n c e sa n dc o r r e s p o n d i n g n u m e r i c a l c h a r a c t e r i z a t i o na p p r o a c ha r ep r o p o s e d a n dt h e na p p l i e dt oe x a m i n i n gt h es i m i l 撕t i e so fd n a s e q u e n c e s g 姊h i c a lr e p r e s e n t a t i o n so fd n as e q u e n c e sa l l o wv i s u a li n s p e c t i o no fd a t a , m a d c a nf a c i l i t a t et h e a n a l y s i s c o m p a r i s o n a n di d e n t i f i c a t i o no fs u c h s e q u e n c e s 1 h sp a p e r c o n s i d e r san o v e l2 - d g r a p h i c a lr e p r e s e n t a t i o no f d n as e q u e n c e sa c c o r d i n g t oh o m o r n o r p h i s m i n a l g e b r aa n dc h e m i c a l s t r u c t u r ec l a s s i f i c a t i o no fb a s e s 1 1 l er e p r e s e n t a t i o nr e f l e c t st h e d i s t r i b u t i o no fb a s e s ，a v o i d st h ec u r v e s o v e r l a p p i n ga n di n t e r s e c i n gi t s e l fa c c o m p a n y i n g g r a p h i c a lr e p r e s e n t a t i o n s ，a n d a l l o w sn u m e r i c a lc h a r a c t e r i z a t i o n t h ee x a m i n a t i o no f s i m i l a r i t i e si l l u s t r a t e st h el i c i l i t yo f t h e a p p r o a c h k e yw o r d s ：b i o i n f o r m a t i c s ；d a t am i n i n g ；s u p p o r tv e c t o rm a c h i n e ；f d o d ；p r o t e i n ；d n a ； g r a p h i c a lr e p r e s e n t a t i o n 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：日期： 丈连理- = 大学博士学位论文 1 绪论 1 1 选题的背景和意义 近年来，由于计算机和信息技术的快速发展，人们开发了大量的甚至巨型的数据库 用于商务管理、政府办公、科学研究和工程开发等。从这些海量数据中发现有用的知 识，成为一个十分迫切的富有挑战性的课题。知识发现( k n o w l e d g ed i s c o v e r y i n d a b b l e ，k d d ) 和数据挖掘( d a t am i n i n g ，d m ) 技术应运而生【l 吲。知识发现是从数 据库中发现知识的全部过程，知识发现可粗略地分为三个阶段，即数据准备、数据挖掘 以及结果的解释评估。数据挖掘是知谚 发现过程的一个特定的、关键的步骤，是指从数 据库中大量的数据中抽取出潜在的、不显为人知的有用信息、模式和趋势。作为- - f 新 兴的研究领域，数据挖掘涉及诸如数据库、机器学习、模式识别、统计学、人工智能和 应用数学等众多学科。 现代分子生物学的发展，特别是人类基因组计划的实旌，生物学家面对着公共数据 库中数以千兆计的记录。随着测序技术的成熟和工业化，核酸和蛋白质的序列数据迅速 增长，许多生物，包括人在内的基因组序列已经完成或接近完成，在揭示这些巨量数据 所蕴涵的信息时，产生了一门年轻的交叉学科一生物信息学( b i o i n f o r m a t i c s ) 4 - 7 。生 物信息学是生物学与计算机科学以及应用数学等学科相互交叉而形成，它通过对生物学 实验数据的获取、加工、存储、检索与分析，进而达到揭示数据所蕴含的生物学意义的 目的。 生物信息学的研究目标是揭示基因组信息结构的复杂性及遗传语言的根本规律，读 懂人类基因组全部d n a 序列，认识人类自身，揭示遗传、发育和进化的联系。生物信息 学必将大大丰富和发展现有的物理学、生物学、化学、数学、计算机科学、信息科学和 系统科学的理论和方法，从而推动学科群的发展，成为自然科学中多学科交叉的有活力 的、有影响的新领域。相对于其他日渐成熟的学科来说，对生物信息学的研究才刚刚 开始。但是它以巨大的发展潜力吸引着世界各地的科研工作者。可以预见，继电子 信息技术之后的下一个科技革命将由生物信息技术领头。生物信息学成果的应用也会 产生巨大的社会效益和经济效益口】，国际上已经出现了大批的基于生物信息学的公司， 实施了许多生物信息学研究计划。主要与药物设计、基因工程药物、生物芯片、代谢工 程与化学工程密切相关。可以况整个生物信息学研究主要就是进行知识发现和数据挖 掘，而且几乎所有已知的知识发现和数据挖掘方法已应用到了生物信息学的研究当中， 取得了丰硕的成果 9 】。 绪论 在进行数据挖掘时首先要确定挖掘的任务和目标是什么，如概念描述、分类、聚 类、关联规则发现或序列模式发现等，然后决定要使用的算法。同样的任务可以用不同 的算法来实现。选择实现算法要考虑两个因素，一是数据的特点，二是实际的要求，有 的希望获取描述性的、容易理解的知识，而有的则是获取准确度尽可能高的预测型知 识。数据挖掘的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳 的。 基于数据的机器学习方法是数据挖掘技术中的重要方面，研究从观测数据出发寻找 规律，利用这些规律对未来数据或无法观测的数据进行预测。包括聚类分析、模式识 别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。传统统计 学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在 实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可 能不尽人意。v a p n i k 等人从六、七十年代开始致力于统计学习理论( s t a t i s t i c a ll e a m i n g t h e o r y ，s l a 3 的研究l ，随着其理论的不断发展和成熟，也由于神经网络等学习方法在 理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视f l o ”j 。与传统统计学 相比，统计学习理论是一种专门研究小样本情况下机器学习规律的理论，它从理论上系 统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及 如何利用这些理论找到新的学习原则和方法等问题。 支持向量机( s u p p o r tv e c t o rm a c h i n c ，s v m ) 是九十年代中期在统计学习理论基础上 发展起来的一种新型通用的有监督的机器学习方法2 1 ”，成为数据挖掘中的一项新技 术。s v m 的主要思想是使结构风险极小化，其主要优点有：它是专门针对有限样本情 况的，其目标是得到现有信息下的最优解；算法归结为一个凸二次规划问题，从理论上 说，得到的将是全局最优解，解决了在神经网络方法中无法避免的局部极值问题；算法 将实际问题通过非线性变换转换到高维的特征空间，在高维空间中构造线性判别函数来 实现原空间中的非线性判别函数；s v m 巧妙地解决了维数问题，其算法复杂度与样本 维数无关；另外，s v m 具有简洁的数学形式和直观的几何解释，且人为设定的参数 少，便于理解和使用。由于s v m 既有严格的理论基础，又能较好地解决小样本、非线 性、高维数和局部极小点等实际问题，具有良好的推广能力，所以成为继神经网络研究 之后机器学习界新的研究热点。s v m 可以进行分类、回归、密度估计等1 1 8 捌，已成功 用于字符识别、文本自动分类、人脸识别、时间序列预测及生物信息学等许多方面。 s v m 从提出和被广泛重视到现在只有几年的时间，其中还有很多尚未解决或尚未 充分解决的问题，在应用方面的研究也是刚刚开始，还具有很大的潜力。因此s v m 是 大连理工人学博士学侮论文 一个十分值得大力研究的领域。本文将对s v m 从理论上进行分析，提出新的模型或算 法，并探讨s v m 在生物信息数据挖掘方面的应用。 本文也探讨其他数据挖掘的新方法。f d o d ( 下t r a c t i o no f d e g r e eo f d i s a g r e e m e n t ) ，是 一种新的信息离散性度量函数，基于信息论中熵的概念口。“j 。f d o d 方法对于任意给定 的两条或多条序列( 核酸或氨基酸序列) ，通过描述这些序列的子序列分布获得这些序 列的信息，最后计算信息离散熵得到序列之间的离散程度，因而可以用于序列的比较及 分类。这种方法简单快速，适于处理大规模的序列数据，己成功用于生物进化研究1 2 、 蛋白质结构类预坝l j 2 6 等方面。对蛋白质四级结构巾亚基数目的生物信息学研究是一个新 的课题 2 7 1 ，本文将研究s v m 和f d o d 两种方法在同源寡聚蛋白质分类中的应用。序列 的比较和分析是生物信息学中最基本也是最重要的研究内容| 4 ”，然而问题比较复杂， 尚有许多问题没有解决。本文将探讨f d o d 方法、生物序列的图形表示及其数值刻划 方法在生物序列的比较和分析中的应用。 1 2 数据挖掘与生物信息学 1 2 1 数据挖掘的概念、任务和方法 f 1 1 数据挖掘的概念 知识发现与数据挖掘是人工智能、机器学习与数据库技术相结合的产物。知识发现 被认为是从数据库中发现知识的全部过程，可粗略地分为三个阶段，即数据准备、数据 挖掘以及结果的解释评估口，3 l 。数据准备包括目标数据选取、数据清理、数据转换等方 面，为数据挖掘做准备，其中目标数据选取是指选择一个数据集或在多数据集的子集 上聚焦，数据清理是指去除噪声或无关数据，去除空白数据域，考虑时间顺序和数据的 变化等，数据转换是指找到数据的特征进行编码，减少有效变量的数目：数据挖掘是知 识发现过程的一个特定的、关键的步骤，首先是要决定数据挖掘的目的，然后选择某一 个特定的数据挖掘算法，抽取出潜在的、不显为人知的有用信息、模式和趋势。结果的 解释评估是要解释发现的模式，去掉多余的不切题意的模式，转换某个有用的模式为知 识，将这些知识放到实际系统中，查看这些知识的作用，或者证明这些知识，用预先可 信的知识检查和解决知识中可能的矛盾。知识发现过程是多个步骤相互连接起来，反复 进行人规交互的过程，如图1 1 所示。 图1 1 数据挖掘视为知识发现过程的一个步骤 ( 2 ) 数据挖掘的任务 数据挖掘作为知识发现的一个核心步骤，其主要任务有两大类，一类是描述，另一 类是预测j 。描述性挖掘任务刻划数据的一般特性，而预测性挖掘任务在当前数据集 上进行推断和预测。具体地说数据挖掘的任务有概念描述、关联分析、分类、聚类、孤 立点分析、演变分析等。 概念描述包括数据特征化和区分，数据特征化是目标类数据的般特性的汇总，数 据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性相比较。 关联分析的目的是发现关联规则，展示数据之间的相互依赖关系。 分类的目的是提出个分类函数把数据集中的分类项映射到某一个类剐。 聚类是根据数据的不同特征，将其划分为不同的数据类，目的是使得属于同一类别 个体之间的距离尽可能的小，而不同类别个体之间的距离尽可能的大。 孤立点( o u t l i e r ) 是一些不符合数据般模型的数据对象，可能是由于度量或执行错 误所导致的，也可能是固有的数据变异性的结果，孤立点本身可能是非常重要的，对孤 立点的探测和分析是一个有趣的数据挖掘任务。 演变分析描述行为随时间变化的对象的规律和趋势，并对其建模，主要包括时间序 列数据分析、序列或周期模式匹配和基于类似性的数据分析。 ( 3 ) 数据挖掘的方法 数据挖掘的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳 的。这些方法可粗略地分为机器学习、统计分析、神经网络、数据库及可视化等方法。 机器学习是通过建立适当的模型，由机器自动处理数据，使信息提取过程尽可能的 实现自动化。常用的机器学习方法有决策树、规则归纳、范例推理、贝叶斯信念网络、 大连理工大学博十学位论文 m a r k o v 模型方法、科学发现、遗传算法以及支持向量机方法等。 统计方法是利用统计学原理对数据库中的数据进行分析，常见的方法有回归分析 ( 如多元回归、自回归) 、判别分析( 如贝叶斯判别、费歇尔判别、非参数判别等) 、 聚类分析( 如系统聚类、动态聚类等) 、探索性分析( 如主成分分析法、相关分析法 等) 、模糊集以及粗糙集等。 神经网络方法源于对大脑的信息处理和学习过程的模拟，主要的模型和方法有前向 神经网络、径向基函数神经网络、反馈神经网络、随机神经网络以及自组织特征映射神 经网络等。 数据库方法主要有联机分析处理( 0 l a p ) 方法和面向属性的归纳方法等。 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚。目前常 用的方法有几何法、彩色法、多媒体法和光学法。例如把数据库中多维的数据变成多种 图形，这对于揭示数据中的状况，内在本质以及规律性起到很强的作用。 1 2 2 生物信息学的研究内容 现代分子生物学的发展，特别是人类基因组计划的实施，蛋白质和核酸的测序数据 以指数方式增加，生物学家面对的数据不再是实验记录本上或文献上的几行简单数字， 而是公共数据库中数以千兆计的记录。在揭示这些巨量数据所蕴涵的信息时，产生了生 物信息学。生物信息学是伴随基因组研究而产生的，因此它的研究内容就紧随着基因组 研究而发展。 生物信息学自诞生以来，大致经历了三个阶段 3 ，5 】。首先是基因年代的生物信息 学，主要是生物信息的收集、存储、管理与提供，数据库的查询与搜索、序列信息的提 取与分析：然后是基因组年代的生物信息学，主要是基因的查寻和同源性分析；随着基 因组和其他测序项目的不断进展，现在开始进入后基因组时代，主要是数据的挖掘、表 达、多样性分析、相互交叉数据分布的总结与分析。研究的内容开始进一步到基因和基 因组的功能分析，即转向功能基因组学( f u n c t i o n a lg e n o m i c s ) 研究。 生物信息学在基因组学研究中的重点是基因组序列，在功能基因组中研究中的重点 则是序列的生物学意义。其主要内容有：( 1 ) 进一步识别基因，识别基因转录调控信 息，分析遗传语言；( 2 ) 进行基因组功能注释，注释所有基因和基因产物的功能，认 识基因与疾病的关系；( 3 ) 研究基因的表达调控机制，研究基因在生物体代谢途径中 的地位，分析基因、基因产物之间的相互作用关系；( 4 ) 比较基因组学研究，在基因 组水平对各个生物进行对照比较，揭示生命的起源和进化，发现蛋白质功能。 1 2 3 生物信息数据库简介 生物信息数据库种类繁多，一般可以分为一级数据库和二级数据库口川。一级数据 库的数据都直接来源于实验获得的原始数据，只经过简单的归类整理和注释：二级数据 库是在一级数据库、实验数据和理论分析的基础上针对特定目标衍生而来，是对生物学 知识和信息的进一步分析、整理和归纳。 一级数据库主要分为基因组数据库、核酸和蛋白质一级结构序列数据库以及生物大 分子( 主要是蛋白质) 三维空间结构数据库。基因组数据库来自基因组作图，序列数据 库来自序列测定，结构数据库来自x 射线衍射和核磁共振等结构测定。国际上著名的 基因组数据库有人类基因组数据库g d b 、线虫基因组数据a c e d b 等；核酸数据库有 g e n b a n k 数据库、e m b l 核酸库和d d b j 库等；蛋白质序列数据库有s w i s s p r o t 、 p 1 r 等；蛋白质结构库有p d b 等。 二级生物学数据库非常多，它们因针对不同的研究内容和需要而各具特色，如基因 调控转录因子库t r a n s f a c 、真核生物启动子数据库e p d 、克隆载体数据库v e c t o r 、密码 子使用表达数据库c u t g 、蛋白质功能位点数据库p r o s i t e 、同源蛋自家族数据库 p f a r n 、同源蛋自质结构域数据库b l o c k s 、免疫球蛋白数据库k a b a t 、蛋白质二级结构构 象参数数据库d s s p 、已知空间结构的蛋白质家族数据库f s s p 等等。 1 2 4 生物信息数据挖掘的若干领域 可以说整个生物信息学研究主要是进行数据挖掘，是数据挖掘技术应用到现实世界 的最佳场所，而且几乎所有已知的数据挖掘技术都已应用到了生物信息学的研究当中， 取得了丰硕的成果。这里特别指出生物信息学中数据挖掘的几个具体领域【4 “。 ( 1 ) 生物序列的比较和相似性分析 序列比较是生物信息学中最基本也是最重要的操作，通过序y u l p , 较可以发现生物序 列中的功能、结构和进化的信息。一般的，序列决定结构，结构决定功能。通过比较生 物序列，可以发现它们的相似性。研究序列相似性的目的之是，通过相似的序列得到 相似的结构或相似的功能。当然，也存在着这样的情况，即两条序列几乎没有相似之 处，但分子却折叠成相同的空间形状，并具有相同的功能。研究序列相似性的另个目 的是通过序列的相似性，判别序列之间的同源性，推测序列之间的进化关系。 序列比较的基本操作是序列比对( a l l i g n m e n t ) 4 j j 。两条序列之间的比对是这两条 序列中各个字符的对比排列。最优比对揭示两条序列的最大相似程度，指出序列之问的 根本差异。打分矩阵是序列比较的基础，选择不同的打分矩阵将得到不同的比较结果。 大连理t 大学博士学位论文 针对核酸序列的打分矩阵有等价矩阵、b l a s t 矩阵、转换一颠换矩阵等；针对蛋白质序 列的打分矩阵有等价矩阵、遗传密码矩阵、疏水矩阵、p a m 矩阵、b l o s u m 矩阵等。 序列比对问题变成在矩阵里寻找最佳比对路径，目前最有效的方法是n e e d l e m a n - w u n s c h 动态规划算法、s m i t h w a t e n n a n 算法和s i m 算法等。 与序列两两比对不一样，序列多重比对( m u l t i p l ea l i g n m e n t ) 的目标是发现多条序 列的共性。某些在生物学上有重要意义的相似性只能通过将多个序列对比排列起来才能 识别。在多重序列近似比对算法方面，有动态规划算法、c a r r i l l o - l i p m a n 的优化计算方 法、按照星形结构或者树形结构组合两两序列比对的渐进方法、遗传算法、模拟退火算 法和隐马尔柯夫模型方法等。进行全局比对的多重序列比对程序有c l u s t a l w 、m a p 、 m s a 、p i l e u p 等。可进行局部比对的程序有p 1 m a 、b l o c km a k e r 、m e m e 、 心a w 、s a m 等。 由于序列比对有一定的局限性，很多人也寻求用其他方法来比较d n a 序列，比如 压缩矩阵的不变量方法，以及利用d n a 序列的图形表示及其数值刻划来比较d n a 序 列，本文在第五章和第六章中将有具体的描述。 ( 2 ) 基因组序列信息分析 基因组不仅是基因的简单排列，更重要的是它有其特有的组织结构和信息结构，这 种结构是长期演化的结果，也是基因发挥其功能所必需的。利用e s t ( e x p r s s e ds e q u e n c e t a g ) 数据发现新基因、分析和预测各种功能位点，研究基因调控网络成为近几年重要的 研究方向。 基因识别方法可以分成两大类，即从头算方法( 或基于统计的方法) 和基于同源序 列比较的方法。从头算方法根据蛋白质编码基因的一般性质和特征进行识别，通过统计 值区分外显子、内含子及基因间区域。基于同源的方法利用数据库中现有的与基因有关 的信息( 如e s t 序列、蛋白质序列) ，通过同源比较，帮助发现新基因。对于新的 d n a 序列，搜索与已知蛋白质、e s t 相似的区域，发现编码区域。最理想的方法是综 合两大类方法的优点，开发混合算法。 在d n a 序列中，除了基因之外，还包含许多其它信息，这些信息大部分与核酸的 结构特征相关联，通常决定了d n a 与蛋白质或者d n a 与r n a 的相互作用。存放这些 信息的d n a 片段称为功能位点，如基因的启动子( p r o m o t e r ) 、基因终止序列 ( t e r m i n a t o rs e q u e n c e ) 、剪切位点( s p l i c es i t e ) 等，这些功能位点与基因的表达调控 密切相关。对这些功能位点进行分析或预测也是d n a 序列分析的重要内容。 传统的分子生物学习惯于分析单个基因。但是生命现象并不是单基因的简单堆积， 而是高度有组织的多基因网络。生命组织是高度有序的，而这种有序性来自于基因之间 的协同作用，来自于复杂的基因调控系统。科学家正在用系统的思想和数学的方法对基 因调控系统进行分析研究，他们认为在基因层次上，生物的调控作用符合控制论原理， 并建立起一些调控系统的数学模型，如布尔网络模型、线性关系网络模型、微分方程模 型、互信息相关网络模型等，在此基础研究基因调控网络的动力学性质。 ( 3 ) 蛋白质结构与功能预测 蛋白质的结构决定蛋白质的生物功能，因此在研究蛋白质时需要了解蛋白质的空间 结构。虽然蛋白质结构测定方法有所改进，但仍不能满足实际的需要。核酸酶变性及重 折叠实验，为从蛋白质的氨基酸序列预测蛋白质的三维空间结构提供了实验基础。直接 从蛋自质序列预测蛋白质结构对研究蛋白质结构与功能关系十分有用，这也将促进蛋白 质工程和蛋白质设计的发展。 - 蛋白质结构预测主要有二级结构预测和空间结构预测。理论和实验表明，不同的 氨基酸残基在不同的局域环境下具有形成特定二级结构的倾向性，因此在一定程度上二 级结构的预测可以归结为模式识别问题。二级结构预钡f 是联系蛋白质一级结构到空间结 构的纽带。预测的目标就是判断某一个片段中心的残基是a 螺旋，还是b 折叠，或是其 它。在二级结构预测方面主要有立体化学方法、图论方法、统计方法、最邻近决策方 法、基于规则的专家系统方法、分子动力学方法、人工神经网络方法以及支持向量机方 法。理论上，蛋白质一级结构决定了蛋白质折叠后的空间结构，可以从氨基酸序列计 算出自然折叠的蛋白质结构。但是由于蛋白质多肽链可能的构象是个天文数字，现有的 计算能力不可能搜索整个构象空间，需采用一定的启发式方法寻找自由能最优或接近于 最优的构象。在空间结构预测方面，主要有从头预测方法，折叠识别方法以及目前来说 比较成功的同源模建方法。 从蛋白质序列出发可以预测与蛋白质功能相关的特征如亚细胞定位、信号肽剪切位 点、信号肽剪切位点的重新设计( 用于优化剪切效率) ，信号锚( i i 型膜蛋白的n 段部 分) 、与糖类相结合的糖基化位点、与转录后修饰有关的磷酸化和其他修饰作用、蛋白 质的不同结合位点和激活位点等。 ( 4 ) 基因表达数据的分析与处理 基因表达数据分析是目前生物信息学研究的热点和重点。目前对基因表达数据的处 理主要是进行聚类分析，将表达规律相似的基因聚为一类，在此基础上寻找相关基因， 分析基因的功能。所用方法有相关分析方法、层次聚类方法、自组