（概率论与数理统计专业论文）数据分布拟合的em算法及其在生物计算中的应用.pdf

摘要 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，生物信息或基 因数据挖掘更使人类受益匪浅。数据分布的拟合问题是数据发掘理论与应用中的一 个典型问题。这就是为了更确切地了解一批观测数据的统计特性，我们必须确定它 们的分布函数，用已知的概率分布去作拟合。本文的主要内容就是讨论在较一般的 混合分布条件下，用e m 算法，在最小熵原理的优化准则下的数据拟合问题。 传统的e m 算法是我们早已熟知的算法( 见 2 ， 3 ) ，本文是在其基础上提 出了新的优化准则，从而使其更方便的应用于数据分布拟合问题这就是用一般指 数混合分布，对观测数据进行拟合，使它们的k u l l b a 吐l e i b l e r 熵为最小。本文在给 出了拟合计算中的e m 算法后，也证明了该拟合计算的收敛性定理。 在生物计算中存在大量数据拟合问题，本文以蛋白质空间结构分析为例，利用 p d b 数据库对蛋白质空间结构中的几种重要参数进行分布拟合，得到了明显的效 果，并由此可以得到蛋白质空间结构特性。这使得本文提出的基于最小熵原理的e m 算法有着更实际的意义 关键词：数据发掘中的分布拟合问题，最小熵原理，e m 算法，生物计算 中的应用 2 a b s t r a c t a st h eo u t c o r r l eo fm a n sr e 8 e a r c ha n de x p l o r a t i o ni nd a t a b a s et e c h n o l o g y ，d a t a m i n i n g ，e j s p e c i a l l yb i o i n f 6 r m a t i c sa n dg e n ed a t am i n i n g ，m a d eg r e a tb e n e 丘tt op e o p l e d i s t r i b u t i o r lf i t t i n gi sat y p i c a lp r o b l e mi nd a t am i n i “g ，r b 矗n do u tt h es t a t i s t i c a lc h a r a c t e ro fas e to ff i a t a w es h o u l dc o n _ f i r mi t sd i s t r i b u t i o nf h n c t i o na n df l ti t w i t ht h ed i s t r i b u t i o nw e v ek n o w n i nt h i sp a p e r ，w e ( 1 i s c u s s e dt h eg e n e r a lm i x e d 1 i s t r i b u t i o n 五t t i n gw i t he ma l g o r i t h mw h i c hi sb a s e do nl e a s tk u l l b a c k l e i b i e r e n t r o p y n o w ，w ea r ef a m i l i a rw i t ht r a d i t i o n a le ma l g o r i t h m ( 2 】，【3 ) a n di nt h i sp a p e r ，i n o r d e rt o 矗tt h eo b s e r v i n gd i 8 t r i b u t i o nb e t t e r ，w eo 矗i e r e dan e wo p t i m i z e dr u i e t h a ti 8 ， b ym i n i m i z i n gt h ek u l l b a c k - l e i b l e re t r o p y ，、v eu s e 也eg e n e r a lm i x e dd i 8 t r i b u t i o n t of i tt h eo b 8 e r v i n gd a t a 。w ep r c i v i d e de ma l g o r i t h mi nt h ef i t t i n gc o m p u t a t i o na n d p r o v e dl t sc o n v e r g e n c et h e o r y t h e r ea r el o t so fd a t af i t t i n gp r o b i e m si nb i o l o 百c a lc o m p u t a t i o n i nt h i sp a p e r ，伦m a d es o m ed i s t r i b u t i o n 矗t t i n go nt h ep r i m a r yp a r a m e t e r s0 ft h es p a t i a is t r u c t u r eo fp m t e i b yp d bd a t a b a s e a n dt h e n ，w e9 0 tt h es p a c i a ls t r u c t u r ec h a r a c t e r o fp r o t e i n ，f r o n lw h i c hw ec a ns e et h ee ma l g o r i t h mb a s e do ni e a s tk u l l b a c k l e i b k r e n t r o p yi sv e r ye 岱巳c t i v e k e y w o r d s d i s t r i b u t i o nf i t t i n gi d a t am i n i n g ，m i n i m i z e de n t r 郇i yt h e o r y ，e m a l g o r i t h m ，a p p l i c a t i o ni nb i o l o 昏c a lc o m p u t a t i o n 3 引言 人们在生产实践和科学实验中，经常会遇到大量的不同类型的数据( d d t a ) 这 些数据提供了有用的信息，可以帮助我们认识事物的内在规律、研究事物之间的关 系等。挖掘并研究这些有用信息对我们的实践和科学研究起着重要的作用，这就是 我们说的数据挖掘 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，发展到现在已 进入了一个更高级的阶段。生物信息或对基因数据的数据挖掘使人类受益匪浅而 它通常的数据挖掘相比，无论在数据的复杂程度、数据量还有分析和建立模型的算 法面言，都要复杂得多。从分析算法上讲，更需要一些新的和好的算法( 见 1 文) 本文主要是利用数据挖掘中的数据分布拟合问题做生物科学领域中蛋白质空间 结构的分析研究蛋白质的研究是生命科学研究的基础和重大核心l 曰题之一，许多 生物功能都需要通过蛋白质来实现，有无数生命现象的奥秘蕴含其中。它与人们的 生活、健康密切相关，人们健康和疾病的机理、各种新药的备制和食物、品种的改 良都依赖于蛋白质的研究进展 p d b ( p r o t e i d a t ab a n k ) 蛋白质空间结构数据库( 见 8 】文) 是1 9 9 7 年在纽约 建立的b r o o k h m 国家实验室国际蛋白质结构数据库，至今0 4 - 版的p d b 数据库 已有2 0 ，o o o 多个蛋白质结构及核酸数据( 见 1 0 】) 。面对如此大量的数据，我们需 要有好的算法才能准确有效地得到我们需要的结果 因此本文的主要内容就是提出了数据分布拟合问题中的快速递归算法，即e m 算法传统的e m 算法我们早已熟知( 见【2 ，【3 】) ，本文提出的e m 算法，是在 传统的算法基础上，赋予其新的优化准则，使它在最小熵原理的优化准则下发挥快 速准确的递归并收敛的作用，从而让我们在p d b 数据库中找出我们需要的有用信 息，通过比较这些信息就能进而发现蛋白质结构的统计特性至今，这一算法的提 出并应用于蛋白质空间结构的数据分布拟合还是第一次。它在搜索处理p d b 数据 库的大量信息中发挥了快速有效的作用，实现了让我们在有限的时间内准确的掌握 蛋白质空间结构的统计特性的目的。 本文第二节介绍了有关数据挖掘及e m 算法的基本知识，第三节讲述了数据分 布拟合的基本知识，这其中讲述了最小熵原理的作用，并给出了验证结果，第四节给 出了我们提出的对一般指数分布进行数据分布拟合的e m 算法，并对它的收敛性给 出了严格的证明。我们在第五节中就讲述了这一算法在生物计算中的主要应用，这 其中我们的结果是基于沈世镒教授提出的蛋白质主链三角形拼接带构成的模型，之 后对蛋白质主要空间结构的数据进行拟合，并进行了统计分析，得到了蛋白质空间 结构的稳定性的统计特性。最后第六节我们对所得的结果进行了进一步的分析，引 出了可以从转角的角度来对蛋白质的空间结构进行分析的问题。 5 这些算法也可在其他领域( 如金融领域) 中使用，但在本文中我们不作讨论。 2 预备知识 2 1 数据挖掘简介 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更把概 念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好 像从矿石中采矿或淘金一样原始数据可以是结构化的，如关系数据库中的数据； 也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数 据发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是 归纳的发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还 可以用于数据自身的维护因此，数据挖掘是一门交叉学科，它把人们对数据的应 用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持在这种需求牵 引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、 可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的 研究领域，形成新的技术热点( 见 1 】文) 现在，对数据挖掘技术进行支持的三种基础技术已经发展成熟，他们是： 一一海量数据搜集 一一强大的多处理器计算机 一一数据挖掘算法 数据挖掘的核心模块技术历经了数十年的发展。其中包括数理统计、人工智能、 机器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎以及广泛的数据 集成，让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 2 2 数据分布拟合问题及e m 算法简介 数据分布的拟合问题是指：对一批观测数据要了解它们的统计特性，除了计算 它们的特征数( 如均值与方差等) 外，更精确的结果就是要确定它们的分布结构。这 就需要我们用若干已知的概率分布去作拟合因此，数据分布的拟合问题是数据挖 掘理论与应用中的一个典型问题，它在大规模数据与数据库的信息处理中有广泛的 应用。 而在大规模的数据与数据库中，观测数据的结构往往十分复杂，这些数据一般 6 不能用一种单一的分布拟合，而是有多种不同类型分布的混合。因此数据分布的拟 合问题就是要确定该混合分布的类型，不同分布所占的比例，及每个分布的参数。拟 合的结果就是要使观察数据的经验分布与拟合分布的k u l l b a c k l e i b l e r 熵为最小，这 就是分布拟合中的最小熵原理。而这一原理在本文的论述中起了关键性的作用。 在统计领域里，主要有两大类计算问题，一类是极大似然估计的计算，另一类 是b a y e s 估计的计算。e m ( e x p e c t a t i o n m “i m i z a t i o n ) 算法理论就是一种用于最大 似然估计或b a y e s 估计的递推算法，最初由d e m p s t e r 等提出，它的每一次递推由两 步组成；e 步( e x p e c t a t i o n ) 和m 步( m “i m i z a t i o n ) 。一般实现的时候要把这两 步循环运行几次，或者直至收敛为止。这在 2 ，3 ，4 等文中已给予讨论。 1 9 9 6 年x ua n dj o r d a n ( 1 9 9 6 a ) ( 见【5 ，7 等文) 给出了对多元混合正态分布中 各类参数的e m 估计，并证明了它们的收敛性定理在 6 】等文中，x ul e i 又把它 们发展成更一般的b y y 学习理论，实现了在多种类型条件下的优化收敛计算。 那么对于传统的e m 的算法，其优化准贝! l 一般是使其所构造的完全函数的期望 值达到最大，而本文提出的e m 算法是使数据分布与已知混和分布拟合的k u i l b a 出 l e i b k r 熵为最小，这一理论将在下文中论述 3 数据分在的拟合问题 3 1 混合分布 首先，我们介绍一下混合分布的概念设x = z 1 ，z 。) 是一批观测数据， 为了简单起见我们取r 为一维数据，且按大小次序排列。记p ( z ) 为由x 确 定的经验分布，研( z 易) ( z ) ，j = 1 ，2 ，k ，是一组已知的分布函数，其中如是分布 奶中的参数或参数向量，那么称 q ( z 画，百) = q - 劬( z 岛) j = l 为岛( z 坞) ( z ) ，j = 1 ，2 ，的混合分布。其中 丘= ( o l ，0 2 ，- 一，n t ) ，o 而口= ( 口t 。如，民) ，是一组参数，这里记 哦= ( 哦，1 ，哦，2 ，- - ，吼，r 1 ) ，i = 1 ，2 ，- 一，七 ( 3 1 ) ( 3 2 ) 那么数据分布的拟合问题就是求适当的a 与6 ，使混合分布q 肛，口) 与数据分布 p 最为接近。 7 l j j 哟 。赳 3 2 互熵及最小熵原理 由上一小节的结论，我们怎么样才能说两个不同的数据分布比较接近呢? 这里 存在一个不同分布之间的“差异度”的问题。 首先，我们利用熵的概念进行分析。一个概率分布p 的熵乡垆( p ) 的定义如下： 。9 纩( p ) = e ( 一l o gp ) = 一p ( z ) l o g p ( z ) d z 其中p ( 。) 是概率分布p 的密度函数熵的单位取决于对数的底当底为2 ，e ， 3 ，1 0 时，熵的单位分别是“比特”、“奈特”、“铁特”、“笛特”( 相应的英文记 号为：b i t ，n a t ，t e t ，d e t ) ( 见 8 】文) 。在下文中，我们都采用的是底数为2 的对数，因而在我们的拟合结果中，熵的单位均为比特( b i t ) 。熵的概念度量了由 p 分布描述的随机试验结果的先验不确定性或观察到输出时所获得的信息量。 k u l l b a 吐l e i b l e r 熵( 以下简称为互熵) 是指：如果p ，q 是两个不同的概率分布， 那么它们的互熵为： ( 别q ) = 厶l o g ( 筹) p ( 如) = 上p ( 圳。g 器出 ( 3 3 ) 其中z 是p q 分布的取值范围，籍是分布p 关于q 的r 丑d o n n 让m d y m 微商， p ，g 分别是分布p q 的概率分布密度( 见 8 】文) 互熵被看作分布p 和q 之间“距 离”的一种度量分布p 和q 之间越不相似，互熵就越大互熵也可以测量所给出 的信息量，它描述了一个假说相对于另一个假说的真实性它也是对数似然度比值 的期望值 因此，数据分布的拟合问题就是在观测数据x 固定的条件下，求参数a 与百， 使分布p 关于q ( z 肛，口) 的k u l l b a c k - l e i b l e r 熵( p i | q 。口) 为最小蟮拙就是使分布p 与q ( z 加，目) 之间的“差异度”为最小，此即最小熵原理这时有 吲引旧哦曲= 厶p ( 劫l o g 夏翻啦 ( 3 4 ) 其中p ( 。) ，吼，巩分别为分布p ( z ) ，q 瓶的概率分布密度在下文中，我们称( 3 2 ) 的 向量为混合分布的比例分布向量 由此看来，有互熵能够衡量两个不同数据分布之间的“差异度”，才有最小熵 原理的充分应用，进而有我们进行数据分布拟合的e m 算法，因而互熵起着至关重 要的作用。我们只有确定了它作为标准的正确性，才能进行进一步的分析。 3 3 分布( 0 ，1 ) 与( 卢，口2 ) 的拟合 那么在实际应用中，互熵究竟能不能作为衡量两个不同分布之间的“差异度， 的标准呢? 为了验证这一结论，我们可以先用互熵拟合标准正态分布p = ( o ，1 ) 8 与一般正态分布q = ( 一2 ) 。这两个分布是我们日常很熟悉的分布，众所周知， 当一般正态分布( 肛，0 2 ) 中的p 近似于o 、而a 近似于1 时，我们可以说正态分布 ( ，一2 ) 是近似于标准正态分布( o ，1 ) 的，就是说它们的“差异度”很小。那么如 果我们上述互熵的结论是正确的，则当p 在。附近，且a 在1 附近时，由这两个分 布计算出来的互熵应该很小。经过拟合计算，我们所得的结果如下面的表1 ： 表1 标准正态分布与一般正态分布的互熵拟合 口“ 00 0 00 20 0 40 0 60 0 80 1 00 1 20 1 40 1 6 0 5 0 1 1 6 4 0 4l 1 6 5 2 01 1 6 8 6 61 1 7 4 4 31 _ 1 8 2 5 1l 1 9 2 9 01 2 0 5 5 91 2 2 0 6 012 3 7 9 1 05 508 0 0 7 8 0 8 0 1 他08 0 4 5 90 | 8 0 9 3 60 8 l 加40 8 2 4 6 20 8 3 5 1 l0 8 4 7 5 lo 8 6 1 8 2 06 005 4 5 4 30 5 4 6 2 30 5 4 8 6 4o5 5 2 6 4o5 5 8 2 5 o5 6 5 4 705 7 4 2 805 8 4 7 0 0 5 9 6 7 3 06 50 3 6 4 5 00 3 6 5 1 80 3 6 7 2 3 03 7 0 6 4 03 7 5 4 20 3 8 1 5 7o 3 8 9 0 8 03 9 7 9 6 0 。4 0 8 2 0 0 7 00 2 3 6 2 20 2 3 6 8 1o 2 3 8 5 702 4 1 5 20 2 4 5 6 40 2 5 0 9 40 2 5 7 4 202 6 5 0 70 2 7 3 9 0 07 50 1 4 6 0 l0 1 4 6 5 20 1 4 8 0 60 1 5 0 6 3o ，1 5 4 2 20 1 5 8 8 30 1 6 4 4 80 1 7 1 1 50 1 7 8 8 4 0 8 000 8 3 8 30 0 8 4 2 80 0 8 5 6 30 0 8 7 8 90 0 9 1 0 40 0 9 5 1 00 1 0 0 0 60 1 0 5 9 2o 1 1 2 6 8 0 8 50 0 4 2 5 90 0 4 2 9 900 4 4 1 90 0 4 6 1 9o 0 4 8 9 80 0 5 2 5 8o 0 5 6 9 70 0 6 2 1 60 0 6 8 1 5 0 9 000 1 7 2 00 0 1 7 5 60 0 1 8 6 3o0 2 0 4 l 0 0 2 2 9 0 0 0 2 6 l lo 0 3 0 0 300 3 4 6 600 4 0 0 0 0 9 50 0 0 3 9 30 0 0 4 2 5o 0 0 5 2 1o 0 0 6 8 1o 0 0 9 0 40 0 1 1 9 20 ，0 1 5 4 40 0 1 9 5 90 8 2 4 3 9 l0 00 0 0 0 0 00 0 0 0 2 900 0 1 1 50 0 0 2 6 000 0 4 6 200 0 7 2 l0 0 1 0 3 90 0 1 4 1 4o 0 1 8 4 7 1 0 500 0 3 3 30 0 0 3 5 90 ，0 0 4 3 70 0 0 5 6 8o 0 0 7 5 1 0 0 8 7o 0 1 2 7 50 0 1 6 1 5o 0 2 0 0 7 1 1 000 1 2 3 l0 0 1 2 5 50 0 1 3 2 60 0 1 4 4 60 0 1 6 1 30 0 1 8 2 70 0 2 0 9 00 0 2 4 0 000 2 7 5 7 1 1 500 2 5 7 3o 0 2 5 9 50 0 2 6 6 0o 0 2 7 6 9o ，0 2 0 2 20 0 3 1 1 8o ，0 3 3 5 80 0 3 6 4 2o0 3 9 6 9 1 2 000 4 2 6 20 0 4 2 8 20 0 4 3 4 20 0 4 4 4 3o 0 4 5 8 30 0 4 7 6 300 4 9 8 400 5 2 4 4 0 0 5 5 4 5 1 2 5 0 。0 6 2 2 40 0 6 2 4 3 0 0 6 2 9 8 o 0 6 3 9 0o 0 6 6 2 000 6 6 8 60 0 6 8 8 9o o 丁1 2 9o 0 7 4 0 6 1 3 0 0 0 8 4 0 00 0 8 4 1 7 0 0 8 4 6 8 o 0 8 5 5 30 0 8 6 7 30 0 8 8 2 70 0 9 0 1 4o 0 9 2 3 6o 0 9 4 0 2 l 3 50 1 0 7 4 l0 1 0 7 5 70 1 0 8 0 50 1 0 8 8 4o 1 0 50 1 1 1 3 7o n 3 1 1o 1 1 5 1 7o 1 1 7 5 5 1 4 00 1 3 2 1 10 1 3 2 2 60 1 3 2 7 00 1 3 3 4 4o 1 3 4 4 7 o 1 3 5 7 9 0 1 3 7 4 l 0 1 3 9 3 30 1 4 1 5 4 l 4 50 1 5 7 8 0o 1 5 7 9 30 1 5 8 3 40 1 5 。0 30 1 5 9 9 9o 1 6 1 2 30 1 6 2 7 4o 1 6 4 5 20 1 6 6 5 8 l5 00 1 8 4 2 1o 1 8 4 3 40 1 8 4 7 30 1 8 5 3 70 1 8 6 2 7 0 1 8 7 4 20 1 8 8 8 30 1 9 0 5 00 1 9 2 4 2 l f 5 50 2 u 1 70 2 1 1 2 9o 2 1 i 6 5o 2 1 2 2 5o 2 1 3 0 9o 2 1 4 1 70 2 1 5 4 90 2 l 7 0 5o 2 1 8 8 6 i 6 0o 2 3 8 5 002 3 8 6 10 2 3 8 9 50 2 3 9 5 20 2 4 0 3 00 2 4 1 3 20 2 4 2 5 60 2 4 4 0 2 o 2 4 5 7 l 1 6 50 2 6 6 0 8o 2 6 6 1 8o2 6 6 5 0 o 2 6 7 0 3o 2 6 7 7 7 02 6 8 7 3 0 2 6 9 8 902 7 1 2 70 2 7 2 8 6 17 002 9 3 7 9 0 2 9 3 8 9 02 9 4 1 9 o 2 9 4 6 0o2 9 5 3 902 9 6 2 802 9 7 3 802 9 8 6 803 0 0 1 8 l7 503 2 1 5 50 3 2 1 6 4o 3 2 1 9 3o3 2 2 4 003 2 3 0 603 2 3 9 00 3 2 4 9 403 2 6 1 70 3 2 7 5 8 l8 0 0 3 4 9 2 90 3 4 0 3 803 4 9 6 403 5 0 0 903 5 0 7 10 3 5 1 5 l0 3 5 2 4 90 3 5 3 6 503 5 4 9 9 l8 5o 3 7 6 9 4o3 7 7 0 3o3 7 7 2 803 7 7 7 003 7 8 2 9 o3 7 9 0 5o 3 7 9 9 8o3 8 1 0 8o3 8 2 3 4 1 0 004 0 4 4 7 0 ，4 0 4 5 5 04 0 4 7 9 0 4 0 5 1 904 n 5 7 504 0 6 4 704 0 7 3 504 0 8 3 904 0 9 5 9 l9 5o 4 3 1 8 3o 4 3 1 9 104 3 2 1 30 4 3 2 5 l0 4 3 3 0 4 0 4 3 3 7 30 4 3 4 5 604 3 5 5 50 4 3 6 6 9 20 0 0 4 5 8 9 904 5 9 0 60 4 5 9 2 80 4 5 9 6 404 6 0 1 40 4 6 0 7 90 4 6 1 5 90 4 6 2 5 2o 4 6 3 6 l 由于篇幅限制，我们只取了部分数据，如将全部数据列出，将会看到更好的效 果。在表1 中，第一行和第一列分别为一般正态分布( p ，口2 ) 的卢和a 取值。其中 卢的取值范围为o o o o 1 6 ，间隔为o 0 2 ；口的取值范围为o 5 0 一2 o o ，间隔为 o 0 5 。其余中间的数值即为标准正态分布p = ( o ，1 ) 与一般正态分布q = ( m 0 2 ) 9 的互熵( p l l q ) 拟合值。通过表1 我们可以看到，当so 0 1 时，有卢5o 1 0 ，而 o _ 9 0 口 11 0 。这就是说，当接近于o ，而口接近于1 o ，即分布( p ，矿) 与 ( o ，1 ) 很接近时，它们的互熵拟合值会很小。也就是说，我们把互熵作为衡量两个 不同分布之间“差异度”的结论是正确的，我们的基于最小熵原理的e m 算法是有 意义的。 从这里我们可以看出，数据分布的拟合问题也可看作一种特殊的参数估计问 题，只是它与最大似然估计、b a y e s 估计的优化准则不同。最大似然估计、b a y e s 估计的优化准则是使带参数的条件概率达到最大，而数据分布的拟合问题是使互熵 为最小。数据分布的拟合问题同样也可采用e m 算法的思路与步骤，而且它的优化 算法更加直接，它不必设置新的参数变量。在本文中我们给出了它的递推算法，并 证明了它的收敛性。 下面的论述中，我们就用最小熵原理作为依据进行e m 算法分析。 4 分布拟合的e m 算法 4 1e m 算法的一般计算步骤 在( 3 1 ) 的表达式中，我们所讨论的混合分布实际上是由二组参数给定，那 么这里的e m 算法就是在一组参数给定的条件下，求另一组参数的最优解。我们赋 予其最小熵原理的优化准则，使传统的e m 算法有了新的意义，它的递推可以归结 为； e 算法：在口给定的条件下，求a 使k ( p l l q d 目) 为最小 m 算法：在a 给定的条件下，求自使k ( p i l 吼口) 为最小。 显然，当其中一个参数给定时，可由反复使用e 、m 算法实现迭代运算，从而 当结果趋于稳定时，求得最终解，即求得使k ( p i l d ) 为最小的最优参数目和丘。 4 2e 算法的解 以下定理在非常一般的条件下给出e 算法求解的递推计算公式 定理1 如果p 是一固定的概率分布，q 。每是由( 3 1 ) 式所给定的混合分布， 那么当目固定时，a 的最优解满足方程组： p ( z ) 差如乩江l ，2 ，k ( 4 1 ) z 5 、 如果a 是为( 3 2 ) 式所给定的向量，取 小啦厶出) 羔如，江1 ，2 ，t ( 4 2 ) 1 n 那么必有：k ( p q n 口) k ( p | | q i ，d ) 成互。 证明( 1 ) 我们先证( 4 1 ) 式。由极值理论可构造l a g r a n g e 函数 l 忸) = ( p 1 l q d ，日) 十a ， 两端对a 。求偏导得： 差= 一厶出，罴出+ - 8 q | j x “q & 那么它的最小解应满足：差= o ，从而得到方程组： 厶出) 老如。_ o ，江，n 将方程组( 4 4 ) 的左边乘啦并求和，可得到 妻啦厶p c z ，嚣如一塞啦x = 。， 即为 厶出，毪出一。， 因此 = l 成立，( 4 1 ) 式得证 ( 4 3 1 ( 4 4 ) ( 2 ) 由( 4 2 ) 定义的甜满足条件( 3 2 ) 因为这时n ：o 是显然的，而 娄n ：= 塞啦厶p c 圳。s 薏如 n 净n l ，p ( z ) l o g 差如 i = lo = 1 1 0 ，f = 厶耋如，等如= 厶出肛 因此a 也是一个混合分布的比例分布向量 ( 3 ) 为证k ( p | | q 刮口) k ( p 1 | q d ，5 ) 成立，我们只要证= k ( p i l q 丘，口) o 就可，这时把( 4 2 ) 的甜代入耳( p | i q 弘口) 中，就可得到 = ：p ( z ) l o s2 措如= ! p ( z ) l 。s 妻a 。 i ( z ) 】d z ， 其中岱( z ) = 吼，民( z ) ，而记 虻厶掣如“= 格， j 爿 q 【z j 。 口【茹j 及q ( z ) = 肇l 啦吼( z ) k ( p ll q 甜口) ( 4 5 ) 因为在本证明的( 2 ) 中我们已经得到叁l 啦= 1 成立，那么由凸函数的j e n s e n 不等式与( 4 5 ) 式得到： 蚤“如厶p ( 。) 1 0 9 毹( z ) 出 46 对( 4 6 ) 式右边的积分值，由对数函数的凸性与n ：的定义即可得到 厶p ( z ) l o s ( 。) 1 0 9 厶p ( z 减( z ) 酬= l o g 挈厶p ( 。) 器d z l = 1 。s 警， 由( 4 6 ) 式与互熵的性质得到 塞a 如s 鲁。 a 如g 熹o l = l 。 成立，此即定理的第二个结论成立。定理得证。 4 3m 算法的解 我们以下讨论m 算法的求解问题，对此问题我们限制在指数分布的情形讨论 一隆山 i ， 为指数分布，其中良= ( 口印，巩山，；) 为该指数分布的参数集，而妒( 玩) 是概率分 布g l ，巩( ) 的归一化系数，使厶吼，巩( 。) 如= l 那么有， e x p m 玩) 】2 六8 x p ( 蚤巩，一) 如 ( 4 8 ) 如果q ( z ) = 坠1n 。q i ，目。( z ) ，那么q ( z ) 的参数集为： 画，百 = ( n 1 ，一，) ；( 口l ，1 ，日1 ，。) ，一，( 8 k ，1 ，一，口k ，“) ) ( 4 9 ) 为在丘固定的条件下求k ( p 【| 5 ) 的最小值问题，我们有以下讨论。 ( 1 ) 为求k ( p | | 吼口) 的最小值，我们先求出 筹一厶貉掣如a 巩，j 6 ( z )a 巩j 。 令其为零，我们得到方程组： 厶器掣如地川，。， ，z ，一，m 埘 的求解问题。 ( 2 ) 利用指数分布的定义，得到 掣瑚p 因此方程组( 4 1 0 ) 受力： 厶器水胪一筹肛。 即 貉一厶拳掣 由这个方程组我们可以得到 a 妒( 玩)如i i 簧b 吼，凰o ) 触， 厶老耥吼，吼( z ) 由( 4 1 ) 式，我们得到 筹= 怕，既j - 1 1 2 ，待1 1 2 ，b ，( 41 1 ) 其中， ( 西，国：凡p ( z ) ；i 粥d 文我们称之为混合指数分布的j 阶混合矩。 ( 3 ) 由( 4 8 ) 式可得到( 4 1 1 ) 左边的值为： 掣= e x p ( 叫鳓t 瑶“氓 ( 41 2 ) 其中，弼，。( 或) = 厶吼，巩( z ) 出，我们称之为指数分布吼，最( z ) 的j 阶矩。这时上述方 程组( 4 1 1 ) 变为： ；i ( 玩) = e x p ( 妒( 玩) ) i ( a ，百) ， j = 1 ，2 ，t ，n ，i = l ，2 ，一，后， ( 4 1 3 ) ( 4 ) 因为如，醒，磕；都是a ，目的已知函数，当丘固定时，方程组( 4 1 3 ) 就是普 通的函数方程。m 算法就可归结为方程组( 4 1 3 ) 的求解问题，我们可用数值解的 方法得到( 4 1 3 ) 的解。 如果利用妒( 玩) 函数的定义，对( 4 1 2 ) 左边的微分计算还可简化，我们这里不 作详细讨论。 4 4e m 算法的递推计算 由以上讨论，我们就可得到分布拟合的e m 算法的递推计算算法，计算步骤为 1 3 ( 1 ) 取d ( o ) ：( 1 ，1 肛，i ) ( 即均匀分布) 为a 的初始分布。取a = 哥o j 时解方程组( 4 ，1 3 ) ，所得的解记为口( “ f 2 ) 当目：5 ( ，画：a ( o ) 时，由( 4 2 ) 式计算得到的舀记为a 【”。 ( 3 ) 如此循环，由已知的a ( ) 解方程组( 4 1 3 ) 得5 ( 蚪“，再由已知的弘+ 1 ) 计算( 4 2 ) 得a ( ) 。这样得到一系列的： a ( m ，口( ”，压( “，目( ”，a ( ”，d ( 引，。如记 k ( s ；z ) = k ( p | j q 。( 。) ( 。) ) ，那么总有 k ( o ；1 ) k ( 1 ；1 ) k ( 1 ；2 ) k ( 2 ；2 ) k ( 2 ；3 ) ，o ， ( 4 1 4 ) 成立，因此当_ o 。时，k t ) 与拟t + 1 ) 的极限必存在且相等。这时的循环运 算取到耳( t ；t ) 或k ( t ；+ 1 ) 的取值稳定为止。 5 蛋白质空间结构数据分布的拟合计算 5 1 蛋白质空间结构研究情况 长期以来，蛋白质的研究一直在众多科学家尤其是医学家、生物学家和化学家 中进行，也有一系列辉煌的成就被获得但另方面，随着蛋白质研究的深入，人 们发现对蛋白质认识的谜团却越来越多，问题也变得更加复杂例如：蛋白质的结 构形态的成因问题；蛋白质的结构形态和功能的关系问题；从d n a 到蛋白质的演 化过程中的因果关系问题；一个典型细胞所含的1 0 万多种蛋白质的功能、相互作 用、形成的机理与变化规律等打开这些谜团正是生命科学研究和发展的关键 从伊卡斯( y c a s ) 和盖莫( g a n m w ) 的早期研究开始，统计分析在蛋白质序 列和进化研究中一直起着很重要的作用蛋白质序列数据既可以在不同物种中进行 分析，也可以从特定生物体的角度加以研究蛋白质结构数据库的建立将为蛋白质 结构的定量化深入研究奠定基础。在本文中我们重点使用p d b 数据库，p d b 数据 库给出了蛋白质各原子空间坐标位置的结构数据，我们把这些数据看作蛋白质结构 的原始数据由这些数据可以确定在不同蛋白质中各种原子的空间位置，利用数据 分布的拟合就可得到这些原子空间结构( 如不同原子的距离，转角或平面角等) 的 分布特征( 如分布类型，分布参数，拟合度等) 。 蛋白质空间结构数据的类型很多，如p d b 0 4 版数据库给出了2 0 ，0 0 0 多种蛋 白质各原子的空间位置数据，且每天都有大量的新数据在产生。本文中所使用的数 据均来自p d b 0 4 版( 见f 10 ) 。在生物信息学中知道，蛋白质为生物高分子物质之 一，具有三维空间结构，因而执行复杂的生物学功能。蛋白质的空间结构形态与蛋 白质的功能有密切关系，蛋白质的功能主要由其空间结构决定。然而本文不打算就 此专题展开详细的讨论。我们的目的是将上述数据分布的拟合理论在蛋自质空间结 构研究中应用，从而达到对蛋白质空间结构数据的透彻分析。 1 4 5 2 蛋白质空间结构概述 众所周知，蛋白质是生命物质的基础，由一系列不同的氨基酸排列组成，并具 有一定的空问形态，形成它所特有的功能。目前已知的氨基酸超过l o o 种以上，而 常见的只有2 0 种，它们分别是：丙氨酸a l a 、精氨酸a r g 、天冬酰胺a s n 、天冬氨 酸a s p 、半光氨酸c y s 、谷氨酰胺g l n 、谷氨酸g l u 、甘氨酸g l y 、组氨酸h i s 、 异亮氨酸i i e 、亮氨酸l e u 、赖氨酸l y s 、甲硫氨酸m e t 、苯丙氨酸p h e 、脯氨酸 p r 0 、丝氨酸s e r 、苏氨酸t h e 、色氨酸n p 、酪氨酸t ”和缬氨酸v a l 。它们都 是n 一氨基酸，有着相同的化学结构式，如下图： h i r c c o o h i n h 2 图1 氨基酸的化学结构式 其中，r 是氨基酸的侧链，它们是氨基酸中不参与肽键形成，而赋予氨基酸 独特性的部分( 比如亲水和疏水，带电和不带电，有无极性等) 。由2 0 种不同的侧 链，形成2 0 种不同的氨基酸 在这2 0 种氨基酸中，有3 种氨基酸比较特殊它们分别是：甘氨酸( g l y ) 、 脯氨酸( p r o ) 和半胱氨酸( c y s ) 。甘氨酸是唯一个没有侧链的氨基酸，因此它 既不能和其他残基的侧链相互作用，也不能产生任何位阻现象；脯氨酸是一个亚氨 基酸，它的n 原子在一个苯环当中，这直接导致它有一些特殊的性质，比如脯氨酸 很少出现在一螺旋中；半胱氨酸中有一个s 原子，它可以和另外一个半膀氨酸形 成s s ( 二硫键) ，对蛋白质的空间结构，特别是远程折叠，有着很大的影响。 本文关于蛋白质空间结构分析的理论是基于沈世镒教授提出的三角形拼接带理 论，因此，我们先简单介绍一下这一理论 在2 0 种常用的氨基酸排列中，它们的主链由n 原子与二个c 原子交替排列而 成，在生物学中把第一个c 原子称为c - a 原子，我们记之为a 原子，因此蛋白质 主链是由n 、a 、c 三原子交替排列组成。我们记之为： z = ( z l ，忍，磊n ) = ( ( l ，a 1 ，e 1 ) ，( 2 ，a 2 ，岛) ，( ，g ) ) ，( 5 1 ) 其中n 为蛋白质的长度( 含氨基酸的个数) ，蟊一。= m ，z 3 。：a 。，缸：c ! i 由这 些原子点排列构成一个三角形带( 见图2 ) ，我们记之为： 。= ( 磊，五+ i ，五+ 2 ) ， = 1 ，2 ，3 n 一2 ，( 5 2 ) 1 5 其中( a ，b ，g ) 表示以a ，b ，g 为顶点所构成的三角形。我们记 r l2 f 魁a zf r 22 f 鱼g7 32 fg 儆+ lf ( 5 3 ) r 4 = l 他g lr 5 = 1 a m + 1r 6 = i g a 计1 其中la bl 表示线段a b 的长度。我们还可记妒1 ，币2 ，妒3 分别为三角形( ( 批，a ，g ) ， ( a ，g ，m + 1 ) ，( g ，m + l ，a + 1 ) ，( ( m + 1 ，a 州，g + 1 ) 之间的夹角( 二面角) 。图一2 中 的b 原子为c b 原子，它是氨基酸主链与侧链连接的原子，对于我们着手研究侧 链结构的统计特性有着重要的作用 我们称钆，强，妒，咖，妒3 这些参数为蛋白质空间结构参数，由p d b 数据库可 以得到在不同蛋白质与氨基酸中的这些参数，利用本文的数据分布拟合就可得到它 们的分布结构。 b 2 a 3 n l r 4 c l r 6 a 2 豳一2 。蛋白质主链的三角形拼接带与结构参数图 5 3 蛋白质空间结构参数的分布拟合问题 在上文中我们已经说明，利用p d b 数据库可以得到在不同蛋白质与氨基酸中 的各参数的值，这样就可对它们进行分布拟合，本文中有关的讨论如下； ( 1 ) 由p d b 数据库可以得到在不同蛋白质与氨基酸中各参数的值，我们记之 为： r ”，i = l ，6 ，j = l ，2 ， ( 5 4 ) 由此很快可以得到它们的均值与方差，它们是： m = ：毋2 ：( 咱) 2 ， ， n 1 而记吼= a 为n 的标准差。 利用p d b 数据库可以得到r 一一，r 6 的均值、方差与标准差的值分别如下表所 示： 1 6 表2 蛋白质主链结构参数的统计特征数据表 ”127 37 45”6妒1母2妒3 均值( p ) 14 9 0 3 01 2 9 0 8 214 6 3 9 824 3 8 9 924 3 9 8 324 4 6 7 23 7 6 0 7 93 0 6 4 7 04 5 0 6 9 3 l 方差( a 2 ) o o o l 2 0o0 0 1 6 1oo 0 0 2 2 o o o l 0 5 0o 0 0 9 5 o0 0 3 0 8 3 5 3 ：；6 1 o ，0 3 4 0 5o0 7 9 3 6 标准差( 们 00 3 5 9 200 4 0 1 800 1 4 8 700 3 2 3 7o0 3 0 8 200 5 5 4 718 7 9 7 901 8 4 5 209 8 9 6 3 1 2 ) 表2 中均值的单位为埃，那么由表2 可以看到参数，的分布是比 较稳定的，从而知道蛋白质主链的各原子间距离是比较稳定的。又由它们的分布特 征，我们可以选择l a p