（应用数学专业论文）基于面积不变量的生物序列相似性分析.pdf

大连理工大学硕士学位论文 摘要 随着一些微生物基因组、人类基因组、拟南芥基因组和水稻基因组全序列测定项 目的完成和快速进展，以及各种生物的基因和蛋白序列的研究，产生了越来越多的庞 大的分子序列数据。对其进行科学的分析、处理和保存推动了分子生物学和数学以及 计算机科学的结合，近几年，计算分子生物学已成为生命科学中异常活跃的一个研究 领域。计算分子生物学作为现代信息科学、计算机科学、生命科学、数学、统计学、 物理学、化学等很多学科相互渗透形成的一门崭新的交叉学科，主要是研究分子生物 学与基因和蛋白质序列有关的复杂计算问题。本文主要介绍了d n a 序列分析中的图形 表示方法以及以d n a 序列为基础的种系树的构造。主要研究内容可以概括如下： 本文在图形表示的基础上提出了一种刻画d n a 序列相似性新的指标，即曲线和x 坐标轴围成面积的平均值。并且以1 1 种物种的卢一球蛋白基因的第一个外显子编码序 列为例，利用该方法分析了他们之间的相似性以及物种进化系统发生树的构造。这种 方法不需要复杂的比对，并且具有准确性高，计算简单等优点。 关键词：d n a 序列；比对；图形表示；序列分析；不变量方法 基于面积不变量的生物序列相似性分析 a n a l y z i n gs i m i l a r i t yo fb i o l o g i c a ls e q u e n c eb a s e do n a r e ai n v ar i a l l t a b s t r a c t b a s e do nn l ec o m p l e t e n e 鹤o fg e n o m es e q u e n c i i 培p r o j e c t so f 址l eh l l l n a n ，a r a b i d o p s i st h 址i 舡 n 8 ，m c ea n dt h er e 8 e a r c ho np r o t e i n8 e q u e n c 鹪，m o r e 钳l dm o r em 0 1 e c u l a rs e q u e n c 瞄d a t ah a 、r e b e e ng e n e r a t e d t h en i e e dt oa n a l y z e ，p r o c e s sa n ds t o r et h e s ed a t ai si n t e g r a t i n gt h em a t h - e m a t i c 8 眦dc o m p u t e r8 c i e n c 稍i n t o 七h em o l e c u l a rb i o l o g y t 1 1 i 8n 俄姐h 够c r e a t e dai l e wi n t e r d i 8 c i p l i n 毗yf i e l dc o m p 0 8 e do fi n f b r m a t i o ns c i e n c e ，c o m p u t e r8 c i e n c e ，l i f es c i e n c e s ，m a n l e m a t i c s ，8 t a t i s t i c s ，p l l y s i c s ，c h e m i s t 珂a n d f o r t h ，w h i c l li 8c 时l e dc o m p u t a t i o n a lm o l e c l l l 盯b i o l o g y c o m p u t a t i o n a lm o l e c u l 缸b i o l o 醪i 8m a i l l l yd e 甜w i t hc o m p l e xc o m p u t a t i o i l 8i n v o l v i n gg e n e 8 e q u e n c e s ，p r o t e i n8 e q u e n c e sb ym a t h e m a t i c 8a n dc o m p u t e rs c i e n c e t 1 1 i sd i s s e r t a t i o nm a i n l y i n t r o d u c et h e8 i m i l a n t ya n a l l y s i so fb i 0 1 0 百c a l q u e n c e 8a n dt l ec o l l 8 t r u c t i o no fp h y l o g e i l e t i c t r e e 8 t h em a i nc o i l t e i l t so ft h i st h e s i sc a nb es u 加m a r i z e da sf 0 l l o w 8 ： i i lt 1 1 i sp a p e r ，b a u s e do nt h e 铲a p h i c a l lr 印r e s e n t a t i o 璐o fd n a 8 e q v e n c e s w ep r o p o s e dan e w i l l 、阻r i a n tt oc h a r a c t 砸z et b es i m i l a r i t yo fd n as e q u e n c e ，n 锄e l yt h ea v e r a g ea r e ab yo c c u p i e d b yc 砒v eo fd n as e q u e n c ea n dt h exa 耐s t h e nw et a k et h e1 1k i n d so fs p e c i e s t h ef i r s tp 9 1 0 b i na sa 肛e x a m p l e ，a n de m p l o y et h em e t h o dt oa n a l y z en l es i m i l 嘶t yo ft h e ma n dc o n s t r u c t t h e i rp h y l o g e n e t i ct r e e ss u c c e s s f l l l l y t h em e t h o dd o e 8n o tr e q u i r es e q u e n c ea u g i u l l e i l ta n di sv e r y s i m p l ea n dh a sm g hv e r a c i t y k e y w o r d s ： d n a s e q u e n c e s ；a l i g n m e n t ；g r a p h i c a lr e p r e s e n 性l t i o n ；s e q u e n c e sa n a l y s i s ；洒v a r i a n 七m e t h o d i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文申不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或其他单位的学位或证书所使用过的材料。与我一同工作的同志对 本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 歹口形6 而 大连理工大学学位论文版权使用授权书 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学 位论文。 作者签名： 噎 争 翩签名：幺丝 大连理工大学硕士学位论文 1引言 本章介绍了生物序列研究的背景、理论意义及应用价值、生物序列的图形表示研 究概况以生物序列的比较分析为主题，介绍了比对和图形表示在计算分子生物学中 的广泛应用，同时列出本文取得的主要结果。 1 1 生物序列研究的背景、理论意义及应用价值 随着人类基因组测序计划的完成，人们的研究重点由测序转向功能基因组的研 究。同样，生物信息学也经历了由最初主要将基因组测序计划完成的序列数据通过数 据库进行存储，到有效利用包括生物大分子的三维结构、代谢途径和基因表达等各类 数据的发展过程。现在和将来，科学家们将着重于研究d n a 序列信息，蛋白质结构信 息，以及它们之间的相互作用。破译每一水平的生物信息提出了与基因或蛋白质有关 的统计和组合数问题。生物信息的急剧增长也带来了对计算机科学的挑战。为此，计 算分子生物学和生物信息学便应运而生 生物信息学大量地在生物学中引入了数学模型，它标志着生物学已经从实验科学 向理论学科转变。对于生物学本身而言，这就是一次从量变到质变的飞跃。在生物信 息学形成以前。一切的生物学理论的发展都是通过大量的实验证据所得到的经典理 论，然而生物信息学的加入之后，生物学理论的研究开始用于指导、验证试验生物 学。这将会使得试验生物学的目的更加明确，并且也将会大大缩短试验周期。 生物信息学的产生将生物学、信息学、数学、计算机科学、物理学等多门学科有 机的整合为一个新兴学科，这一学科领域的建设必然会推动上述诸多学科的进一步发 展。与此同时，在生物信息学建设的过程中，又以此为基础萌生出一系列分支科学， 如d n a 计算等。所有的这一切，其最直接的意义便是给各个领域带来了无限的商机， 孕育了一个美好的市场。另一方面，伴随生物信息学的发展，人类必将揭示更多的生 命活动本质规律，其中当然会有很多是与人类自身健康、疾病、衰老等相关的生物信 息，而它们的发展必然导致新药物的设计与研发周期大幅度变短以及基因治疗的最终 实现，从而彻底地改变人类自身的命运，这无疑是人类文明的又一次飞跃。当然，在 这一过程中产生的巨大经济效益是现在无法估量的。生物信息学主要是研究生物信 息的采集、处理、存储、传播、分析和解释等方面内容的一门学科。它利用生物学、 计算机科学和信息技术分析大量而复杂的生物数据，揭示其所蕴涵的生物学意义。具 基于面积不变量的生物序列相似性分析 体地说，生物信息学是把基因组d n a 序列信息分析作为源头，在获得蛋白质编码区的 信息后进行蛋白质空间结构模拟和预测，最后依据特定蛋白质的功能进行必要的药物 设计 计算分子生物学不仅是生物信息学的前身，更是生物信息学的核心部分。可以 说，对生物信息学的研究中数学技术发挥着重要作用。随着生物信息学算法的不断完 善，已能进行生物序列家族或同源性分析；进行生物序列的聚类，建立进化树并确定 生物序列间的进化关系；进行代谢途径相关基因的同源性分析，以及获取其它生物代 谢途径的相关信息等。其中生物序列的比较是生物信息学中最基本的问题，因为对于 d n a 序列，即使我们考虑他的一个很短的片断。我们也不可能直接得出它表示的对象 所具有的全部信息，如果我们比较不同的生物序列就有可能得到某些重要信息，然而 这个问题非常复杂，至今还有许多未解决的问题。总之，对生物序列进行分析和比较 是生物信息学的最基本也是最重要的课题之一，同时对生命科学的研究具有深远的意 义1 1 9 】 、 1 2 生物序列比较的研究概况 目前生物序列比较主要有两种方法：序列比对算法和矩阵不变量方法。 序列比对算法：序列比对又叫序列联配，它是运用某种特定的数学模型或算法 找出鼹个或多个序列之间的最大匹配碱基或残基数，对比算法的结果在很大程度上 反映了序列之间的相似程度以及它们的生物学特征f 1 0 l 。根据比对的序列数目多少可 分为两两序列比对( p a i r w i 8 es e q u e n c ea l i g n m e n t ) 和多序列比对( 瑚【u l t i p l e8 e q u e n c e a u g n m e n t ) ，根据比对的范围可分为全局比对( 舀0 b a l la l i g i l m e n t ) 和局部比对( 1 0 c 越 a l i g n m e n t ) 。 目前，进行序列比对的算法很多，而这些算法大多基于运筹学中的动态规划思 想，只是在其基础上进行了不同程度的改进而己。应用最为广泛的动态规划算法有 n e e d l e m 姐w h n s c h 算法f 1 1 1 和s m i t h w a t e r m a n f l 2 1 算法。在此基础上产生的数据库收 索程序家族有b l a s t f l 3 1 和f a s t a f l 4 1 。动态规划算法f 1 5 1 是由n e e d l e m a n 和w h j l s c h 在1 9 7 0 年提出的，最初用于求两个序列的最佳对准，其不但可用于全序列对准，而 且还用于局部序列对准。对于双重全序列对准情况，该方法的关键是设计一个二维矩 阵，该矩阵的两个轴就是要对准的两个序列。算法的第一步是根据替代矩阵在该矩阵 的每一个位置上赋予一个数值，得到一个原始矩阵然后从该矩阵的右下角( 对应于 序列的c 端) 开始，把该矩阵中的数值按如下规定逐行相加得到一个“转化矩阵”： 把下一行各单元中的最大允许值加到该单元左边的上一行及上一列的所有单元中。转 化完后，在追踪时，从左下角( 相当于序列的n 端) 开始向下向右追踪，不允许垂直 向下或向左，这样就得到了最高积分路径。该路径自动离开矩阵对角线位置意味着在 某一序列中要引入一个空位。由于空位的引入不代表进化事件，所以要用对其罚分的 方法来调整路径。 2 大连理工大学硕士学位论文 s 血t h 和w a t e r m a n 【1 6 1 给出了n e e d l e m a n w h 璐c h 算法的数学证明，并将其扩展 成一个包含改正的记分系统，提出了s m i t h w 玑e r m a n 算法。这两种方法密切相关， 其主要差异在于n e e d l e m a n w u n s c h 算法查找的是序列间的全局相似性，而s m i 乞h w - a t e m a n 算法查找的是局部相似性。s m i t h w a t e r m a n 算法得出的不对结果可能只覆 盖了每一条序列的一小部分( 局部) ：而n e e d l e m a n w r u i l s c h 算法却试图尽可能地覆 盖整条序列，从某条序列的最左端开始到最右端结束。因为真正的生物学序列往往不 是在全长上相似，丽是局部的相似，所以s 戚t h w a t e r m a n 算法使用更为广泛。 另外，在进行序列比对时，有两个方面问题直接影响相似性分值：空位罚分和取 代矩阵。空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有合适的理论 模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观特色。粗 糙的比对方法仅仅用相同不同来描述两个残基的关系，显然这种方法无法描述碱基或 残基取代对结构和功能的不同影响效果。为了提高敏感性和生物学意义，针对不同的 研究目标和对象应该构建适宜的取代矩阵，目前国际上通用的取代矩阵有p a m f l7 l 和 b l o s u m 【1 8 】 动态规划方法将一个复杂的问题分解为性质相似的子问题，并从一组具有高分值 的比对中找出优化的结果。但是这种方法十分耗时。随着序列数量的增加，序列比对 的算法复杂性按指数规律增长。降低算法复杂性，是现今序列比对的一个重要研究方 向为此，产生了不少很有实用价值的序列比对算法。这些方法的特点是利用启发式 算法降低算法复杂度，以获得一个比较满意但并不一定最优的比对结果。有的算法还 将动态规划和启发式算法结合起来。 不变量法：利用基于矩阵不变量的方法来比较生物序列，不同于以前的方法去直 接比较序列，而是去考虑这些序列的不变量。这些不变量是从序列所对应的矩阵中提 取出来，即它把初始的生物序列转化数值序列。因此这种方法的关键在于如何构造合 适的矩阵来表示序列。目前，常用的构造方法一般有序列构造法，图形构造法和矩阵 构造法。 在这些方法中，比较著名的是图形表示方法。图形表示方法最早是在1 9 8 3 年由 e h a n l o r i 和j r 璐k i n 提出的【1 9 卜它的基本思想是建立映射，将碱基( 或氨基酸) 映成平面或空间的点，然后连接这些点得到空间图形。图形表示方法最大的优点就是 可视化。克服了以往人们观察一个较长的序列不能留下总体深刻的印象的缺点。近几 年它发展也比较快，第二章我们将具体介绍一下图形表示的一些方法。自从1 9 8 3 年由 e h 锄o r i 和j r 1 l s k i n 提出了d n a 序列图形表示的思想一一将d n a 序列表示为一条平 面或空间中的曲线，把d n a 序列的研究带进了一个新的研究领域。自此国内外不少化 学专家如m r a l l d i c ，a n a n d y 以及国内郭晓峰、廖波和王天明等人【2 m 3 7 】提出了生物 序列的众多的不同维的图形表示。m r n d i c 等人还基于他们的图形表示，将d n a 序 列转化为矩阵等数学表示，进一步用矩阵不变量来研究d n a 序列，取得了很好的结 果生物序列的图形表示主要应用在序列相似性分析和基因识别等方面 2 m 3 7 】。我国著 名理论物理专家张春霆院士也提出了一种d n a 序列的几何图形表示一z 曲线，z 曲线是 3 基于面积不变量的生物序列相似性分析 表示d n a 序列的一个等价的三维空间曲线 3 8 】通过对z 曲线的研究来对基因组序列 进行研究是一种几何学的途径，这种新颖的学术观点为引进更多的数学工具来分析生 物序列提供了广阔的前景。原则上说，基因组中的许多问题都可以通过这种途径加以 解决，这种独树一帜别开生面的研究思路已经得到国内外学术界的普遍好评和认可， 越来越多的学者，加入到对z 曲线研究的行列中来。可以预见，用几何学方法研究基 因组将会有一个广阔的发展空问。d n a 是携带生物遗传信息的主要大分子但r n a 是 大部分病毒的遗传物质，并且r n a 还参与蛋白质的合成、与细胞分化、代谢、记忆的 储存等有重要关系正是由于r n a 具有的这些特殊属性，目前越来越多的人开始关注 r n a ，最近，廖波和王天明鉴于现有比较r n a 二级结构相似性的算法受不带假结的 限制，首次提出用几何图形表示r n a 二级结构f 3 9 - 4 0 】根据r n a 二级结构组成和核 昔酸a ，c ，g ，u 的化学结构分类，他们给出了r n a 二级结构的3 d 图形表示和6 d 图形表示法，并利用这些表示的数据特征来比较r n a 二级结构的相似性。以上这些表 示都还有各自的缺陷。主要表现在以下几点： ( 1 ) 有退化现象；( 2 ) 对完整序列而 言，使用的数学不变量计算太复杂，有的甚至还没有算法解决；( 3 ) 缺乏表征生物序 列特征的更多的灵敏度足够好的数学不变量以及生物序列( d n a 序列、r n a 序列和 蛋白质序列) 的图形表示的应用研究还很少。 1 3 本文的主要工作 计算分子生物学的主要课题有：序列组合、序列分析、生物信息资料库、基因认 定、种族树的构建以及结构预测等，从计算理论的角度来讲，它们都是难处理的；换 句话讲，我们并不知道是否存在有效的算法去解决这些间题目前的研究集中在设计 好的近似算法或概率算法；这些算法虽然并不能对有关间题的每一个实例都能求出好 的解，但对大多数实例却行之有效。本文对生物序列图形表示方法的不变量进行了探 索，提出用四水平线方法中的曲线和x 轴围成的平均面积来代替原来的矩阵不变量作 为新的不变量。利用这一新的不变量来比较和分析生物序列，并且构造系统进化树。 本文的主要内容如下： 第二章，系统详细地介绍d n a 序列的比对方法和在介绍矩阵不变量方法在序列相 似性分析之前我们介绍了各种几何图形表示方法。 第三章，给出了d n a 序列相似性分析的一种新方法：利用己有的d n a 序列的图 形表示寻求新的数值特征，即曲线与x 轴围成的面积的平均值，利用这些数值特征来 比较d n a 序列的相似性。利用这些新的数值特征作为d n a 序列的不变量分析了1 1 个 物种的一球蛋白基因的第一个外显子d n a 序列的相似性和非相似性并且构建了这1 l 物种的系统进化树 本文的主要内容是作者近期获得的一些结果，我们希望这些工作能在将来的研究 中探讨数学与生物两大学科的汇合点。由这些内容的讨论看到，许多数学理论与工具 可在分析生物序列领域内应用，这些问题数据丰富，背景明确，将成为研究生命科学 4 大连理工大学硕士学位论文 的有力工具。但由于生物序列结构的复杂性，许多问题远远没有解决，因此继续深入 研究的发展空间巨大。 5 大连理工大学硕士学位论文 2 生物序列的比较方法 本章系统详细地介绍了序列的比对方法和d n a 序列的几何图形表示方法的研究概 况，同时指出了各种方法的优缺点。并且介绍了这些方法在d n a 序列相似性分析的应 用。 2 1引言 在生物信息学中，序列的比较是通过将两个或多个核酸序列或蛋白质序列进行比 对( a h g i 】m e n t ) 。通过比对未知序列与己知序列( 尤其是功能和结构已知的序列) 之 间的相似性得到它们的同源性来预测未知序列的功能。而矩阵不变量方法主要是基于 d n a 序列图形表示的基本思想，首先把d n a 序列表示成一条空间曲线，然后从这些 图形上得到矩阵继而提取矩阵不变量。根据不变量来分析d n a 序列的相似性。下面我 们详细介绍它们 2 2 序列比对 序列的比对主要是研究序列间的优化对应，即用一个距离函数来度量两个序列间 的相似性和非相似性。一般的认为，两个序列间的主要不同是由替换和对换引起的， 所以序列间的优化对应研究被看作是序列的置换或对比( 或者匹配) 。在此我们主要 介绍当前应用最广的序列比对算法，有关序列比对的参考文献和网上的使用工具，在 每一本有关生物信息学的参考书中都有详细的介绍。例如，w a t e 瑚a i l 等。 早期的序列比对是全局的序列比较，但由于蛋白质具有的模块性质，可能由于外 显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描述序列两 两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基的相似性分 数，分数越高则说明两个残基越相似。因此，序列比对问题变成在矩阵里寻找最佳比 对路径。目前最有效的方法是n e e d l e m a n w 曲s c h 动态规划算法f 1 1 】，其指导思想就是 在多级过程的每一级上列出各种可行的局部解，然后按照某些条件舍弃那些肯定不能 得到最优解的局部解。该方法由n e e d l e m a n 和w h 璐c h 于1 9 7 0 年提出，最初用于求两 个序列的最佳比对，其不但可用于全序列比对，而且可用于局部序列比对。对于双重 全序列比对情况，该方法的关键是设计一个二维矩阵，该矩阵的两个轴就是要比对的 7 基于面积不变量的生物序列相似性分析 两个序列。算法的第一步是根据替代矩阵在该矩阵的每一个位置上赋予一定数值，得 到一个原始矩阵。然后从该矩阵的右下角( 对应与序列的c 端) 开始，把该矩阵中的 数值按如下规定逐行相加得到一个“转化矩阵 ：把下一行各单元( c e l l ) 中的最大 允许值加到该单元左边的上一行即上一列的所有单元中。转化完成后，再追踪出最大 积分路线的优化路径，它代表最佳比对。追踪时，从左上角( 相当于序列的n 端) 开始向下向右追踪，不允许垂直向下或向左，这样就得到了最高分路径该路经自动 离开矩阵对角线位置意味着在某一序列中要引入一个空位由于空位的引入不代表进 化事件，所以要用对其罚分的方法来调整路径全序列动态规划算法的缺点是：在一 些局部序列相似性较高而全序列相似性很小的情况下，前者常被后者的平均效应所掩 盖，其同源性不易被检出s m i t h 和w a t e m l a n 通过对n e e d l e m a n - w h n s c h 算法进行修 改，提出了寻找两个被比较序列的“最类似 片段的局部序列比对方法。这种方法和 n e e d l e m a n w 曲s c h 算法的主要区别在于： 1 替代矩阵中必须包含负值；2 转化矩阵中所计算的最小积分值为o ；3 优化路 径可以在积分矩阵的任何一个位置终止，面不是仅仅在最后一行或最后一列终止。 当把动态规划的基本思想推广到多重序列对比时就是所谓的n 维动态规划算 法。n e e d l e m a n w h n s c h 算法可以直接用于三个序列的比对m u r a t a 和g 0 t o h 明确地 确定了同时比较三个残基时的权值是三个残基间两两比较时的权值之和。这个规则可 以被扩展到n 个序列的比对中。即多重序列比对的积分是n 个序列中两两进行双重比 对所得积分之和。对于n 维动态规划算法除去多个很短序列的比对外，三维以上矩阵 所需要的分内存空间和动态优化所需要的时间太长。对于n 个序列的比对其运行时间 是子生物学是在分子水平上d ( 2 n 矧2 。厶) ，即运行时间呈指数增长，这是一个坏 消息例如假设每步需要1 毫微秒( 1 0 亿分之一秒，1 0 - 9 ) ，那么对于长度为1 0 0 的6 个序列的比对，其运行时间为2 6 1 0 0 6 1 0 一，差不多是6 4 0 0 0 s 如果增加两个序列， 其运行时间变为2 6 1 0 9 s 。所以动态规划算法不是很实用。在f a s t a 程序包中可以找 到用动态规划算法进行序列比对的工具l a l i g n ，它能给出多个不相互交叉的最佳比 对结果。 在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和空 位罚分粗糙的比对方法仅仅用相同、不同来描述两个残基的关系，显然这种方 法无法描述残基取代对结构和功能的不同影响效果，比如缬氨酸对异亮氨酸的取 代与谷氨酸对异亮氨酸的取代应该给予不同的打分。因此如果用一个取代矩阵来 描述氨基酸残基两两取代的分值，将会大大提高比对的敏感性和生物学意义虽 然针对不同的研究目标和对象应该构建适宜的取代矩阵，但国际上通用的取代矩 阵有p a m 和b l o s u m 等。它们来源于不同的构建方法和不同的参数选择，包括 p a m 2 5 0 ，b l o s u m 6 2 ，b l o s u m 9 0 ，b l o s u m 3 0 等。对于不同的对象可以采用不同 的取代矩阵以获得更多的消息。例如对同源性较高的序列可以采用b l o s u m 矩阵， 而对同源性较低的序列可以采用b l o s u m 3 0 矩阵。空位罚分是为了补偿插入和缺失对 序列相似性的影响，由子没有合适的理论模型能很好地描述空位问题，因此空位罚分 8 大连理工大学硕士学位论文 缺乏理论依据而更多的带有主观特色。一般的处理方法是用两个罚分值，一个对插入 的第一个空位罚分；另一个对空位的延伸罚分。对于具体的比对问题，采用不同的罚 分方法会取得不同的效果。 2 3d n a 序列的图形表示 2 3 1g 曲线和h - 曲线 1 9 8 3 年，h a 1 0 r i 首先提出表示d n a 序列的图形方法：g 一曲线和h 曲线。g 一 曲线是一种5 维空间表示，其中4 个坐标方向分别为四种核苷酸，另一个方向说 明d n a 序列核苷酸的位置特征，这一方法不能实现可视化。当用两个坐标轴的 四个方向表示四种基( a n w ；c n e ；g s e ；t s w ) ，另一个方向表示d n a 序列 核苷酸的位置时，曲线就变成3 维空间的曲线，这样的曲线被称为h 曲线4 1 1 。 但这种方法要实现最佳可视化效果就需要2 维投影。h 锄o r i 和r u s l 【i n 用h - 曲线 发现，b a c t e r i o p h a g e m l 3 、h - u m a ni m m u l l o d e 矗c i e n c y r u s ( h l v ) 以及e p s t e i nb a r r r u s ( e b v ) 等几种病毒基含量有剧烈变化的区域f 4 2 】。 2 3 2c g r 图 1 9 9 0 年，j e f i e y 最先提出c g r ( c h a o sg r 印h i c a - lp r e 8 e n t a t i o n ) 方法f 4 3 】。这种方 法将序列对应于一张揭示其固有分形结构的图，不同的d n a 序列在图中显示出不同 的模式，从外形上看相似于许多自然现象，如山、云、珊瑚、人脑等等。其几何上的 应用以及处理基因组分析问题的应用己经显示了很好的结果4 4 1 。c g r 图的方法( 见 图1 1 ) 是按照下面的步骤产生的f 4 5 】： 1 将d n a 序列中的a 、g 、t 、c 四种碱基分别放到单位正方形的四个顶点，根 据代表正方形四个项点的碱基的不同排列顺序，可得到不同类型的c g r 图，以a 、t 作为对角线图称为a t r c g r 图。类似的，以a 、g 作为对角线的c g r 图称为a g c g r 图，以a 、c 作为对角线的c g r 图称为a g c g r 图。以a t - c g r 图为例说明其构造 算法； 2 以正方形的中心作为起点，从d n a 序列a t g g c 中取第一个核苷酸a ，连接 中心和顶点a ，用这条线段的中点表示d n a 序列中的第一个核苷酸，如图1 1 ( a ) 所 示； 3 d n a 序列的第二个核苷酸t 则表示为代表前一个核苷酸的点与顶点t 连线的中 点，如图1 1 ( b ) 所示； 4 重复第3 步直到将d n a 序列中最后一个核苷酸表示为正方形中的点。 9 基于面积不变量的生物序列相似性分析 g ( ( d ) 图2 1 ：序列a t g g c 的c g r 图的构造 f i g u r e2 1 ：t h ec o n s t r u c t i o no fc g rt h e q u c e n c ea t g g c 如果在d n a 序列中不存在显著的模式，则c g r 图中的点将会是完全随机分布 的；反之，如果模式存在，例如重复的核苷酸和核苷酸片段，或者是缺失某种核苷酸 或几种核苷酸的组合，那么正方形区域中的点将会有些地方密集，有些地方稀疏，这 在c g r 图中就表现为一定的分形结构。d n a 序列的c g r 图具有如下基本性质： 1 c g r 图中的点与d n a 序列中的核苷酸一一对应，因此c g r 图中的可视模式 对应于d n a 序列的某些固有模式； 2 c g r 图中的点也与d n a 序列的起点到其对应的核苷酸的子序列一一对应； 3 屏幕的清晰度限制了c g r 图的某些细节，然而由于分形结构，图的任一部分都 可以被放大，显示更精细的结构； 4 d n a 序列中的邻近碱基在c g r 图中并不互相靠近( 除非第一点靠近一个碱基 顶点，而序列中的下一个核苷酸是同样的碱基) ，在c g r 图中相互靠近并不意味着在 d n a 序列中也相互靠近，根据性质2 ，c g r 图中的邻近两点也不一定对应于d n a 序 列中的相近子序列； 5 c g r 图所表现出来的可视模式是d n a 序列的整体模式，而不是局部模式，在 某一区域中点的密集或稀疏程度对应于在这个区域里的子序列在整个d n a 序列中的多 或少。 1 0 大连理工大学硕士学位论文 由于d n a 序列的c g r 图表示具有以上性质，因此从c g r 图中提取的特征不仅 真实的反映了d n a 序列的特征，还突出了d n a 序列的整体模式。j e 盘e y 的研究结果 显示，对于图的“d o u b l e - s c o o p ”模式，脊椎动物的c g r 图要多于非脊椎动物，类似 的其它特殊模式的差异也相继被发现，还有的研究小组进行了用于区分d n a 序列的外 旋子( e x o n ) 和内旋子( i n t r o n ) 甚至整个基因的数据试验。 2 3 3 二维曲线表示 1 1 9 8 6 年m a g a t e 8 构造出最早的二维表示【2 0 】，规定+ x 轴单位方向为t ，x 轴方向为a ，+ y 轴方向为c ，一y 轴方向为g 。 2 1 9 9 4 年a n 矗d y 给出的二维表示【3 0 】为：+ x 轴单位方向为c ，x 轴方向为 a ， + y 轴方向为g ，y 轴方向为t 3 1 9 9 5 年p m l e o n g 和s m o r g e n t h a l e r 提出另一种二维表示【4 6 】+ x 轴单位方向 为g ，x 轴方向为a ，+ y 轴方向为c ，y 轴方向为t 。 以上三种情况，均以原点为初始点，每增加一个基就按照其所给出的方向增加一 个单位向量。图2 2 给出了基的定义的图形表示。这三种图形表示的曲线上点的坐标分 别为： ( 2 1 ) 总结：此三种表示是由于四个核苷酸基的任意选择性产生的，可以根据后来的关 于化学上核苷酸基的分类来解释，即：( 1 ) 按照弱、强氢键分类：w = a ，t ) ，s = c ，g ) ； ( 2 ) 按照酮基、氨基分类：m = a ，c ) ，k = g ，t ) ：( 3 ) 按照嘌呤、嘧啶分类：r = _ a ，g ) ， y = _ c ，t ) ；分别对应上面3 个图形关于x 轴方向上的取值。 但其共同的缺点是都有一定程度上的退化( 指图形的交叉、重叠) ，从而导致一 定量的信息丢失。如在g a t e s 的图形表示中：a t 、a t a 、a t a t 、a t a t a 、a t a t a t 的图形表示难以区别。 2 3 4“四水平线”图形表示 r a i l d i c 基于平面上的四条水平线提出了一种2 维表示：将所要讨论的序列以整数 单位点为基点沿x 轴正方向排列开，选择四个基的某种排列方式放置在y 的正方向， 并延伸出四条平行于x 轴的直线，从原点出发，以序列中的基所在的y 轴线与x 基 产生的垂直于x 轴线的交点为图形点，并连接所有相邻的交点，如图2 3 所示【2 2 】。 1 1 a 互 一 一 g q i i = 戤 玑 ，f1l a 正 一 一 g 倪 = = 戤 鼽 ，jl_， a 瓯 一 一丑g = 一一 搦 玑 ，ifl_， 基于面积不变量的生物序列相似性分析 图2 2 ：g a t 钙，n a i l d 弘l n g 的二维表示中基 f i g u r e2 2 ：t h ed e 6 n a t i o no ft h eb a sb ym a g a t 馏，a n a n d y 明dp m l e o n g 优点：完全避免了退化问题，故而不造成信息丢失；方法简便，没有方向选择的任意 性。 图2 3 ：m m d i c 的人的p 一球蛋白第一个外显子前1 0 个基a t g g t g c a c c 的图形表示 f i g u r e2 3 ：n o v e l 擎a p h i c a l 弛p r e s e n t a t i o no ft h e8 e q u e n o ea t g g t g c a c cb y 胁d i c t h er e c 烛西憾 ( d o t 8 ) d e n o t et h eb a 瞄m a k i i l gu pt h e 鼬q u e n 2 3 5 一种紧密的2 维表示 该方法也是由r a n d i c 提出的，他用二进制数来定义核苷酸基：a = 0 0 ，g = 0 l ， c ：1 0 ，t ：1 1 ；将一个序列用2 维图形表示时，以原点为出发点，水平的单位线表示相 1 2 ， o c t 口 c 大连理工大学硕士学位论文 邻基之间的连接，垂直的单位线段表示一个基，如果基的表示中含有代码1 ，则对应 于1 所在的前后，在线段端点上用黑色点表示，如果基的表示含代码o ，则不作任何 改变。最重要的是，该曲线是以原点为中心，作顺时针的转变，而且一个垂直单位线 接连一个水平单位线。人a 一球蛋白第一个外显子序列图形表示如图2 4 所示【2 4 1 。优 点：不仅完全避免了退化、不丢失原序列的信息，而且可以节省表示空间，如一个长 为1 4 0 0 的基序列仅需要4 0 4 0 的平面面积即可。 一o墙- b42o2毒88恤 图2 4 ：人卢一球蛋白第一个外显子序列的图形表示 f i g u r e2 4 ：t h ec o m p 8 u c tf 印h i c 越r 印r e 跎n t a t i o no fh u m a n 卢一酉o b i ne x o n 2 3 6 三维曲线表示 张春霆【3 8 ，4 7 1 以及m r a n d i c 等人f 2 2 】将d n a 序列的四个基看作一个正四面体的 四个顶点，建立一个x y z 坐标系。具体的做法可直接用数学形式描述如下； 1 将d n a 序列中的四个基按照它们的化学结构分类如下：嘌呤r = a ，g ) 和 嘧啶y = c ，t ；氨基m = a ，c 和酮基k = g ，t ) ；弱氢键w = a ，t ) 和强氢键 s = c ，g ) 。 2 建立x y z 坐标系，其中x ，y ，z 轴的正方向分别对应着r ，m ，w 基；它们 的负方向分别对应着y ，k ，s 基。 1 3 8 g o 瑶 r 壤 喀 协 基于面积不变量的生物序列相似性分析 3 画d n a 序列的3 维图形如下：观察d n a 序列从左到右一次一个基，根据观察 到的基所属的集合元素的个数在三维坐标下画出这个序列的3 维几何图形。 显然，对于不同的序列，它们的几何图形也不同，序列和图形之间有一一对应关 系。现考虑一d n a 序列，设它共有n 个碱基，从头开始直到最后，依次考查此序列， 每次只考察一个碱基。为进行定量研究引进直角坐标系，则每一结点的直角坐标可表 为 f ，z n = ( a + g ) 一( c k + 死) 骱= ( 如+ g ) 一( g 竹+ 死) 【= ( 厶+ 死) 一( g + 瓯) ( 2 2 ) 其中，厶，兀，g n 和q 分别是前n 个基的子序列中基a ，。t ，g 和c 的个数。 值得指出的是，这一公式有直接的生化意义另外，z 曲线还具有一一对应性、等步 性、回路性、渐近性、对称性、手性等优良性质，它在分析限制性内切酶对d n a 序列 的识别等方面有重要的应用。 上述的3 维图形表示有很强的数学意义，然而有一个共同的缺陷，即都存在退化 序列，如序列a c g t g t c a 和a c g t g t c a a c g t g t c a 。虽然它们的几何表示应该 是不一样的，然而并不能从它们的图形中表现出来，我们称这种现象为序列的退化。 与之不同，y u a ne ta 1 构建的三维空间表示【4 8 】( 图2 5 所示) ，克服了上述3 维图 形表示的退化现象，采用方法为：让g = 9 1 9 2 鲰表示一条任意的d n a 本原序列， 构造映射v ，映射g 到一个点集 f ( 一1 ，o ， 皿c 肌，= 三：! i 【( o ，1 ，t ) ( 2 3 ) 即：以原点为起始点，每增加一个基，在原有基础上以其定义的单位向量向z 轴 正向延伸。优势在于它不存在上述3 维图形表示的退化现象，而且仅有三种不同的图 形表示，分别对应于四个基的三种不同分类。按照d n a 曲线中点( 代表基) 的坐标所 反映的信息，也可以将已有的图形表示大致分成两类：( 1 ) 坐标反映d n a 序列中某 些核苷酸基的分布。( 2 ) 坐标仅确定位置。另外，还有d n a 序列的1 维表示，这主 要是指使用统计学方法研究单个基、一对基( 1 6 个二元组) 基的三元组( 6 4 种) 等的 频率。 1 4 a a e r = = = = 驮仇优吼 ， 大连理工大学硕士学位论文 图2 5 ：y l l a n 等人给出的人b 一球蛋白第一个外显子序列前l o 个基的图3 d 形表示 f i g u r e2 5 ：t h e3 - dg r a p h i c a lr e p r e n t a t i o n0 ft h e 眙q u e n c ea t g g t g c a c cb yy u 觚e ta l 2 4 不变量法 2 4 1由图形表示提取特征矩阵 对于d n a 原始序列，因序列太长，很难直接从序列本身提取信息。d n a 原始 序列的图形表示提供了解决这个问题的一种方法，它能使得我们更直观的观察。用矩 阵表示d n a 序列的信息从另一个角度来解决这个问题。这一工作最早有m r a j l d i c 等 人【2 3 】提出。具体的做法有下面几种： 1 e 矩阵：其中( i ，j ) 元由曲线上两个基对应点的欧氏距离得到。 2 m m 矩阵：其中( i ，j ) 元由曲线上两个基对应点的欧氏距离与它们之间存在 的单位线段数之比( 即b i l ) 得到 3 l l 矩阵( 也称d d ( d i s t a n c e d i s t a n c e ) 矩阵) ：其中( i ，j ) 元由曲线上两 个基对应点的欧氏距离与它们之间的图论距离( 曲线上两点间的线段长的和) 之比得 到，主对角线元为零，所有元素都小于或等于1 。这种矩阵来源于d n a 原始序列的二 维几何图形表示。假设一个d n a 原始序列的长度为n ，即它有n 个基构成。我们构造 一个死扎阶对称矩阵如下，它的( i ，j ) 项为最f 岛，这里忍，是几何图形中第i 个 点和第j 个点之间的e u c l i d e a n 距离，g 钉是几何图形中第i ，个点和第j 个点之间的图论 意义上的距离。利用这种矩阵的最大特征值可以给出d n a 原始序列的几何图形的折叠 度的一种结构性解释。 1 5 基于面积不变量的