（计算机软件与理论专业论文）抗体结合位结构比对技术的研究和实现.pdf

抗体结合位结构比对技术的研究与实现上海师范人学硕士学位论文 摘要 生物信息学是包括生物学、数学、物理学、信息科学以及计算机科学等诸 多学科的新型交叉学科，是以计算机为工具对生物信息进行储存、检索和分析 的科学。蛋白质组学的研究是其中非常重要的方面。结构比对是蛋白质研究的 一个方向，通过结构比对，查找出序列比对无法发现的隐藏信息是结构比对的 研究目标，并通过结构比对推动蛋白质研究邻域的发展。 本文在蛋白质结构比对的基础上，根据抗体结合位的空间结构特性，提出 了一种新的结构比对方法。该方法是建立在原子空间坐标信息的基础上进行的 结构比对，没有使用任何氨基酸序列信息，所以是一种真正的三维结构比对方 法。该方法通过建立局部坐标系将比对物体配准，进而查找匹配的原子；然后 逐步扩大搜索区域来查找最大局部相似结构，接着使用i c p 法提高匹配的精度， 最后将匹配的结构位点作为生物学研究的数据。通过实验证明了本算法的可行 性。 散乱点集中的点除了坐标信息外没有任何拓扑信息及特征信息，所以本文 根据点与周围邻近点的关系对点进行分析，从而提取点的特征信息。通过这些 点的特征信息可以对点进行分类，从而减少进行局部搜索的基数，降低算法复 杂度，减少本算法的运算时间。 关键字；生物信息学结构比对三维散乱点曲面逼近i c p 算法 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 a b s t r a c t b i o i n f o r m a t i c si san e wc r o s ss u b j e c ti n c l u d i n gb i o l o g y , m a t h e m a t i c s ，p h y s i c s ， a n di n f o r m a t i c s i ti sav e r yi m p o r t a n tw a yt os t o r a g e ，r e t r i e v a l ，a n a l y z el a r g ea m o u n t o fd a t ab yc o m p u t e rt e c h n i q u e p r o t e o m i c si sa ni m p o r t a n ta s p e c to fb i o i n f o r m a t i c s s t r u c t u r ec o m p a r i s o ni so n eo fd i r e c t i o n so fb i o i n f o r m a t i c sd e v e l o p m e n t t h r o u g ht h e c o m p a r i s o no fp r o t e i ns t r u c t u r e sw ec a nf i n d s o m eh i d i n gi n f o r m a t i o nw h i c hi s u n a b l et ob ef o u n db ys e q u e n c ec o m p a r i s o n ，w h i c hi sat a r g e to fs t r u c t u r ec o m p a r i s o n t h e nt h ed e v e l o p m e n to fp r o t e i nr e s e a r c hi sp r o m o t e db yi t t h i sp a p e rp r e s e n t san e ww a yo fc o m p a r i s o ni sa c c o r d i n gt ot h et r a i to fa n t i b o d y i n t e r f a c et h r e e d i m e n s i o ns t r u c t u r e ，w h i c hi sb a s e do nt h e p r o t e i n s t r u c t u r e c o m p a r i s o n t h i sm e t h o do n l yu s e sc o o r d i n a t eo fa t o mr a t h e rt h a na n ya m i n oa c i d s e q u e n c ei n f o r m a t i o n ，t h e r e f o r e ，i ti sat r u et h r e e d i m e n s i o n a ls t r u c t u r ec o m p a r i s o n a p p r o a c h e s f i r s t l y , w eu s el o c a lc o o r d i n a t es y s t e mt oa l i g nt w oo b j e c t sf r o mw h i c h w es e a r c ht h em a t c h i n ga t o m s e c o n d l y , b r o a d e ns e a r c ha r e at of i n dt h eb i g g e s tp a r t i a l s i m i l a rs t r u c t u r e t h e nu s ei p ca r i t h m e t i ct oi m p r o v et h em a t c h i n ga c c u r a c y f i n a l l y , t a k et h em a t c h i n ga t o ma st h es t u d yd a t ao fb i o l o g y t h ef e a s i b i l i t yo fa r i t h m e t i ci s v a l i d a t e db ye x p e r i m e n t ， t h e r ei sn ot o p o l o g i c a li n f o r m a t i o na tt h ep o i n tw h e r es c a t t e r e dp o i n ts e t a c c o r d i n g t ot h er e l a t i o n s h i pb e t w e e np o i n ta n dt h o s eo fs u r r o u n d i n gn e i g h b o r h o o d t h i sp a p e rg e t sc h a r a c t e ri n f o r m a t i o no fp o i n t s ，a n dt h e nc l a s s i f i e st h e m ，w h i c hc a n r e d u c et h en u m b e ro fl o c a ls e a r c hs i t e so fa n t i b o d yi n t e r f a c es t r u c t u r ec o m p a r i s o n a r i t h m e t i c ；a sar e s u l t ，t h ec o m p l e x i t ya n dt h er u n n i n gt i m eo fa l g o r i t h m sw i l lb e r e d u c e d k e yw o r d s ：b i o i n f o r m a t i c s ，s t r u c t u r a lc o m p a r i s o n ，3 ds c a t t e r e dd a t a , s u r f a c e a p p r o x i m a t i o n ，i c pa r i t h m e t i c 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中 除了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声 明并表示了谢意。 作者签名：壶娘吼柳。7 。，y 丁 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后 遵守此规定。 阳吲日期：聊弦们 抗体结合位结构比对技术的研究与实现上海师范人学硕士学位论文 1 1 论文研究背景 第一章绪论 生物信息学( b i o i n f o r m a t i c s ) 是近年来发展起来的一个包括生物学、数学、 物理学、信息科学以及计算机科学等诸多学科的新型交叉学科。其研究重点主 要体现在基因组学( g e n o m i c s ) 和蛋白学( p r o t e o m i c s ) 两方面，其主要任务是分 析研究序列数据中所含的各种信息，特别是d n a 序列中的遗传及调控信息，研 究蛋白质序列与结构及功能的关系。生物信息学力求在生物体的整体水平发现 生命信息的传递和指导功能，在整体水平上认识生命现象，并将此类信息与生 物体和生命过程的生理生化信息相结合，阐明其分子机理，最终进行蛋白质、 核酸的分子设计、药物设计和个体化的医疗保健设计。生物信息学已成为整个 生命科学发展的重要组成部分。“儿”啪 蛋白一蛋白相互作用是许多生物过程的基础，包括信号传导和基因表达调 控，都依赖于蛋白一蛋白相互作用。蛋白一蛋白相互作用使得相应的蛋白质之间 可以形成稳定的复合物，包括抗原一抗体复合物，蛋白酶一抑制剂复合物以及激 素一激素受体复合物。这些蛋白质通过蛋白一蛋白相互作用形成稳定复合物，在 生物体内共同起作用。生物信息学的一个基本观点是：分子的结构决定分子的 性质和分子的功能。生物大分子蛋白质的空间结构决定蛋白质的生物学功能。 因此进行蛋白质结构的研究有重大的意义。 抗体因其分子结构和功能的特点，是研究蛋白一蛋白相互作用的理想模型。 抗体分子与功能的研究成果使生物医药领域发生了革命性变化，为威胁人类健 康的重大疾病提供了有效的诊疗手段。然而，对抗体分子结构和功能变化的规 律认识还不充分，单纯应用生物学技术手段难以迅速获得所需的功能性抗体分 子。为解决这一问题，必须加快建立抗体分子结构与功能研究的创新体系。近 年来，由于生物信息学、蛋白质组学等学科的高速发展，为从分子进化角度研 究抗体结构与功能提供了契机。 抗体结合位结构比对技术的研究与实现 上海师范大学硕士学位论文 本课题围绕抗体分子结构和功能变化规律这个关键问题，通过抗原一抗体晶 体结构的比对，尤其是抗原一抗体作用界面和作用位点的空间结构比对，从原子 层面上尝试解释抗原一抗体相互作用的基本规律，包括保守的残基和位点，抗原 表位与抗体表位在空间结构上的特殊性，抗原一抗体相互作用中主要作用力。 1 2 分子结构研究意义 分子结构的研究意义如下。“”“3 ： 1 ) 蛋白质序列足够相似，那么蛋白质结构也是相似的。但是，这并不意味着 具有相似结构蛋白质一定具有相似的序列。实际上存在这样的情况，即两个蛋白 质的序列完全不同，但是它们却具有相似的结构。两个从不同进化源点出发的蛋 白质，由于趋同进化的作用，可能会折叠成相似的空间结构。因此，为了发现具 有相似结构的蛋白质，需要在结构水平上比较蛋白质。 2 ) 蛋白质的结构比序列更加保守。通过比较蛋白质的空间结构，可以发现蛋 白质的结构共性，发现属于同一家族蛋白质的保守结构，发现与蛋白质功能密切 相关的结构域，发现特定的空间结构模式，而这种模式在进行序列分析时无法发 现。同时，通过比较蛋白质的结构，可以对蛋白质进行结构分类。 3 ) 抗原抗体是蛋白质的一种，抗原抗体的结合位置并非是随机的，而是发生 在具有特殊三维结构的特殊部位。这些特殊的结构是针对特定的结合分子，限制 其它分子在这个部位结合。这些部分又称为结合位。在整个抗体结构中，与各种 抗原结合的位是最重要的。结合位至少包含5 段随机肽链其中有重链和轻链它们 并不是仅由一个基因编码的如果有1 0 个片断，总组合就是1 0 0 ，0 0 0 ，于是这个 方法就能够形成多样的结构。通过比较同类抗原抗体，我们可以发现这些结合位。 对于抗原抗体的结合位，通过序列比较，我们只能得到一部分信息。然而，如果 在结构这个层次上进行比较，则可以发现更多的信息。 为此，上海第二医科大学委托上海生物信息研究中心对抗原抗体进行研究， 本课题为其中的一部分。 抗体结合伉结构比对技术的研究与实现上海师范大学硕七学位论文 1 3 国内外研究现状分析 国外一直非常重视生物信息学的发展，在很多邻域都有了比较大的发展。在 蛋白质结构比对研究中，国外已形成了一些技术来比对分子模型。 1 s s a p r s e q u e n t i a ls t r u c t u r ea l i g n m e n tp r o g r a m ) 。j 美国国家研究中心的w r t a y l o ra n d 和纽约大学的c a o r e n g o 提出t s s a p 的比对技术，并被运用于k a t h 系统中。该方法首先定义局部坐标系，通过查找 局部匹配的方式得到最优的全局匹配空间变换矩阵，最后进行比对。但其主要是 根据残基序列顺序为基本比对的依据，所以不是一种真正的三维比对，而是基于 序列比对的一种发展。 2 d a l i ( d i s t a n c em a t r i xa l i g n m e n t ) 1 2 7 】 d a l i 由h o l ma n ds a n d e r 提出是一种以距离矩阵来进行比对的方法。他将蛋白 质三维结构转换为二维距离矩阵，并且将该矩阵再分成6 6 的子矩阵。然后，它 汇编成一个子矩阵匹配表，该表根据子矩阵和子矩阵弹性的相似得分为基础。然 后通过将这些分子矩阵匹配对组合成大集合的对应残基，集合将给出最大相似得 分。该技术使用了m o n t e c a r l o 优化和分支跳跃搜索。该技术应用在f s s f 和d d d 结 构类标注系统中。该方法速度较快，也有较高的精确度。 3 v a s t ( v e c t o ra l i g n m e n ts e a r c ht 0 0 1 ) 1 2 8 1 g i b r a t 提出，该技术在三维空间中将蛋白质二级结构( s s e s ) 作为线性片断， 并且使用图片理论来对准他们。所有成对的同类型二级结构表示为一幅图中的点， 那些拥有相似的距离和角度属性的点用边联系起来。接着使用最大集团检测算法 来发现公共同形子图，然后在两个结构之间进行初级对准。接着使用吉布斯采样 方法来将初级对准延伸到原子级的细化对准。 4 c e ( c o m b i n a t o r i a le x t e n s i o n l 1 2 - 5 】 s h i n d y a l o va n db o u r n e 提出，该技术也是一个流行的结构比对技术。它首先 选择一个局部的初始对齐框架对( a f p ) 作为对齐的基本方式，然后通过添加新的 a f p 来组合扩展对齐方式。不断重复的添加a f p 直到每个蛋白质的长度都被扫描 过，或者没有好的a f p s 存在就中止。 国内对生物信息学领域也越来越重视，在一些著名院士和教授的带领下，在 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 各自领域取得了一定成绩，有的在国际上还占有一席之地。如北京大学的罗静初 和顾孝诚教授在生物信息学网站建设方面、中科院生物物理所的陈润生研究员 在e s t 序列拼接方面以及在基因组演化方面、天津大学的张春霆院士在d n a 序 列的分析方面都取得重要成果。但与国外相比还是有一定的差距。在结构比对 方面，目前还没有深入研究。 1 4 论文的主要内容和章节安排 本文根据抗体结合位的结构特点提出了一种新的结构比对方法。该方法通 过对原始数据的预先处理，提取点的局部分布特征和表面信息。然后使用最大 局部匹配法将物体进行初次配准，接着使用i c p 算法将初次筛选的局部匹配精 确配准。最后提取两个比对物体重叠的位点作为生物学分析的数据。实验证明 本方法能够很好的应用于抗体结合位进行结构比对，也可以应用于一般的蛋白 质结构比对中，是在结构比对上所进行的一次有益的探索。 本论文的章节安排如下： 第一章全文概述，介绍了论文研究背景和国内外结构比对发展现状，并讨 论了本课题的研究内容和意义。 第二章介绍本文涉及的理论知识。包括生物信息学研究对象，抗体介绍， 数学理论知识，和编程平台。 第三章对原始数据进行处理，提取特征信息，从而可以对点集中的点进行 分类。 第四章介绍了一种新的基于局部匹配的二次配准比对方法。详细介绍了算 法的流程，并通过实验说明本算法的可行性。 第五章对论文进行了总结和展望。在总结全文的基础上，概述了本文的创 新点，以及未来进一步的研究方向。 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 第二章结构比对理论基础 2 1 生物信息学的主要研究内容 生物信息学主要包括以下几个主要研究领域，这里仅列出其名称并只做简 单介绍。口1 嘲 1 、序列比对。 基本问题是比较两个或两个以上符号序列的相似性或不相似性。序列比对 是生物信息学的基础，非常重要。两个序列的比对有较成熟的动态规划算法， 以及在此基础上编写的比对软件包一b a l s t 和f a s t a ，可以免费下载使用。这些 软件在数据库查询和搜索中有重要的应用。有时两个序列总体并不很相似，但 某些局部片断相似性很高。s m i t h - w a t e r m a n 算法是解决局部比对的好算法，缺 点是速度较慢。两个以上序列的多重序列比对目前还缺乏快速而又十分有效的 算法。 2 、结构比对。 基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相似 性。通过空间结构上的分析来反映蛋白质间的进化和演变过程，可以发现序列 比对不能发现的生物信息。这方面的研究相对较晚，已经提出了几种算法来进 行结构比对，包括成对比对，多维比对等，但仍有大量的工作要做。 3 、蛋白质结构预测，包括2 级和3 级结构预测，是最重要的课题之一。 从方法上来看有演绎法和归纳法两种途径。前者主要是从一些基本原理或 假设出发来预测和研究蛋白质的结构和折叠过程。分子力学和分子动力学属这 一范畴。后者主要是从观察和总结已知结构的蛋白质结构规律出发来预测未知 蛋白质的结构。同源模建和指认( t h r e a d i n g ) 方法属于这一范畴。虽然经过3 0 余年的努力，蛋白结构预测研究现状远远不能满足实际需要。 4 、计算机辅助基因识别。 基本问题是给定基因组序列后，正确识别基因的范围和在基因组序列中的 精确位置这是最重要的课题之一，而且越来越重要。经过2 0 余年的努力，提 抗体结合位结构比对技术的研究与实现 上海师范大学硕士学位论文 出了数十种算法，有十种左右重要的算法和相应软件上网提供免费服务。原核 生物计算机辅助基因识别相对容易些，结果好一些。从具有较多内含因子的真 核生物基因组序列中正确识别出起始密码子、剪切位点和终止密码子，是个相 当困难的问题，研究现状不能令人满意，仍有大量的工作要做。 5 、非编码区分析和d n a 语言研究。 在人类基因组中，编码部分仅占总序列的3 5 ，其它通常称为“垃 圾”d n a ，其实一点也不是垃圾，只是我们暂时还不知道其重要的功能。分析非 编码区d n a 序列需要大胆的想象和崭新的研究思路和方法。d n a 序列作为一种遗 传语言，不仅体现在编码序列之中，而且隐含在非编码序列之中。 6 、分子进化和比较基因组学。 早期的工作主要是利用不同物种中同一种基因序列的异同来研究生物的进 化，构建进化树。既可以用d n a 序列也可以用其编码的氨基酸序列来做，甚至 于可通过相关蛋白质的结构比对来研究分子进化。以上研究已经积累了大量的 工作。近年来由于较多模式生物基因组测序任务的完成，为从整个基因组的角 度来研究分子进化提供了条件。比较两个或多个完整基因组这一工作需要新的 思路和方法，这方面可做的工作是很多的。 7 、序列重叠群装配。 一般来说，根据现行的测序技术，每次反应只能测出5 0 0 或更多一些碱基 对的序列，这就有一个把大量的较短的序列全体构成了重叠群( c o n t i g s ) 。逐步 把它们拼接起来，形成序列更长的重叠群，直至得到完整序列的过程称为重叠 群装配。拼接e s t 数据以发现全长新基因也有类似的问题。已经证明，这是一 个n p 一完备性算法问题。 8 、遗传密码的起源。 遗传密码为什么是现在这样的? 这一直是一个谜。一种最简单的理论认为， 密码子与氨基酸之间的关系是生物进化历史上一次偶然的事件而造成的，并被 固定在现代生物最后的共同祖先里，一直延续至今。不同于这种“冻结”理论， 有人曾分别提出过选择优化、化学和历史等三种学说来解释遗传密码。随着各 种生物基因组测序任务的完成，为研究遗传密码的起源和检验上述理论的真伪 提供了新的素材。 抗体结合位结构比对技术的研究与实现 上海师范人学硕士学位论文 9 、基于结构的药物设计。 人类基因组计划的目的之一在于阐明人的约1 0 万种蛋白质的结构、功能、 相互作用以及与各种人类疾病之间的关系，寻求各种治疗和预防方法，包括药 物治疗。基于生物大分子结构的药物设计是生物信息学中的极为重要的研究领 域。为了抑制某些酶或蛋白质的活性，在己知其3 级结构的基础上，可以利用 分子对接算法，在计算机上设计抑制剂分子，作为候选药物。这种发现新药物 的方法有强大的生命力，也有着巨大的经济效益。 l o 、其他。 基因表达浦分析，代谢网络分析；基因芯片设计和蛋白质组学数据分析等， 逐渐成为生物信息学中新兴的重要研究领域。 2 2 抗体简介 2 2 1 抗体的定义 抗体”( a n t i b o d y ) 是机体在抗原物质刺激下，由b 细胞分化成的浆细胞所产 生的、可与相应抗原发生特异性结合反应的免疫球蛋白。因为最初有人用电泳 证明血清中抗体活性在y 球蛋白部分，故曾把抗体统称为两种( y ) 球蛋白。后 来证明，抗体并不都在y 区；而且位于y 区的球蛋白，也不一定都具有抗体 活性。1 9 6 4 年，世界卫生组织举行专门会议，将具有抗体活性以及与抗体相关 的球蛋白统称为免疫球蛋白( i 曲。如骨髓瘤蛋白，巨球蛋白血症、冷球蛋白血症 等患者血清中存在的异常免疫球蛋白以及“正常人”天然存在的免疫球蛋白亚 单位等。因而免疫球蛋白是结构及化学的概念，而抗体是生物学及功能的概念。 可以说，所有抗体都是免疫球蛋白，但并非所有免疫球蛋白都是抗体。 2 2 2 抗体的分类 抗体的分类可按以下几种方式分类吲n 0 1 ： ( 1 ) 按作用对象，可将其分为抗毒素、抗菌抗体，抗病毒抗体和亲细胞抗体( 能 与细胞结合的免疫球蛋白，如1 型变态反应中的l g e 反应素抗体，能吸附在靶细 胞膜上) 。 ( 2 ) 按理化性质和生物学功能，可将其分为i g g 、i e , a 、i g m 、i g e 、l e d 五类。 抗体结合位结构t t e 技术的研究与实现 上海师范大学硕十学位论文 ( 3 ) 按与抗原结合后是否出现可见反应，可将其分为：在介质参与下出现可 见结合反应的完全抗体，即通常所说的抗体，以及不出现可见反应，但能阻抑 抗原与其相应的完全抗体结合的不完全抗体。 ( 4 ) 按抗体的来源，可将其分为天然抗体和免疫抗体。 2 2 3 抗原抗体结合物的三维结构 抗原抗体及其结合物的三维结构“”：抗原是单链结构，由分子组成。抗体 是双链结构，由一条重链，一条轻链组成。如下图2 1 所示。红色单链的为抗 原，抗体由蓝色的和绿色的双链组成。当抗原抗体相结合时，他们相结合的部 位称为接触面，是分析抗原抗体结合性的重要部位。本文主要是研究和实现抗 体结合部位的结构比对技术。 2 3 四元数 图2 1 抗原抗体结合图 首先谈谈欧拉角：欧拉角本来是航天飞行模拟器中表示飞机方位的术语，欧 拉角被定义为( r o l l ，p i t c h ，y a w ) ，相当绕x ，y ，z 轴的旋转角度。用欧拉角来表 示旋转是非常方便简洁的。但是它有一个问题：就是会产生万向节锁。 万向节锁是使用欧拉角产生的病态现象。因为最后的旋转矩阵依赖于多次 旋转的先后次序，所以有时候绕一个轴的旋转会被映射到到另外一个轴上去。 更糟糕的是，它甚至使在某个轴上的旋转不可实现。比如，假设一个物体被旋 抗体结合位结构比对技术的研究与实现 上海师范大学硕十学位论文 转的顺序依次是z ，y ，x ，并且绕y 轴的旋转角度是9 0 度，这样，首先绕z 轴旋 转，然后绕y 轴旋转，此时，z 轴被转到了x 轴，这样任何在x 轴上的旋转实际 上就是在z 轴上的旋转。 使用四元数“”“”有两个主要的理由：避免万向节锁，在旋转时允许平滑插 值。刚才说了，万向节锁是一种容易影响到欧拉角表现的现象。本质上说，它 意味着你将在某些时候失去角度上的自由性。这归咎于欧拉角总是以球坐标系 表示。绕着一个轴旋转不能够再适应其它的轴，你可以在一个位置停止，在那 里两个轴的作用相互抵消掉了，那看起来就好像其中一个轴断了一样。四元数 就不会遭受万向节锁的痛苦，因为它不用三个分离的轴表示旋转。使用四元数 的第二个理由，就是其可实现两个状态问的平滑插值。四元数支持球形线性插 值( s l e r p ) ，那意味着点沿着球体表面传播就像他们从一个方位移到另外一个一 样。 2 3 1 四元数概念 一般复数是一个实部和一个虚部，写成c = x + i y 。四元数( ( o u a t e r n i o n ) 把 复数概念扩充到高维。一个四元数有一个实部( 标量部分) 和三个虚部( 向量部 分) ，写为： q = s + i a + j b + k c 或者q = ( s ，v ) 其中，虚数项系数a ，b 和c 是实数：参数s 也是实数，它是标量部分。 参数i ，j ，k 有如下特性： i2 = j 2 = k ? - 一1 ， 单位四元数q = ( 1 ，( 0 ，0 ，0 ) ) 四元数的模：= 丁i 了干驴了7 单位化的四元数的特点是其模为1 ，即：以丁i 干丽：1 。 2 3 2 四元数的运算 ( 1 ) 四元数的单位化 抗体结合位结构比对技术的研究与实现 上海师范大学硕士学位论文 。1 。：腰i 再7 s = s s c a l e ，a = a s c a l e ， ( 2 ) 四元数的加法 q l + q 2 = ( s l + s 2 ，v l + v 2 ) ( 3 ) 四元数的乘法 q l q 2 = ( s l s 2 一v l v 2 。s l v 2 + s 2 v l + v l v 2 ) ( 4 ) 四元数的点乘 d o t ( q l ，q 2 ) = q 1 sq 2 s + q 1 aq 2 a + q 1 bq 2 b + q 1 cq 2 c ( 5 ) 旋转轴和旋转角转换为四元数 已知旋转轴u ( x ，y ，z ) 和绕u 旋转的角0 ，则 s = c o s ( 0 2 ) ，y = us i n ( 0 2 ) 四元数转换为旋转抽( x ，y ，z ) 和旋转角0 0 = 2 a r c c o s ( s ) ， 若0 o ，则 u x = v 。a s i n ( 0 2 ) ，u y = v b s i n ( 0 2 ) ，u z = v c s i n ( 0 2 ) 若e ：o ，则认为绕旋转轴无旋转，可使t l = v ( 6 ) 四元数转换为旋转矩阵 由四元数转换为旋转矩阵如下： 1 2 b 2 2 c 22 a b 一2 s c2 a c + 2 s b i 2 a b + 2 s c1 2 a 2 2 c 2 2 b c 一2 s a i2 a c 一2 s b2 b c + 2 s a 1 2 a2 2 b 2 【 o oo ( 7 ) 旋转矩阵m 转换为四元数 有了上面这个矩阵，就可以反求四元数了。 m 0 0 + m l l + m 2 2 + m 3 3 = 4 ( 1 一a z _ b a - c 2 ) = 4 s 2 由上式可解出s ， 由l d , o - m 。= 4 s c 可解出c ， 由。- m a = 4 s b 可解出b ， 由广m 。产4 s a 可解出a 。 ( 8 ) 欧拉角转换为四元数 抗体结合位结构比对技术的研究与实现 上海师范大学硕士学位论文 假设对应于x ，y ，z 轴的欧拉角为n 、b 和r ， 由旋转轴x 和旋转角a 得到四元数q x ，即： q x = ( c o s ( a 2 ) ，( s i n ( a 2 ) ，0 ，0 ) ) ： 由旋转轴y 和旋转角b 得到四元数q y ，即： q y = ( c o s ( b 2 ) ，( s i n ( b 2 ) ，0 ，0 ) ) ： 由旋转轴x 和旋转角y 得到四元数q z ，即： q z = ( c o s ( y 2 ) ，( s i n ( y 2 ) ，o ，o ) ) ： 最后得到的四元数是q = q x q y q z 。 2 4 模糊理论概述 模糊理论”。”是在美n n # i 大学电气工程系l a z a d e h 教授于1 9 6 5 年创立 的模糊集理论的数学基础上发展起来的，主要包括模糊集理论、模糊逻辑、模 糊推理和模糊控制等方面的内容。 目前，对待模糊理论，学术界一直有两种不同的观点，其中持否定态度观 点的大有人在，客观地说，有如下两个主要方面的原因：其一是推崇模糊理论 的学者在强调其不依赖于精确的数学模型时过分地夸大了其功效，而正确的观 点似乎应该是模糊控制不依赖于被控对象的精确数学模型，当然它也不应该拒 绝有效的数学模型。模糊控制理论在其特定的条件下可以达到经典控制理论难 以达到的“满意控制”，而不是最优控制；其二是模糊理论的确还有许多不完善 之处，比如模糊规则的获取和确定，隶属函数的选择以及稳定性问题至今还未 得到完善的解决。尽管如此，大量的工程系统已经应用上了模糊理论，特别是 日本，尤为重视模糊理论的工程应用。从发展来看，模糊控制已经成为智能控 制的一个重要分支。 2 4 1 模糊集的概念 在经典集合论中，任何一个元素与任何一个集合之间的关系，只有“属于” 和“不属于”两种情况，两者必居其一，而且只具其一，绝对不允许模棱两可。 比如“不大于5 的自然数”是一个清晰的概念，该概念的内涵和外延都是明确 的。可是，我们也经常遇到没有明确外延的概念，这种概念实质上是模糊的概 抗体结合位结构比对技术的研究与实现上海师范丈学硕士学位论文 念。例如， “比5 大得多的自然数”就是一个模糊概念。可以想象无法划定一 个明确的界限，使得在这个界限内所有自然数都比5 大得多，而界限外的所有 自然数都不比5 大得多。只能说某个数属于“比5 大得多”的程度高，而另一 个数属于“比5 大得多”的程度低，比如5 0 属于“比5 大得多”的程度比1 0 属于“比5 大得多”的程度高。 l a z a d e h 在1 9 6 5 年把普遍集合中的元素对集合的隶属度只能取0 和1 这 两个值推广到可以取区间 0 ，1 中的任意一个数值。即可以用隶属度定量去描述 论域u 中的元素符合概念的程度，实现了对普通集合中绝对隶属关系的扩充， 从而用隶属函数表示模糊集合，用模糊集合表示模糊概念。模糊集合具体定义 如下。 定义1 2 1 设u 为论域，则【厂上的一个模糊集合a 由【，上的一个实值函 数 u 一【0 , 1 】 儿2 “一心 ) 来表示。对于“【厂，函数值心 ) 称n u 对于爿的隶属度，而函数心称为 a 的隶属度函数，其图形 ，f l 图2 1 隶属函数图 由此可见，模糊集合a 是一个抽象的概念，其元素是不确定的，我们只能 通过隶属函数以来认识和掌握a 。儿( “) 的数值大小反映了论域u 中的元素u 对于模糊集合a 的隶属程度，心 ) 的值越接近于1 ，表示“隶属于彳的程度越 抗体结合位结构比对技术的研究与实现 上海师范大学硕士学位论文 高；心( “) 的值越接近于0 ，表示“隶属于爿程度越低。特别地，若。以) = 1 则认为u 完全属于a ；若心以) = 0 ，则认为“完全不属于4 。 经典集合和模糊集合日j 的关系可以这样来概括：模糊集合是清晰集合在概 念上的拓广，或者说清晰集合是模糊集合的一种特殊形式；而隶属函数则是特 征函数的扩展，或者说，特征函数只是隶属函数的一个特例。模糊集合完全由 它的隶属函数来刻画。 2 4 2 模糊模式识别直接方法的基本原理 设u = 伽。，h ：，“。) 为待识别对象所构成的集合，u 中每一个待识别对象 有i n 个特性指标u f l ，“，“h ，记 “j = f 1 “f 2 ，“h )o = 1 ，2 ，n ) 设待识别对象集合u 可分成p 个类别，且每一类别均为u 上的一个模糊集， 记为4 ，爿：，一。，则称它们为模糊模式。 现在的问题是：给定一个对象“，u ，如何识别“；归属于4 ，a ：，a 。中哪 一类比较合适? 首先，我们注意到a 1 ，彳：，a ，都是u 上的模糊集，故可求出u ，对 a 。，彳：，a ，相应的隶属度为爿，0 ；) ，a ：u a 4 ， 。) 。显然，u ，对哪一个模糊模 式的隶属程度最大，就把u ；归属于哪一类是比较合适的，这就是下面要介绍的 隶属原则。 1 最大隶属度原则 设a 为给定论域u 上的一个模糊模式，“，“：，“。为u 中的，z 个待识别对 象，若 a ( u 。) = m a x 似 1 ) ，a ( u 2 ) ，a ( u 。) ) ， 则认为u ，优先归属于模糊模式a 。 2 最大隶属原则 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 设爿。爿2 ，a ，为给定论域u 上的p 个模糊模式，“。e u 为一个待识别对 象，若 爿。 o ) = m a x a 1 o ) ，a 2 o ) ，a 。0 0 ) ) ， 则认为u 。优先归属于模糊模式4 。若这样的模糊模式不止一个，则应考虑 别的因素和别的标准，加以进一步判断。 3 阈值原则 设4 ，4 ：，彳，为给定论域u 上的p 个模糊模式，规定一个阈值( 置信水 平) a ( o 川，“。u 为一个待识别对象。 ( 1 ) 如果 m a x 似。以o ) ，a 2 o ) ，爿。 。) ) n 时，一般不可能使所有的残差为零， r ( x 1 在范数意义下最小： i p 一血j f ：2 肛c x ) i ：2m ，i n i ，( y ) i i ：。m 脚i n 怜一6 ：( 3 - - 4 ) 3 3 2 线性最小二乘法 n 。r m a le q u a t i 。n s ) ，奇异值分解法s v d ( s i n g u l a rv a l u ed e c o m p o s i t i 。n ) 和特征 向量估计法e v e ( e i g e n v e c t o rg s t i m a r i o n ) 在法方程( 2 5 ) 中， c 1 当b 一0 ra 为非奇异矩阵，即07 一) - 1 存在时，系数矩阵x 可以通过方 栏 4 7 血；4 7 6 ( 3 6 ) 求解得到，方程( 2 6 ) 称为法方程，此时x = 0 7 4 ) 1 爿7 b 这种方法称为法方程 法。 2 当b ，o 且a 为奇异矩阵时，为了避免计算07 爿r 1 ，将矩阵a 分解为 a ；u w v 7 ( 3 7 ) 其中w 为元素为非负值的对角矩阵，u 和v 都是正交矩阵( 列向量正交) ，即 w 。p f 口g ( w jj j ，u r u 一矿7 矿；1 从而系数矩阵x 可以通过方程 石。矿k n g ( 1 w ，炒 ( 3 8 ) 求解得到，这种方法称为奇异值分解法。一 3 当b = o 时，方程( 2 5 ) 变为 a x ：0 ( 3 9 ) 假设矩阵“r 彳) 的特征值为 ( i ：1 ，9 ) ，如果存在其中一个特征值 2 0 ， 则u r 4 ) x = 九产- o ( 3 1 0 ) 所以对应特征值a ，的特征向量x 即为方程( 2 9 ) 的解，这种方法称为特征向 量估计法。在实际应用中，由于特征值- 不会恰好为零，因此我们将对应其中 绝对值最小的特征值的特征向量作为x 的最小二乘解。 以上三种方法都适用于数据点分布广泛的情况，其中法方程法m n e 速度最快， 而奇异值分解法s v d 由于要对矩阵进行奇异值分解，因而速度也最慢，但当矩阵a 的奇异情况未知时，采用此方法较为稳妥。 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 3 3 3 非线性最小二乘法 非线性最小二乘方法“7 “”3 对应的方程r ( x ) 为非线性方程组，令 6 b ) ；肛b 眶= r ( x ) t r 仁) ( 3 - 1 1 ) 假定r ( x ) ：r 4 一r ”在开凸集d cr ”一r “上f r e c h e t 可微，则 v 6 g ) = 2 r b 厂，g ) ( 3 1 2 ) 于是6 g ) ( 或咿b ) 的局部极小点石必须满足方程 f ( x ) = ，b ) r r ( x ) = o ( 3 1 3 ) 这个方程称为非线性最d - - 乘问题的法方程。一般地说，它是一个非线性 方程组。 我们采用牛顿法的基本思想来求解非线性最d - - 乘问题，常用的是两种迭 代方法：g a u s s n e w t o n 方法和l e v e n b e r g m a r q u a r d t 方法。 g a u s s - n e w t o n 方法算法如下： 算法1 设给定试验数据表d ( t ，y ) ，以及模型y = v ( t ，x ) ，为法方程解工 的一个初始近似，1 为变量个数，n 为参数个数，而m 为试验数据的组数。记 4 一r7 0 忙) ) ，e 。4 ，x ) ；( ，l ，厶厂，k 为迭代序号 按下列步骤迭代求解： 1 ) 计算，n 及( i = 1 ，m ：j = l ，n ) ： 廿坩，= 掣，肚薹掣和) 2 ) 计算6 ) 2 雌拖 3 ) 若精度满足要求，则转 4 ) 求解线性方程组 a i x 恤) 一一r b 恤) ( 4 。t 4 。a x ( ) = 一) 5 ) 计算x 恤+ 1 ) = x “) + x 恤) 6 ) 置k = k 十1 ，转 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 7 ) 置工= 工( “) 并结束迭代 算法1 中迭代收敛判别准则可采用以下算法。 算法2 由主程序输出迭代点耽+ 。，修正量a 及残差平方和屯，屯+ 1 ，此外。， ，。为预先给定的正常数。按下列步骤判别迭代收敛与否： 1 置i = 1 2 若眇“卜即则转5 3 若眇“一x ；| 岛弦，则转1 2 4 转6 5 若i 廿“一x ：l e ：则转1 2 6 若i 6 。以，则转1 2 转1 1 若慨+ 。- 6 。i e 5 ，则转1 2 置工x 。，并转主程序结束迭代 转主程序结束迭代 以上算法的作用是：如果迭代收敛，则6 和x 的k 次迭代结果和k + 1 次迭代 结果在绝对误差或相对误差的意义下十分接近。通常取 s 1 _ 1 0 - 3 ，2 = 1 0 ，3 ：1 0 - 4 ，4 = 1 0 ，f 5 = 1 0 1 0 ，s 6 = 1 0 5 。 g a u s s n e w t o n 法对初始近似要求比较苛刻，初值选取不好，迭代可能不收 敛。 l e v e n b e r g m a r q u a r d t 法对g a u s s n e w t o n 法作了改进，引入了阻尼因子作 为收敛因子，扩大收敛区域，使迭代过程能够稳定进行，因而 l e v e n b e r g m a r q u a r d t 法有时也称为阻尼最小二乘法在实际应用中，一般都采用 l e v e n b e r g m a r q u a r d t 法来求解非线性最小二乘问题。 l e v e n b e r g m a r q u a r d t 方法算法如下： 抗体结合位结构比对技术的研究与实现上海师范大学硕士学位论文 算法3 设给定试验数据表d ( t ，y ) ，模型y 2 y ( t ：x ) ，为法方程解z 的一个 初始近似x 。，初始阻尼因子，缩放常数v 以及允许误差f 。按下列步骤迭代 求解： 1 计算( o ) = ，f g 。) ( i = 1 ，m ) 以及6 g 。) 2 置k = l 3 置心= v 一1p m 4 计算n 及( i = l ，m ；j = 1 ，n ) ： 掣萨薹掣圳) 5 求解线性方程组 ( a r a t + 以i ) 5 x 一e 6 计算x = x + 缸，0 ) ( i = 1 ，m ) 以及6 0 ) 7 若6 b ) 6 b ( ) ，则转9 8 置以= ”以，转5 9 置x “= x 1 0 转算法2 ) ，若收敛准则不满足，则置k = k + 1 ，转3 1 1 置j + = 工“+ 1 ) 并结束迭代 选取阻尼因子。的原则：阻尼因子在保证6 g ) 下降的前提下，宜选取较小的 值，因为当“的值较小时，下降方向值较大，因此加快收敛。但当产值较小而 又不能保证对应的6 & ) 下降，则应选取较大的阻尼因子。不严格的说，阻尼因 子选取的原则应是：尽可能是搜索方向靠近g a u s s n e w t o n 方向，否则就只能转 向6 0 ) 的负梯度方向。常用值为