（概率论与数理统计专业论文）生物信息学有关的数据结构与智能计算问题.pdf

摘要随着生物技术的发展，积累了越来越多的生物数据，对生物数据的存储分析形成了新的学科；生物信息学。生物信息学的发展是多种学科交叉的结果，但是另外一方面对生物数据的分析，新算法的开发对数学和计算机科学的发展也起到了一定的推动作用。本文就是对这方面的初步探讨。本文分三个部分，第一部分，从生物信息学中的生物序列的比对出发，将序列的突变推广到信息科学和计算科学中的广义差错，并且给出其应用：广义纠错码和容错复杂度。第二部分，使用模糊神经网络算法分析基因识别的因素问题，第三部分，给出一种新的聚类算法e m r 算法，并将其应用于蛋白质的聚类中在数据处理问题中，差错的类型有多种，除了符号的变更外还有数据的丢失与插入等情况发生，我们统称这种差错为广义差错或突变误差在计算机，信息论与生物信息学领域中，对这种广义差错都有研究，并分别对这种差错给以度量的定义，如在计算机与信息论领域称这种广义差错的度量为l e v e m h t e i n 距离，编辑距离fe d i t ed i s t a n c e ) 或e v o l u t i o n a r y 距离等，这些距离有的是等价的，也有是不等价的在生物信息学中，为寻找序列的突变误差的发生的状况有一系列的比对( a h g n m e n t ) 计算方法与研究，由此可产生a l i g n m e n t 距离与a 1 i g n m e n t 空间，a l i g n m e n t 距离实际上就是e v o l u t i o n a r y 距离本文首先概述这几种距离的定义与相互关系，为研究广义差错的数据结构，我们引进它们的代数结构理论，并由此对a l i g n m e n t 距离满足三角形不等式给出它的严格证明，本文还讨论了最小罚分比对与最大得分比对的关系问题与广义纠错码的构造问题，给出了最优比对的不唯性的例子，最小罚分比对与最大得分比对的不等价性与等价条件在码长较小时利用a l i g n m e n t 算法可得到一系列最优的广义纠错码复杂度理论是计算机科学与密码学的重要基础，所谓容错复杂度就是允许数据具有差错时的复杂度，近年来在密码学研究中受到重视本文对一般广义差错( 符号改变、插入与删除) ，给出了它们一般的非线性容错复杂度的定义、计算与应用。在真核生物外显子与内含子的识别中，由d n a 序列可以产生多种结构的特征参数，如氨基酸的频率分布，z 一坐标等，我们称这些特征参数为外显子与内含子的识摘要别因素本文的目的就是分析这些因素，及它们的组合在基因识别中的作用为此目的，我们采用了人工神经网络理论中的模糊感知器模型，建立相应的特征参数集与神经网络训练与识别模型，并以b u r s e t g 1 1 i g o 训练集为训练数据，以h m r ，h 1 7 8 ，果蝇和拟南芥等数据集构成混合检验集，选择d n a 序列的氨基酸的频率分布，z 一坐标等为该序列的特征参数，并对这些参数及它们的不同组合作学习训练与识别的因索分析，分别在单因素，低因素( 因素数为2 ，3 ，4 ，5 ) ，高因素( 因素数大于5 ) 时，得到这些因素在不同组合下识别的精度指标，由此可以看到不同因素组合在基因识别中的作用聚类分析是数据发掘理论与统计学中的一个重要领域常见的聚类分析类型很多，如系统聚类，中心聚类等，这些数据的聚类一般是以它们的距离为基础，把距离较近的数据归结为同一个类，本文提出的分布族的聚类分析问题，是指所讨论的数据是由一大批数据序列组成，由每个序列可确定它的分布结构( 如频率分布，二重数据的联合频率分布等) ，由此就可以产生分布族，为对分布族进行聚类分析，在本文中我们以k u l l b a c b l e i b l e r 熵为不同分布的差异性度量，给出了相应的优化聚类算法，这种算法与e m 算法或k m e a n 算法思路相似，但又增加个新的递归运算步骤，所以我们称之为e m r ( e x p e c t a t i o n - m “i m i z a t i o n _ r e c u r s i v e ) 算法，或k r - m e a i l s ( k m e a n sr e c u r s i v e ) 算法，我们证明了该算法的最优性与收敛定理关键词：生物信息学，广义差错与突变误差，a l l g n m e n t 空间，容错复杂度，基因识别，e m r 聚类算法a b s t r a c ts e q u e n c e sw i t hg e n e r a l i z e de r r o r sw h i c ha r ec a l l e dm u t a t i o i l si nb i o i n f o r m a t i c sa n dg e n e r a l i z e de r r o r c o r r e c t i n gc o d e s 盯e8 t u d i e di nt h i sp a p e r i nt h ea r e a so fb i o i 】1 f o r m a t i c s ，c o m p u t e r8 c i e n c ea n di n f o r m a t i o nt h e o r y 7s e q u e n c e 8 丽t hg e n e r a l i z e de r r o r s a r ed i 8 c u 8 s e dr e s p e c t i v e l yf o rd i 氐色r e n ta i m s f i r s t l y ) w eg i v et h ed e 矗n i t i o n so f 以i g m e n td i s t a n c ea n dl e v e n s h t e i nd i s t a n c eb ye x p a n s i o ns c q u e n c c sa n dd i s c u s st h e i rp r o p e r t i e sa n dr e l a t i o n s t h et h em o d u l a rs t r u c t u r et h e o r yi si n t r o d u c e df o r8 t r i c t l yd e s c r i b et h ee x p a n s i o ns e q u e n c e s ，e8 h o wt h a tt h ee x p a n s i o nm o d u l a rs t r u c t u r e so fs e q u e n c e sf o r mab o o i k a na 培e b r a a sa p p l i c a t i o l l so ft h em o d u l a rs t r u c t u r et h e o r y jw eg i 、，ean e wa n dm o r es t r i c tp r o o fo ft r i a n g l ei n e q u a l i t yf o ra l i g n m e n td i s t a _ i l c e a tl a s t ，t h ed e 6 n i t i o na n dc o n s t r u c t i o no fg e n e r a l i z e de r r o r c o r r e c t i n gc o d e s 盯es t u d i e d ，a n ds o m eo p 恤n a lc o d e s 矾t hs m a l l l e n g t h 缸el i s t e d c o m p l e ) c i t yt h e o r yi so n eo f i m p o r t a n tb a s e si nc o m p u t e rs c i e n c ea n dc r y p t o g r a p h mt h e8 0 - c a l l e df a m t t o l e r a n c ec o m p k ) ( i t yi 8t h ec o m p l e x i t yw h e nd a t ae r r o r sa r et 0 1 e r a b l e w ep r e s e n tt h eg e n e r a ld e 矗n i t i o no ff a u l t t o l e r a n c ec o m p l e 五t yw i t h。t l l ea i do ft h em u t a t i o na n da u g m e n to fb i o l o g ys e q u e n c e s f r t h e r m o r e ，am e t h o dt oc o m p u t en o n - 1 i n e a rf a u l t t o l e r a n c ec o m p l e x i t yi sa 1 8 0g i v e ni nt h i sp 印e r i nr e c o g n i t i o no fe u l ( a t y o t i cg e n o m e s ，m a n yc h a r a c t e r i s t i cp a r a m e t e r sc a nb eo b t a i n e df r o md n as e q u e n c e ，w h i c hw ec a ur e c o g n i t i o nf a c t o r s ，8 u c ha sc o n t e n t so fa i n i n oa c i d se n c o d e db yt h ed n as e q u e n c ea n dz _ c u r v ee c t t h ep u r p o s eo ft h i 8p a p e ri st oa n a l y 8 i st h e s ef h c t o r 8a n dt h e i rc o m b i n a t i o n si ng e n er e c o g i l i t i o n w e1 1 s ef u z z yp e r c e p t r o nm e t h o do fn e u r 龃n e t w o r ka n dc o n s t r u c tt h et r a i n i n ga n dr e c o g n 拍0 nm o d e 】o ft h e s ef a c t o r s w e1 1 s eb u r s e t g u i g od a t a s e ta st r a j n i n g8 e ta n dc o n s t r u c tat e s t i n gs e tc o 璐i s t e do fh m r ，h 1 7 8 ，d r o s o p h i l am e l a n o g a s t e ra n da r a b i d i p s i st h a l i a n ad a t a s e t s e l e c t i n gd i 船r e n tf a c t o r 8a n dt h e i r sc o m b i n a t i o n 8i ng e n er e c o g l l i t i o ng e n e r a t ed i f f e r e n tr e c o g n i t i o na c c u r a c i e s t h ec o m b i n a t i o n so fs i n g l e - f a c t o r ( t h e b e ro ff a c t o ri s1 ) ，l o w f a c o t o r ( t h en u m b e ro ff a c t o r si s2 ，3 ，4a b s 打a c to r5 ) a n dh i 曲一f a c t o r ( t h en u m b e ro ff a c t o r s 5 ) a r ec o l l s i d e r e d8 e p a r a t e l yi no u rp a p e r a 8ar e s u l t ，w eg e tt h ef a c t o r sa n dt h ec o m b i n a t i o n sw h i c ha r ei m p o r t 蚰ti ng e n er e c o g n i t i o n t h ef u z z yp e r c e p t r o nm e t h o di sp r o v e dt ob e1 1 s e f u l i ng e n er e c o g n i t i o n i f8 e l e c t i n gf i v ep r o p e rf a c t o r s ，t h ea c c u r a c yi sc l o s et ot h a 止o b t a i n e db ys o f t w a r ew h i c ha r ec u r r e n t l y1 1 s e d c l u 8 t e ra n a b s i si 8a ni m p o r t a n t 矗e l d0 fd a t am i n i n ga n ds t a t i 8 t i c s t h e r ea r em 舡1 ym e t h o d so fc l u 8 t e ra n a l y s i 8 ，8 u c ha sh i e r a c h i c a lc l u 8 t e ra n a l y s i 8 ，p a r t i t i o n a 王c l u s t e ra n a l y s i 8e t c i nt h i sp a p e r ，w ep r e s e n tac l u s t e r i n ga l g o r i t h mb a s e do nd i s t r i b u t i o nf 眦i l yi no r d e rt om a k ec l u s t e r i n go fd i 8 t r i b u t i o nf 锄i l y ) w eu s ek u l l b a c k l e i b l e re n t r o p ya st h em e a s l l r eo ft h ed i f f e r e n td i s t r i b u t i o n sa n dp r e s e n tt h ec o h 唧o n 也n go p 七i m a 卫a l g o r i 乞h m t h ea l g i t h mi 88 i m i l 盯t ot h ee m “g o r i t h ma n dk m e a n sa l g o r i t h m t h ed i 船r e n c ei st h a tw ea d dan e wr e c l l r 8 i v e8 t e p ，s ow en a m ei te m r ( e x p e c t a t i o n m a 函m i z a t i o n r e c u r 8 i v e ) o rk r - m e a l l 8 ( k m e a n sr e c u r s i v e ) 柏g o r i t h m w ep r o v et h eo p t i i i l i z a t i o na n dc o n v e r g e n c et h e o r e mo ft h i 8a l g o r i t h m k e yw o r d s ：b i o i n f o m a t i c s ，g e n e r a h z e de r r o r sa n dm u t a t i o ne r r o r s ，a l i g n m e n ts p a c e ，f a u l t t o l e r a n c ec o m p l e x i t y ，g e n er e c o g n i t i o n ，e m rc l u t e r i n ga l g o r i 七h m y9 6 8 9 2 7南开大学学位论文版权使用授权书本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。学位论文作者签名：孓熏) “。厂年f 乙月7 日经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。指导教师签名：学位论文作者签名：解密时间：年月日各密级的最长保密年限及书写格式规定如下南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：丑套7 。猝i2 ，月f 日绪论上世纪初，孟德尔遗传定律的重新发现，掀起了对遗传信息内容和本质的科学探索，推动了过去一百年来生物学的发展。生命科学在2 0 世纪的发展过程根据时间自然地划分为4 个阶段【1 】第一阶段：在最初的2 5 年中，科学家建立了遗传的细胞基础，染色体第二阶段：随后的2 5 年中，1 9 5 3 年，d n a 双螺旋结构的提出，定义了遗传的分子基础。第三阶段：第三个2 5 年中，揭开了遗传的信息基础，伴随着细胞识别基因信息的生物学机理，与d n a 重组克隆和测序技术的发明，通过运用这些技术，科学家可以探索基因中的信息最后2 5 年，从第个基因到全基因组，基因组学研究领域蓬勃兴起，这期间，最重大的事件是称为生命科学“登月”计划的人类基因组计划的全面实施2 0 0 0 年，人类基因组草图的公布，标志着人类进入后基因组时代大量的生物序列被测定只是完成了中的一步，对这些序列的解读和分析变得越来越重要。在此之前，大量的数学家和物理学家都投身其中，试图揭开序列中的奥秘，并且取得了很大的成果，生物信息学因此诞生生物信息学作为多学科的交叉，在过去的十年中，是生命科学从过去的经验学科有了定量化研究的基础，大大促进了生物学家对生命现象的理解。而同时，在研究工作中提出的新问题同样也影响到了数学和计算机领域的发展，典型事件是d n a 计算机的出现，改观人们以往对计算机的观点，成为计算机领域的研究热点，并且被称为是未来计算机的发展方向在生物信息学中，序列比对是序列分析中的重要工具，因为序列比对而建立的生物序列突变的研究与信息论，计算机科学中对广义差错的研究有共通之处。本文的主要结果就是从生物序列的突变研究得到广义纠错码的定义和构造本文同时给出了生物信息学中的两个智能算法：模糊神经网络算法和k m r 聚类算法这两个算法都具有可推广性，而不仅限于生物信息学中o 1 生物信息学随着生物技术的发展，尤其是d n a 测序技术，大量的生物序列被测定，包括核苷酸序列，蛋白质序列，蛋白质空间结构信息，这些数据的存贮量正在以指数增长绪论2自2 0 世纪8 0 年代晚期以来，序列数据大约每1 6 个月增长1 倍，而随着人类基因组草图的完成，以及d n a 微阵列等高效实验技术的出现，生物信息数据以更快的速度增长，每6 8 个月增长1 倍研究的重点已经从积累数据到如何解释这些数据在数据量呈几何级数增长的情况下，生物信息学的基础研究将致力于解决生命科学中与系统和集成相关的问题生物信息学( b i o i h f o r m a t i c s ) 是一门新兴的交叉学科，是伴随基因组研究而产生的，因此它的研究内容就紧随着基因组研究而发展广义地说，生物信息学从事对基因组研究相关生物信息的获取、加工、储存、分配、分析和解释这一定义包括了两层含义，一是对海量数据的收集、整理与服务，也就是管好这些数据；另一个是从中发现新的规律，也就是用好这些数据。o 1 1 生物数据库表1 1 生物数据库一级数据库g e n b a l l k核酸序列数据库h t t p ：w w wn c b i n l n l n i h 9 0 v w e b g e n b a n k s i w s s _ p r o t蛋白质序列数据库h t t p ：w w e ( p 鹪h c h 8 p r o t s p r o t - t o p h t m lp d b蛋白质结构数据库h t t p ：w w w r c s bo r g p d b 二级数据库p r o s i t e蛋白质功能位点数据库h t t p ：e ) 币矸h c u g e c h s p r o t p r o s i t e h t m ls c o p蛋白质结构数据库h t t p ：s c o p m r c - l m bc a ma cu k s c o p 出吨a s c o p 1 h t m lc a t h蛋白质结构分类数据库h t t p ：c a t h w w wb i o c h e m u c l a cu k 1 a t e 8 t p f a m蛋白质家族数据库h t t p ：p f a m w 璐t 1 e d u p r i n t s蛋白质印迹数据库h t t p ：u m b e r s b s m a n a c u k d b b r a w s e r p m n t s p r o d o m蛋白质域数据库h t t p ：p r o t e i n t o u l o u s ei n r a f r p r o d o m c i l r r e n t h t m l h o m ep h p现在国际上大量存在的生物数据库按照数据的来源大致可以分为以下两类：一级数据库，这类数据库中包含了原始的序列和结构数据，是生物信息学中的基本数据资源，比如基因组数据库，核酸，蛋白质的序列数据库，蛋白质的三维结构数据库，这些数据大多来源于生物实验技术的测定，基因组数据库来源于基因组作图，序列数据库来源于序列的测定，蛋白质的三维结构数据来源于核磁共振或者x 晶体衍射二级数据库，这类数据库是研究人员根据不同的需要，将一级数据库中的信息加以绪论3整理，分析，解释或者提取而得到的，也称为专门数据库。总的来说，一级数据库的数据规模大，通常需要专门的高性能的计算机，大容量的存储空间和专门的数据库管理软件，一级数据库的更新较快而二级数据库规模相对较小，许多的二级数据库基于w e b 开发，具有友好的图形界面和方便的访问方式，二级数据库的更新也相对较慢。常见的数据库及其访问方式如表1 1 所示法国生物信息研究中心i n f o b i o g e n 维护的生物信息数据库目录d b c a t ( 2 】) 搜集了主要5 1 1 个数据库( 至2 0 0 5 6 9 ) 的名称、内容、数据格式、联系地址、网址等详细信息，使用户对目前生物信息数据库有一个详尽的了解分类数据库数量d n a8 7r n a2 9p r o t e i n9 4g e o m i c5 8m a p p i n g2 9p r o t 血s t r u c t u r e1 8l i t e r 砒u r e4 3m i 8 c e u a n e o u s1 5 3数据库中的数据很多来自于全世界科学家的贡献，而且各个数据库建立的时间和目的不尽相同，现在数据库格式的标准有很多，这不利于数据的整合，新成立的美国生物技术工业组织( b 1 0 ) ( 见h t t p ：w w w b i o - o r g ) ，正在计划制定存储和检索有关生命分子信息的“世界标准”o 1 2 生物信息学的主要研究内容生物信息学的研究涉及多个方面，首先包括对数据的存储和管理，生物数据库就是这方面的努力，也是进行数据分析的基础对数据的分析主要围绕基因组分析，蛋白质结构分析和药物设计三个方面，下面简要介绍这三个方面中的一些主要工作1 基因组分析( 1 ) 序列的比对绪论4序列的比对作为生物信息学中的一个基本问题一直受到广泛的关注比对的目的是为了得到序列之间的差异度序列之间的差异度是了解序列关系并作进一步分析工作的基础。( 2 ) 基因识别计算机辅助基因识别，目的是通过从大量的基因数据中积累的规律，能够达到由计算机自动从核酸序列中识别基因数据基因识别的算法在原核生物上取的很好的效果，真核生物的基因结构远较原核生物复杂，所以对真核生物的基因识别始终是个难题。( 3 ) 非编码区分析和d n a 语言研究人类基因组中，编码为蛋白质的序列占所有基因组序列的3 5 ，其余的9 5 的序列过去称之为垃圾序列，但是随着研究的深入，对于这些非编码区序列的分析变得越来越重要，非编码区中包含了调节基因编码的信息简单地说，编码区只是告诉人们编码的序列是什么，但是什么时候编码，表达多少，在基因重合的情况下如何剪切，这些重要的控制信息往往具有特定的模式，但是大多数模式还并不为人们了解( 4 ) 分子进化和比较基因组学生物的进化过程一直是生物学家非常关心的问题在分子水平上，同一种基因序列在不同物种之间的差异性，是早期研究工作的重点随着越来越多的基因组测序的完成，在全基因组的水平上比较物种间的进化关系成为可能和必然2 蛋白质结构分析( 1 ) 蛋白质二级结构的预测蛋白质的二级结构是蛋白质在空间中的局部结构，因为蛋白质在空间中形成螺旋和片状平行的结构( 称为。一螺旋和p 一折叠) 等非常规则的局部结构，而空间结构是由这些规则的二级结构按一定的拓扑关系排列而成，所以从蛋白质的一级结构出发预测蛋白质的二级结构是蛋白质结构分析中的个重要问题，是从序列出发预测蛋白质空间结构的第一步( 2 ) 蛋白质空间结构的比对序列的差异度可以使用序列比对的方法，而蛋白质空间结构之间的差异度则使用空间结构的比对相对序列比对，空间结构的比对在维数要高，所以比对的复杂度要大得多。空间比对对于了解和预测蛋白质的结构有重要的作用53 药物涉及相关传统的药物设计开发周期长，大约是十年的时间，但是基于生物信息平台的药物设计，可大大缩短着一开发周期基于生物大分子结构的药物设计是生物信息学中的极为重要的研究领域。对蛋白质空间结构的研究，可以促使对蛋白质功能的了解，从而可以从分子水平上找到很多疾病的致病机理( 1 ) 基于受体结构的药物筛选药物的治疗作用是通过药物分子和作为受体的生物大分子之间的相互作用而产生疗效为了抑制某些酶或蛋白质的活性，在已知其三级结构的基础上，可以利用分子对接算法，在计算机上设计抑制剂分子，作为候选药物这种发现新药物的方法有强大的生命力，也有着巨大的经济效益( 2 ) 分子模拟与药物设计分子模拟在药物设计的很多环节起到重要的作用，分子模拟不仅可以确定生物大分子的空间结构，并且进一步应用于寻找先导化合物，优化先导化合物等方面o 2 序列比对序列比对是生物信息学中的基本问题( 3 ，4 】) ，是许多分析工作的基础。在核酸和蛋白质序列的分析中，常常遵循的模式，是从序列到结构再到功能，序列作为最上游的数据或者最底层的数据，发现其中的规律具有重要的作用。在序列数据的分析中，首先面对的问题是，如何描述序列间的关系，这就需要定义个距离，根据不同的需求，距离的定义形式也是多种多样的。进化分析中，常常使用序列的相似性作为序列间的距离，而在聚类分析中，可以采用序列的相似性，但是为了降低计算的复杂度，也可以采用本文中提出的两条序列中概率分布的互熵从进化论的观点看，遗传是主要的，而变异对序列来说只是一小部分，所以进化时间相近的序列，总是会有相似的序列，因此常常使用序列的相似程度来作为两个序列间的距离为了计算序列之间的相似程度，就需要使用比对算法按照序列比对的条数可以分为二重序列比对和多重序列比对二重比对的算法在早期的研究中受到广泛的关注，动态规划作为解决最优化问题的经典算法被最早地应用于序列比对问题上( 见 5 ，6 ”目前生物信息学中通用的比对程序为b l a s t ( 【7 ) 和f a s7 r a ( 【8 ) ，这两个绪论6程序都是基于动态规划算法。但是随着序列规模的不断增加，动态规划算法的时间复杂度和空间复杂度无法解决大规模序列的比对问题，更低复杂度的算法是比对问题的研究重点。s p a 算法是一个与序列长度呈线性复杂度的算法( 【9 ) ，在长序列的比对上由很大的优势多重比对作为一个n p 完全问题( 【1 0 】) ，直没有得到很好的解决，多重比对的规模一直受到限制，s m a ( 1 1 ) 算法是个基于s p a 算法和模结构的多重比对算法，在时间复杂度，比对序列的规模上都有着较大的提高o 3 广义差错广义差错的概念包括符号的变更，数据的插入与丢失( s u b s t i t u t i n g i 璐e r t i n g d e l e t i n g ) 等类型的差错，在我们日常生活中经常发生，因此在计算机科学、信息论与生物信息学中受到关注( 见 1 2 ，1 3 ，1 4 ) ，近期都有许多研究但他们的定义出发点与进展程度并不相同关于广义差错的最早研究首见于1 9 6 3 年，由l e v e n s h t e i n 给出f 1 3 1 ，他对二个序列所产生的广义差错进行多种度量定义，其中之一是把二序列的长度与它们最大公共子序列之差作为这二序列的距离，我们称之为l e v e 璐h t e i n 距离另一种定义是把一序列经过一系列经符号的变更、数据的插入与删除运算变成另一序列，在计算机科学领域称这种运算为数据的编辑运算，并把它们的最小运算次数称为最小编辑距离在计算机科学中，d n a 计算机是未来计算机发展的方向之一 1 5 ，是计算机科学和生命科学的结合点。但是在d n a 计算过程中，大量不可避免发生的差错可能导致整个系统的不稳定性。这些差错不同于传统通信理论中的替换差错，而且包含插入、删除差错，这使得开发一种新的差错控制系统成为必要对广义差错及其所产生的数据空间a l i g n m e n t 空间的研究就是这个方向的初步尝试在生物信息学领域，最小编辑距离又称为进化距离( e v o l u t i o n a r yd i s t a n c e ) ( 1 1 4 )或者比对距离1 9 7 4 年，p e t e rh s e l l e r 8 1 4 ，用序列扩张的方法对具有广义差错的二序列给出了它们的进化距离( e v o l u t i o n a r y 距离) ，并在一般的条件下证明了e v o l u t i o n a r y 距离满足度量空间的三个基本条件( 非负性、对称性与三角形不等式成立) ，由于不难证明l e v e n s h t e i n 距离与e v o l u t i o n a r y 距离的等价性 1 6 】，这样看来关于广义差错的度量问题似乎已完全得到解决但是我们发现，如果仔细阅读f 1 4 1 文绪论7关于e v o l u t i o n a r y 距离三角形不等式的证明，就可发现该文的证明并不严格由于广义差错序列结构的复杂性，对它们关系的描述并不简单，需要用一定的数学结构给以表达本文使用序列扩张的模结构理论( 见【1 2 ，17 ) ，给出了它们的几种不同的表达方式与等价关系，并给出了不同序列扩张结构的相互关系具有布尔代数的运算规则，由这些关系才能使 1 4 文定理l 得到严格的证明，并由此看到广义差错序列的数据结构的基本特性在下文中，为了避免混淆，我们统一称广义差错的距离为比对距离( a l i g n m e n td i s t a n c e ) 。广义差错的概念在生物信息学中被称为是序列的突变误差，在生物学中对突变误差的研究有以下特点( 【4 】) ：( 1 ) 在生物学中对突变误差的研究有十分广泛的应用，它与生物进化、演变、疾病分析与医学治疗都有密切关系，同时也是基因定位、搜索、拼接与预测研究的主要工具与手段因此可以毫不夸大地说，对生物序列突变误差的研究已是近代分子生物学与生物信息学中的核心与基本问题( 2 ) 在生物信息学中，称寻找序列突变位置的运算为序列的比对运算( a l i g n m e n t ) ，生物序列的比对运算的要点是寻找不同序列之间的最小罚分比对或最大得分比对，我们称不同序列之间的最小罚分比对的罚分值为序列之间的比对距离( a g n m e n t 距离) a l i g n m e n t 距离与e v o l u t i o n a r y 距离的定义实际上是等价的，因此它们与l e v e i l 8 h t e i n 距离等价在本文中我们将要说明，不同序列之间的最小罚分比对或最大得分比对并不等价( 3 ) 由于序列突变在生物学中的重要意义，因此对序列的比对问题有大量的研究，如求最小罚分解的快速比对的s m i t h _ w a t e r m a n 的动态规划算法( 见 6 文) ，利用统计判决的s p a 算法等( 见 9 文) ，他们的计算复杂度为d ( n ) 一0 ( n 2 ) 这样对长度很大的序列我们很快就可得到它们的最小罚分比对因此在本文中，我们把由不等长序列与它们的a i i g n m e n t 距离所构成的空间称为a l i g n m e n t 空间，并给以研究本文从生物序列的突变误差出发，给出了广义差错的严格数学描述，严格证明了a l i g n m e n t 空间为个度量空间，说明最优比对的不等价性，给出了最大得分比对和最小罚分比对的不等价性和等价条件。最后，我们讨论广义差错的两个应用：广义纠错码和容错复杂度绪论8传统的纠错码的设计只能纠正替换错误，自l e v e n s h t e i n 的f 13 1 文发表后，能够纠正替换插入删除错误的纠错码近期在编码与密码学中有较多的研究( 见 1 7 ，1 8 ，1 9 ，2 0 文) 由于a l i g n m e n t 空间构成度量空间，我们就可定义它的广义纠错码，利用序列比对的快速算法就可构造广义纠错码的译码算法，并在码长较小时，搜索构造广义纠错码所谓容错复杂度指允许数据具有差错时的复杂度，具有差错时的复杂度近年在密码学的研究中受到重视( 见【2 1 ，2 2 ，2 3 ，2 4 ，2 5 j ) 序列在允许差错的情况下，其复杂度有可能大大降低，密码学中乱数流的设计中，对m 一序列做差错变换可以提高序列的非线 生复杂度，从而增加破译的难度一些序列也可能因为具有较高的非线性复杂度，但是通过差错变换能够降低其复杂度而使其不具备原来所期望的密码强度在生物序列分析中，通过差错变换，一些生物序列的复杂度会大大降低，由此可以得到序列片断之间的递推关系。由此可见，广义差错是多种学科的结合点，如果能把生物信息学，信息科学，计算机科学中的研究目标，理论与思路方法联系起来，相互借鉴相互促进，对于这些学科的发展是很有意义的o 4 基因识别在核酸序列中正确识别基因的位置是基因识别的基本问题。根据识别对象的不同，基因识别的算法又分为原核生物和真核生物两类因为原核生物和真核生物序列结构的不同，在真核生物上的基因识别仍然是个困难的问题萝詹辩墨| 【_ l 蕊莓鹎擅域圆、啦嚷簿越霞分_ 啊蟹鬈饔：j ：= 1 譬爱圈图1 ：原核生物基因结构示意图绪论图2 ：真核生物基因结构示意图9如图l 和2 中所示，原核生物的基因结构相对简单，一个基因的编码序列是连续的，而在真核生物中，一个基因的编码序列并不连续，而是交替的外显子( e x o n )片断和内含子( i n t r o n ) 片断，其中外显子片断是编码序列，将一个完整基因结构中所有的外显子片断相连才能翻译出完整的蛋白质序列目前的基因识别算法可以分为两个类【2 6 】，第一类，基于序列的同源性，第二类基于序列的统计特性基于序列同源性的算法，因为具有同源性的序列往往具有相似的功能，所以将未知序列和已知基因结构的数据进行双重或者多重比对，和已知序列的基因结构对应的序列片断往往就是未知序列基因结构的序列片断基于统计特性的方法，主要是根据基因结构中编码序列片断和非编码片断具有不同的统计特性 2 7 】 2 8 】 2 9 基于统计特性的基因识别算法需要使用已知序列作为训练集训练参数参数根据不同的需要有很多选择，比如密码子的使用，氨基酸的含量，编码区的三周期性和功率谱等等现在很多识别算法使用的高阶马尔科夫模型( h i g h e r o r d e rm k o vc h a i nm o d e l ) 或者隐马尔科夫模型( h i d d e nm ”k o vc l l a i nm o d e l ) ，比如g e n e i d 3 0 1绪论1 0使用6 阶马尔科夫模型，g e n e s c a n 【3 1 使用隐马尔科夫模型马尔科夫模型需要训练的参数比较多，一个6 阶马尔科夫模型需要训练的参数多达4 6 “一1 个而使用神经网络算法的识别算法，选择合理的参数十分重要z c u r v e 系列f 3 2 ，3 3 ，3 4 ，3 5 基于z 曲线理论，虽然只选取6 9 个参数，但是预测精度仍然达到了很高的水平，在某些指标上甚至超过现有的基因识别软件。在本文中，我们试图分析参数对预测水平所起到不同的作用，找到最有用的参数多余的参数虽然能够提供更多的信息，但是有可能干扰最后的预测水平根据奥卡姆剃刀( o c k h a m sr a z o r ) 原则，应该尽量选择简单的模型和较少的参数o 5 生物序列的聚类聚类分析是数据发掘理论与统计学中的一个重要领域3 6 ，3 7 ，3 8 1 常见的聚类分析类型很多，如系统聚类，中心聚类等，这些数据的聚类一般是以它们的距离为基础，把距离较近的数据归结为同一个类，本文提出的分布族的聚类分析问题，是指所讨论的数据是由一大批数据序列组成，由每个序列可确定它的分布结构( 如频率分布，二重数据的联合频率分布等) ，由此就可以产生一分布族，为对分布族进行聚类分析，在本文中我们以k u u b a d l e i b l e r 熵为不同分布的差异性度量，给出了相应的优化聚类算法，这种算法与e m 算法或k m e a n 算法思路相似，但又增加个新的递归运算步骤，所以我们称之为e m r ( e x p e c t a t i o n - m a 妇m i z a t i o n - r e c u r s i v e ) 算法，或k r - m e a m ( k m e a n 8 鼬c u 瑙i v e ) 算法，我们证明了改算法的最优性与收敛定理生物序列数据库，如g e n b a n l c ，p d b ，s w i s s _ p r o t 都是典型海量数据( 如2 0 0 5 年的g e n b a n k 数据已经超过1 0 0 gb p ) ，其中存在大量分布结构的分析问题，本文以s w i 8 s p r o t4 4 0 版( 其中含有1 5 3 8 7 l 条蛋白质序列与5 6 6 0 8 1 5 9 个氨基酸单位)为例，做蛋白质一级结构成分比例的聚类分析，由此实现我们的聚类分析算法与蛋白质成分结构的分析。o 6 本文的主要工作1 我们称由序列的广义差错所产生的数据空间为a h g n m e n t 空间，本文给出了该空间是个度量空间的严格证明，说明了最优比对的不唯性，并给出最小罚分比绪论对与最大得分比对的不等价性与等价条件对信息科学中的广义纠错码，利用比对算法，给出了它们的编译码算法，并且在码长较小时，给出几组最优的广义纠错码。2 将广义差错应用于复杂度理论，提出容错复杂度的概念，论证了容错复杂度的密码体制的安全性更强，因此容错复杂度是密码学与生物信息学的一个结合点，既可以应用于密码学中的乱数流设计，也可以作为生物信息学中研究生物语言的工具。在对生物序列的分析中引入容错复杂度，可以大大降低生物序列的非线性复杂度，得到d n a 片断之间的相互递推关系。3 为了解决真核生物基因识别的问题，本文运用了模糊神经网络的方法，对于真核生物基因识别的因素进行了深入的分析分别在单因素，低因素( 因素个数为2 ，3 ，4 ，5 ) ，高因素( 因素数大于5 ) ，得到这些因素的在不同组合下的识别精度。最后得到影响真核生物基因识别的几个最重要的因素，发现这几个因素的对真核基因的识别可达到了很高的精度水平4 使用k u l l b a c k - l e i b l e r 互熵作为不同分布的差异性度量，给出了分布族聚类的一个算法e m r ，并且证明了该算法的收敛性。最后将其应用于蛋白质序列的聚类，本文使用s w i * p r o t4 4 0 版数据库，对其中的1 5 3 8 7 1 条蛋白质序列进行聚类并建立相应的分类数据库第一章生物信悫学中的跑对阂题l + l 生物序列1 1 1 生物序列的结构在生物学审，遗传单位d n a 以投翡戆单位蛋自蒺帮蹙囊嚣定数基的生物分子燕震捧确鏊残懿。羚n a 穰r n a 囊4 秘垒物分子组戒，努蒡l 怒a ，e ，g ，t 程矗，e ，g ，移，在空间中形成双螺旋结梅在蛋白旗中则由2 0 种标准氯麓酸组成，氨基酸的序列在空间中首先形成二级结构然后形成熙加复杂的结构，这憋结构往往和功能息息相关在生物信息学中，对应于它们的空间结构，由这些生物分子组成的序列往往称之为一级结构，在本文中称为生物序列或尝楚髂为序列对这浆生物j 笋刭鲸分析是生物偿患学最基稿懿舔突疼容。图1 1 ：d n a 分子结构示意圉旁爽戮瓣楚蔗懿分羲懿基疆，宪黠手发理生凌痔粥弱镌鹚稻臻锈绫囊遂绽镶惫有着重要的作用。有实验证孵，这燕生物序列决定了序列的结构和功能耜似的序辫往往具有糨似的结构和功能在结构和功能的研究中，序列的相似性往往是首先鹱得到的l 。2a 邀n 臻e 砖算法序列的最傀比对实际是个最优化问题，由于生物序列的特劳管陛，比对常常叉被1 2第一章生物信息学中的比对问题1 3分为全局比对和局部比对，局部比对在全局上往往不是最优的，但是有其生物上的意义，因为一条生物序列各个部分的重要