（运筹学与控制论专业论文）生物序列的图形表示及相似性分析.pdf

生物序列的图形表示及相似性分析 摘要 本文内容主要涉及两方面：一方面是生物序列的图形表示，包括d n a 序列 的二维图形表示和四维图形表示以及r n a 二级结构的二维图形表示；另一方面 是在图形表示基础上进行的相似性分析，相似性分析用到的生物序列的数值特征 有商矩阵的正规化最大特征值以及平均几何中心。 本文的主要工作包括以下几个方面： 在第二章，通过把d n a 初始序列划分成一系列密码子，根据遗传密码建立映 射，得到一种新型的非退化的二维图形表示。利用序列对应点的坐标构造商矩阵， 以商矩阵的正规化最大特征值作为序列数值特征，进而对1 1 种物种的卢球蛋白 基因的第一个外显子序列进行相似性分析。得到的相似性矩阵是合理的，并且有 一定进步。 在第三章，改进了已有的四维图形表示。利用d n a 分子中的四种碱基a 、 g 、c 和t 的化学结构分类，给出了d n a 序列的一种新的四维图形表示方法。 在图形表示基础上构造平均几何中心作为序列的数值特征，并利用数值特征给出 了两种度量d n a 序列相似性的方法。 在第四章，用二进制码来表示r n a 二级结构的特征序列中的碱基，把r n a 初始序列转化成二进制编码序列，进一步构造映射并以w o r m 曲线为模板给 出了r n a 二级结构的二维图形表示。利用图形表示上对应点的坐标构造商矩阵， 以商矩阵的正规化最大特征值作为二级结构的数值特征，并对9 种病毒的二级结 构进行相似性分析。 关键词：d n a 序列，r n a 二级结构，商矩阵，正规化最大特征值，相似性。 g r a p h i c a lr e p r e s e n t a t i o no fd n a a n dr n a s e q u e n c e s a n da n a l y s i so fs i m i l a r it yb a s e do nit0 a n a l y s i ss i m i l a r it y1 3 a s e d0 ni t a b s t r a c t t h ep a p e rc o n s i s t s o ft w op a r t s ：t h ef i r s tp a r tc o n c e r n so nt h eg r a p h i c a l r e p r e s e n t a t i o no fd n as e q u e n c e sa n dr n as e c o n d a r ys t r u c t u r e s i ti n c l u d e s2 da n d 4 dg 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 d2 dg r a p h i c 时r e p r e s e n t a t i o no f r n as e c o n d a r ys t r u c t u r e s t h es e c o n d a r yp a r tc o n c e r n so na n a l y s i so fs i m i l a r i t v b a s e do ng 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 dr n as e c o n d a r ys t r u c t u r e s t h en u m e r i c a lc h a r a c t e r i z a t i o n so fd n a s e q u e n c e sa n dr n as e c o n d a r ys t r u c t u r e st h a t a r eu s e di nt h ea n a l y s i so fs i m i l a r i t yi n c l u d en o r m a l i z e dl e a d i n ge i g e n v a l u e so ft h e q u o t i e n tm a t r i c e sa n da v e r a g eg e o m e t r i c a lc e n t e r s t h em a i nc o n t e n t sa r el i s t e da sf o l l o w s ： i nc h a p t e rt w o ，t h ep a p e rd i v i d e sp r i m a r ys e q u e n c e so fd n ai n t oas e r i e so f c o d o n s t h e ng e tam a pa c c o r d i n gg e n e t i cc o d ea n do u t l i n ea2 d g r a p h i c a l r e p r e s e n t a t i o no fd n as e q u e n c e so fn o n d e g e n e r a c y t h ep a p e rc o n s t r u c t sq u o t i e n t m a t r i c e sa n dl e t st h en o r m a l i z e dl e a d i n ge i g e n v a l u e so ft h eq u o t i e n tm a t r i c e sb et h e n u m e r i c a lc h a r a c t e r i z a t i o n so fs e q u e n c e s a tl a s tt h ep a p e rg i v e so u tt h ee x a m i n a t i o n o fs i m i l a r i t i e sa m o n gt h ec o d i n gs e q u e n c e so ft h ep g l o b i ng e n eo f1 1d i f f e r e n t s p e c i e s t h es i m i l a r i t ym a t r i xi sr e a s o n a b l ea n dh a ss o m ea d v a n t a g e i nc h a p t e rt h r e e ，t h ep a p e ri m p r o v e st h ep r e v i o u s4 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 a s e q u e n c e s an e w4 dg r a p h i c a lr e p r e s e n t a t i o ni sp r o p o s e da c c o r d i n gt ot h e c h e m i c a lc l a s s i f i c a t i o n so ff o u rn u c l e o t i d e s ：八gca n dt t h e nc o m p u t et h ea v e r a g e g e o m e t r i c a lc e n t e r so ft h eg r a p h i c a lr e p r e s e n t a t i o na n du s ei t a st h en u m e r i c a l c h a r a c t e r i z a t i o n so fd n a s e q u e n c e s f u r t h e r m o r e t h ep a p e ro u t l i n e st w oa p p r o a c h e s t oc o m p u t et h es i m i l a r i t i e so fd n as e q u e n c e s i nc h a p t e rf o u r , b i n a r yi a b e l sa r eu s e dt or e p r e s e n tt h ec h a r a c t e r i s t i cs e q u e n c e s 0 fl 吼s e c o n d a r ys t r u c t u r e s s ot h es e q u e n c e sa r et r a n s f o r m e di n t ob i n a r yc o d e s t h e np r o p o s ea2 dg r a p h i c a lr e p r e s e n t a t i o no fr n as e c o n d a r ys t r u c t u r e sb yu s eo f t h e w o r m c u r v ea st e m p l a t e t h ep a p e rc o n s t r u c t sq u o t i e n tm a t r i c e sa n dl e t st h e n o r m a l i z e d l e a d i n ge i g e n v a l u e s o ft h e q u o t i e n t m a t r i c e sb et h en u m e r i c a l c h a r a c t e r i z a t i o n so fr n as e c o n d a r ys t r u c t u r e s a tl a s tt h ep a p e rg i v e so u tt h e e x a m i n a t i o no fs i m i l a r i t i e sa m o n gt h es e c o n d a r ys t r u c t u r e so f n i n ed i f f e r e n tv i r u s e s k e y w o r d s ：d n as e q u e n c e s ，r n as e c o n d a r ys t r u c t u r e s ，q u o t i e n tm a t r i c e s ， n o r m a l i z e dl e a d i n g e i g e n v a l u e , s i m i l a r i t y 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含其他教育机构的学位或证书使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：牟敬君签字日期；2 0 0 8 年5 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到 中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：牟敬君 签字日期：2 0 0 8 年5 月日 字逸幽写 签字日期击年乃7 7 日 生物序列的图形表示及相似性分析 1 1 背景及发展情况 第1 章引言 随着人类基因组计划( h g p ) 实施的进一步深入，生命科学已步入后基因组 时代。现在和将来，科学家们将着重于研究d n a 序列信息、蛋白质结构信息，以 及它们之间的相互作用。生物信息的急剧增长也带来了对其它学科的挑战，为此， 计算分子生物学和生物信息学便应运产生。计算分子生物学是数学、计算机科学 和生物科学交叉的新兴领域之一，主要研究与基因和蛋白质序列有关的组合和计 算问题。其主要课题有：序列组合、序列分析、生物信息资料库、基因认定、种 族树的构建以及结构预测等。生物信息学是计算分子生物学的“孪生 学科，是 用数理和信息科学的观点、理论和方法去研究生命现象、组织和分析呈现指数增 长的生物学数据的一门学科。 传统的序列( d n a 、r n a 和蛋白质) 是用字母表示，它在发表、存储和提供计 算机进行快速分析等方面具有不容争议的优点，因而被广泛应用。但是，随着计 算复杂度的增加和可视化技术的发展，序列的字母形式不能满足人们的多种需 要。近年来，不少学者打破了d n a 序列的字母表示的传统，给出了一系列d n a 序 列的图形表示。图形表示的发展也为生物序列的相似性分析提供了一种新的方 法，即数值刻画法。在结构基因学和功能基因学的研究过程中，生物序列的相似 性分析成为一种有效的手段，具有深远的意义和实际应用价值，并且具有广阔的 发展空间。 目前国内外对于生物序歹0 的相似性分析已有不少成果，他们有个共同的思想 就是：将生物序列转化为图形，利用图形构造矩阵，再利用矩阵不变量来比较生 物序列的相似性。a n a n d y 于1 9 9 4 年最先提出d n a 序列的图形表示 1 ，随后， 在文献 2 ，3 中m r a n d i c 和m v r a c k o 等人利用四条水平线构造了2 d 图形表示， 并提出了m m ，l l ，l l 矩阵；文献【4 ，5 】用二进制码表示碱基，并利用 w o r m 曲线为模板给出了一种2 d 表示；文献【6 ，7 】分别提出了d n a 序列的 3 d 和4 d 图形表示：张春霆院士给出了一种d n a 几何图形表示一z 曲线：廖波、 张玉森、王天明、郭晓峰等也给出了不同的图形表示，文献 8 ，9 将核苷酸a ，c ，g 1111 和t 分别附初始坐标( 一1 ) ，( ，1 ) ，q ) ，( 二，一1 ) ，然后坐标累加，得到一种低退 口 口口 a 化度的2 d 表示；文献 i o i 根据四种核苷酸的分类分别附a ( c ) ，g ( t ) 坐标“f ) ， 生物序列的图形表示及相似性分析 ( o , i ) ，a ( g ) ，c ( t ) 坐标n f ) ，( 0 ，f ) 和a ( t ) ，g ( c ) 坐标g i ) ，( 0 ，f ) ，使得每条序列对 应三条曲线；文献【1 1 】通过对核苷酸a ，g ，c 和t 分别附初始坐标( 小，一五) ， ( n ，一埘) ，( n ，小) ，伸，n ) 得到一种非退化的2 d 图形表示；文献 1 2 - 1 4 均对 核苷酸核苷酸a ，g ，t ，c 附初始坐标( 一1 0 ，0 ) ，g 0 ，0 ) ，( 0 ，- l o ) ，( o , l o ) ，通过构造映 射给出了不同的3 d 图形表示；文献 1 5 根据碱基的三种分类构造映射，通过把 d n a 序列映射成点集，给出了一种4 d 图形表示：文献 1 6 2 0 以碱基对为研究对 象，分别给出了不同的2 d 和3 d 图形表示，而文献 2 1 ，2 2 则以三联核苷酸为研 究对象，给出了d n a 序列的不同图形表示。上述文献中进行相似性分析时用到的 矩阵不变量主要有最大特征值、次对角线上所有元素和的平均值、最大( 小) 行 和、矩阵的迹等等。利用与d n a 序列的图形表示相同的方法，文献 2 3 ，2 8 给出 了关于r n a 二级结构的图形表示，并在此基础上寻求结构不变量，进一步进行相 似性分析。 早期的图形表示存在各自的缺陷，主要表现在：( 1 ) 有退化现象和序列信息 丢失现象。( 2 ) 维数太高，不满足可视性。( 3 ) 对完整序列而言，使用的数学变 量计算太复杂。近几年来，随着研究的深入，上述问题正逐渐被克服，生物序列 图形表示方面的研究进入了新的阶段。 1 2 预备知识 本文用到许多分子生物学方面的相关知识，有基本的概念，例如：d n a 、 r n a 、蛋白质等：还有分子遗传学机制，例如：基因、遗传密码和蛋白质的合成 等。下面介绍一些基本的知识： 一、d n a ，r n a 和蛋白质。 生物体包含两类核酸：核糖核酸( r i b o n u c l e i ca c i d ) ，简写为r n a ；脱氧核糖 核酸( d e o x y r i b o n u c l e i ca c i d ) ，简写为d n a d n a 是遗传特征的基础，它是由核 苷酸小分子生成的聚合物，核苷酸由糖、磷酸和碱基构成。核苷酸共有四种，可 以用四种碱基来区分它们，四种碱基分别是腺嘌呤( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 。d n a 分子可以看作是四个字母字符集k = a ，c ，g ，t 上的词。d n a 分子是有方向性的，由糖中的5 个碳原子进行标记。一般按5 3 方向。d n a 蕴 含的复制机制的关键特征就是碱基互补，即a 与t 配对，g 与c 配对。这种配对 2 生物序列的图形表示及相似性分析 是由于氢键的作用，原理是d n a 单个链( 按5 到3 次序) 与相反方向的相补的链 配对。d n a 分子是双链结构，两条链缠绕在一起形成双螺旋，即著名的双螺旋结 构。这种碱基互补配对的机制使得d n a 在细胞中得以复制。 r n a 分子与d n a 分子很相似，但在组成和结构上也有一些重要的区别。在r n a 分子中，核糖取代了d n a 分子中的脱氧核糖。另外，胸腺嘧啶t 被尿嘧啶u 取代 了，u 与t 一样能够与a 配对。r n a 分子并不形成双螺旋，有时可以看到r n a d n a 杂交双螺旋。此外，r n a 能够通过碱基互补与同一分子的其他部分结合。r n a 主 要有3 类，即信使r n a ( m r n a ) ，核糖体r n a ( r r n a ) 和转移r n a ( t r n a ) 。这3 类r n a 分子都是单链，但具有不同的分子量、结构和功能r n a 二级结构就是单 链r n a 分子自身缠绕配对可以形成茎环结构，例如t r n a 可以形成三叶草的二级 结构。 蛋白质是生命的物质基础，没有蛋白质就没有生命。它们既是工作部件，又 是组成原料。蛋白质包括很多种，结构蛋白是组织的构成单元，酶是化学反应的 催化剂。蛋白质是由一类称为氨基酸的简单分子组成的。自然界中发现了2 0 种 不同的氨基酸，表i - i 列出了这些氨基酸，这是蛋白质中最常见的2 0 种，另外 还有几种非标准的氨基酸。 表1 - i 蛋白质中发现的2 0 种常见的氨基酸 单字母缩写三字母缩写名称 1aa l a 丙氨酸( a l a n i n e ) 2 c c y s 半胱氨酸( c y s t e i n e ) 3d a s p天冬氨酸( a s p a r t i ca c i d ) 4eg l u 谷氨酸凹l i a l n i ca c i d ) ： ： 5fp h e 苯丙氨酸( p h e n y l a l 柚i n e ) 6g g l y 甘氨酸( g l y c i n e ) 7hh i s 组氨酸( h i s t i d i n e ) 8i l i e 异亮氨酸( i s o l e u c i n e ) 9k l y s赖氨酸( 1 y s i n e ) 1 0ll c u 亮氨酸( 1 e u c i n e ) l lmm e t 甲硫氨酸( m e t h i o n i n e ) 1 2 na s h 天冬酰氨( a s p a r a g i n e ) 1 3pp r o 脯氨酸( p r o l i n e ) 1 4 q g l n 谷氨酰胺( g u t a m i n e ) 1 5 r a r g精氨酸( a m i n i n e ) 生物序列的图形表示及相似性分析 1 6 1 7 1 8 1 9 2 0 s t v w y s e r t h r 唧 r y r 丝氨酸( s e r i n e ) 苏氨酸( t h r e o n t n e ) 缬氨酸( v a l i n e ) 色氨酸( t r y p t o p h a n ) 酪氨酸( t y r o s i n e ) 二、分子遗传学机制。 d n a 分子的重要性在于，机体中合成r n a 和蛋白质的信息编码于d n a 分子中。 基于此，d n a 有时被称为“生命蓝图 。每个细胞都有几个非常长的d n a 分子， 每一个这样的分子称为染色体。d n a 中仅有一部分连续的片段编码构建蛋白质的 信息，而其它部分并不编码蛋白质信息。每一种蛋白质仅对应一段d n a 序列，该 段序列称为基因。如前所述，蛋白质是氨基酸链，因此，确定蛋白质仅需确定其 所含的每一个氨基酸。这正是基因所要做的，它用三联核苷酸编码每一个氨基酸， 每个三联核苷酸称为密码子。三联核苷酸与氨基酸之间的对应关系称为遗传密 码，见表1 - 2 。 表1 - 2 中的三联核苷酸是用r n a 碱基而非d n a 碱基表示，因为r n a 分子提供 了d n a 和蛋白质之间的关联。有三个密码子u 从，u a g 和i i g a 并不编码任何氨基酸， 而是用于表示基因的终止。 蛋白质的合成是通过细胞中的酶的作用将d n a 中所隐藏的信息转录到m r n a 中，再由t r n a 按密码子一反密码子配对的原则，将相应氨基酸运到核糖体中，按 照m r n a 的编码按顺序排列成串，形成多肽链，再进行折叠和扭曲成蛋白质。 三、读框和可读框。 读框是指把d n a 或r n a 序列划分成密码子的3 种可能方式之一。需注意的是 3 种读框分别起始自给定序列的l 、2 、3 位置，如果考虑从位置4 开始，获得的 密码子是起自碱基1 所获得读框的子集，即是起自不同位置的同一读框。通常， 如果分别起始自f 和，i f i 是3 的倍数，那么实际上使用的是同一读框。 d n a 序列的一个可读框是指该序列的一个连续段，由起始密码子开始，含有 整数个的密码子( 长度是3 的倍数) ，且无终止密码子。 表l - 2 氨基酸的遗传密码 4 生物序列的图形表示及相似性分析 a a u ，a a ca s p a r a g i n e a s hn u g u ，u g c c y s t e i n ec y s c g a a , g a g g l u t a m i ca c i dg l ue c a a , c a g g l u t a m i n eg 1 i i q g g u ，c , g c , g c , a , g g gg l y c i n eg l y g c a u ，c a c h i s t i d i n eh i sh a u 配a 泓 i s o l e u c i n en ci c u u ，c u c ，姒c u g u - u a , u u g l e u c i n el e u。l a a a a a g l y s i n e跏 k a u gm e t h i o n i n em e tm u u u ，u u c f h e n y l a l a n i n e p h cf c c u ，c c c ，c c a , c c g p r o l i n ep r op u c u ，u c c , u c a , u c g a g u , a c - c s e r i n es e rs a c u , a c c , a c a , a c g t h r c o n i n et h rt u g g t r y p t o p h a nt q , w u a u ，u a c t y r o s i n e斯 y g u u ，g u c ，g u a , g u g v a l i n ev v 5 生物序列的图形表示及相似性分析 第2 章d n a 序列的二维图形表示 a n a n d y 于1 9 9 4 年提出d n a 序列的图形表示之后，许多学者都相继给出过 d n a 序列的二维图形表示f 2 5 ，8 1 1 ，2 9 。上述表示都是针对单个碱基进行分析 得出的，此外，还有一些学者通过对碱基对的研究，分别提出了不同的二维表 示1 6 1 8 1 。m r a n d i 和廖波早期都考虑过利用三联核苷酸来比较d n a 序列的相 似性 2 l ，2 2 。由于三联核苷酸在蛋白质的形成过程发挥重要作用，因此，利用 三联核苷酸来研究d n a 序列具有深远的意义。不同于已有的二维图形表示，本 章通过把d n a 初始序列划分成一系列密码子，根据遗传密码建立映射，得到一 种新颖的2 d 图形表示。此图形表示满足可视性，而且是非退化的。在此图形表 示基础上，进行的相似性分析是借助于广泛使用的商矩阵三和m m 的正规 化最大特征值。与其它二维图形表示基础上的相似性矩阵相比，本章得到的结 果是合理的，并且有一定进步。 2 1 构造2 d 图形表示 对于任意给定的d n a 序列gi i s g 。，9 2 ，g 矗( & 似，t ，g ，c ，f 一1 ，2 ，以 此处n 是被给定序列的长度) ，首先构造映射妒，把初始序列映射成一系列点的 集合，点的坐标为( 毛y ) 。由于每个三联核苷酸即为一个密码子，因此，可以把 d n a 初始序列表示成密码子序列g = g 。g ：9 3 ，g 。9 5 9 。，若用c j 表示密码子，则 上述序列可以写为g - q ，c 2 ，c l ( 此处m - n 3 ) 。密码子一共有6 4 个，其中 6 1 个编码蛋白质，见表1 - 2 ，其余三个密码子u a a ，u a g 和u g a 并不编码任 何氨基酸，而是用于表示基因的终止。由此遗传密码，下面给出映射驴，满足： 7 生物序列的图形表示及相似性分析 妒( c i ) 一 ( i ，1 ) 若q g c t ，g c c ，g c a , g c g ( i ，2 ) 若q t g t ，t g c ( i ，3 ) 若c j g a t ，g a c ( i ，4 ) 若q g a a , g a g ( i ，5 ) 若q 1 盯，t t q ( i ，6 ) 若c je g g t ，g g c ，g g a , g g g ( i ，7 ) 若c ie ( c a t ，c a q ( i ，8 )若qe a t i ，a t c ，a t q ( i ，9 ) 若c ； a a a , a a g ( i ，1 0 ) 若c ie c r r ，c t c ，c t 八c t g ， ir a , t r g ( i ，1 1 ) 若c ie a t g fi1 , 2 朋 ( i ，1 2 ) 若qe a a t , a a c ( i ，1 3 ) 若qe c c r ，c c c ，c c a , c c g ( i ，1 4 ) 若c fe c a a , c a g 若qe c g t ，c g c ，c g a , c g g ，a g g ，a g a 若qe ( t c t , t c c ，t c a , t c g ，a g t ，a g c 若qe ； a c t , a c c ，a c a , a c g 若qe g i t ，g t c ，g t a , g t g 若q t o g 若q ( t a t ，t a c 若c i t g a , t a g ，吖姨 由驴的定义可知，对于每个密码子c ，都有唯一确定的点与之对应，即驴是单 一映射。 7 一 表2 - 1 给出了1 1 种物种的球蛋白基因的第一个外显子序列。以人的序列 的前3 0 个碱基为例，c i = - a t g g t g c a c c t g a c t c c t g a g g a g a a g t c t 可以表 示成l o 个密码子序列g = a t g ，g t g ，a 屺，c t g ，a c t ，c c t ，g a g ，g a g ， a a g ，t c t ，经过映射妒的作用，得到一系列点的集合( ( 1 ，1 1 ) ，( 2 ，1 8 ) ，( 3 ，7 ) ， ( 4 ，1 0 ) ，( 5 ，1 7 ) ，( 6 ，1 3 ) ，( 7 ，4 ) ，( 8 ，4 ) ，( 9 ，9 ) ，( 1 0 , 1 6 ) ) 8 、-、-、-、一、j 5 6 7 8 9 0 ) 1 1 1 1 1 2 o bbbbkbk ，ll，l，l，l，k，l 生物序列的图形表示及相似性分析 表2 - 11 1 种物种的基因的第一个外显子序列 物种 d n a 序列 人a t g g t g c a c c t g a c t c c t g a g g a g a a g t c t g c c g l - r a c t g c c c t g t g g g g h u m a nc a a g g t g m c g t g g a _ r 丁a a g t t g g t g g t g a g g c c c t g g g c a g 羊a t g c t g a c t g c t g a g g a g a a g g c t g c c g t c a c c g g c t t c t g g g g c m g g g o a tt g 舭a g t g g a t g a a g t t g g t g c t g a g g c c c t g g g c a g 负鼠a t g g t g c a c t t g a c t t c t g a g g a g m g m c t g c a t c a c t a c c a t c t g g t c o p o s s u mt a a g g t g c a g g 丌g a c c a g a c t g g t g g t g a g g c c c 丌g g c a g 山鸡a t g g t g c a c t g g a c t g c t g a g g a g m g c a g c t c a t c a c c g g c c t c t g g g g g a l l u sc a a g g t c m t g t g g c c g a a 丁g t ( 迄g g c c g m g c c c t ( 拈c c a g 狐猴a t g a c t t t g c t g a g t g c t g a g g a g m t g c t c a t g t c a c c t c t c t g t g g g g c l e m u rm g g t g g a t g t a g a g a m g 丌g g t g g c g a g g c c t t g g g c a g 家鼠 a t g g t t g c a c c t g a c t g a t g c t g a g a a g t c t g c t g t c t c t t g c c t g t g g g c m o u s e 执g g t g m c c c c g a t g m g t l - g g t g g t g a g g c c c t g g g c a g g 野兔 a t g g t g c a t c t g t c c a g t g a g g a g a a g t c t g c g g t c a c t g c c c t g t g g g g c r a b b i tm g g t g a j 盯g t g g a a g a a g 丌g g t g g t g a g g c c c t g g g c 鼠a t g g t g c a c c w 姨c t g a t g c t g a 呲g c r a c t g t t a g t g g c c t g t g g g g a r a ta a g g t g m c c c t g a t a a t g t t g g c g c t g a g g c c c t g g g c a g 大猩猩a t g g t g c a c c t g a c t c c t g a g g a g m g t c t g c c g t t a c t g c c c t g t g g g g c g o r i l l aa a g g t g m c g t g g a t g m g t t g g t g g t g a g g c c c t g g g c a g g 牛a t g c t g 屺t g c t g a g g a g a a g g c t g c c g t c a c c g c c 丌1 t g g g g c a a g g t g b o v i n e 执g t g g a t g 从g r g g t g g t g a g g c c c t g g g c a g 黑猩猩a t g g t g c a c c t g a c t c c 丁g a g g a g m g t c t g c c g t t a c t g c c c t g t g g g g c c h i m p a n z e ea a g g t g m c g t g g a t g m g t t g g t g g t g a g g c c c t g g g c a g g l t g g t a t c a a g g 对任意给定的序列，通过上述映射妒，得到一系列点的集合，且点的坐标 已知。下一步，在笛卡尔坐标系中，标出集合中的点，然后用直线连接每两个 相邻的点，即可得到一条z 形曲线，称为d n a 序列的特征曲线，此曲线即为d n a 序列的2 d 图形表示。图2 - 1 给出了对应于人的序列的前3 0 个碱基序列的图形 - - i - - - 一 霰不o 9 生物序列的图形表示及相似性分析 图2 - i 序列a t g g t g c a c c t g a c t c c t g a g g a g a a g t c t 对应的图形表示 由于任意d n a 序列在划分成密码子时都有三种读框，分别起始自给定序列 的l 、2 、3 位置。上述图形表示是按第一种读框得到的。如果从序列的2 、3 位 置开始划分密码子，将会得到两种不同的密码子序列，需要注意的是，此时密 码子的长度研分别满足坍一f ( 刀一1 ) 3 1 和历一( 刀- 2 ) 3 1 。经过映射妒的作用， 会得到两个点集，进一步得到两条特征曲线。因此对于给定d n a 序列，通过上 述构造方法会得到三个图形表示，分别称为a ，b 以及c 型曲线。图2 - 2 给出了 对应于人的声基因的第一个外显子序列的a ，b 和c 型曲线，可以看出三种曲线 是截然不同的。 a 型b 型 c 型 图2 2h u m a n 的卢基因的第一个外显子序列的a ，b 和c 型曲线 1 0 生物序列的图形表示及相似性分析 2 2d n a 序列的直观分析 图2 - 3 给出了1 1 种物种的卢基因的第一个外显子序列的a 型曲线。由构造 图形表示过程可以看出，得到的特征曲线是非交叉并且非重叠的，因此图形表 示是非退化的。此外，在将d n a 初始序列转化成点集过程中，没有信息的丢失。 对于任意的d n a 序列，在某一读框下有且仅有一条特征曲线与之对应。 分析图2 - 2 给出的特征曲线，可以直观判断g a l l u s 和其它物种是不相似的， 因为其特征曲线存在很大差异。另一方面，可以看到h u m a n 和c h i m p a n z e e ， g o a t 和b o v i n e ，r a b b i t 和r a t 是比较相似的，只是在某段对应曲线上有个别的 差异。同时，也可以看到o p o s s u m ，r a b b i t ，r a t 以及g o r i l l a 都与h u m a n 有相 似的趋势，但与h u m a n 相比较还是有不同程度的跳跃。 因此，要进一步分析这些物种之间的相似性必须借助于图形表示的数值特 征。 h u l l l a i l w 、 o d o s s u m l e m u r g a l l u s m o u s e 生物序列的图形表示及相似性分析 r a b b i t g o r i l l a c h i m p a n z e e b o v i n e 图2 31 1 种物种的基因的第一个外显子序列的a 型曲线图 2 3d n a 序列的2 d 数值特征 为了对d n a 序列进行相似性分析，本章中采用不变量来刻画其特征曲线。 通过上述方法得到d n a 序列的图形表示之后，利用d n a 序列的特征曲线构造一 个矩阵，进一步采用矩阵不变量一最大特征值来作为该序列的数值特征。下面 给出所用到的商矩阵l l 和肘吖，具体定义如下： 首先，给出用到的两个距离矩阵：欧氏距离矩阵e d 和路径距离矩阵p d 给定特征曲线上任意两点f 和j ，坐标分别为( 而，只) 和( x ，y ，) 欧氏距离矩阵 e l ) 是元素f e di 。定义为点f 和j f 之间的欧氏距离的对称矩阵： 1 2 生物序列的图形表示及相似性分析 f 吼一f 巩；拈一t ) 2 + ( 辫一乃) 2 。 路径距离矩阵p d 是元素 p d l 定义为点f 和j 之间的所有的邻接点间的欧氏距 离和的对称矩阵： 【p d l | 肋】爿一 e d l 1 + 严d k ：+ + p d k ，( f _ ) o ， 商矩阵l l 的元素 l l 定义为矩阵e d 和p d 对应元素的商： l l 1 , 一【e d p d 】 ，( f j ， l l o 一0 ) 。 同样的，商矩阵膨肘的元素 膨m l 定义为矩阵肋对应元素和特征曲线 上的点f 和j 之间的图论距离的商： m m 1 , - 严d w 一小( f j f ， m m l s o ) 由上可知，商矩阵l l 和m m 是对称矩阵。 得到商矩阵l l 和m m 后，即可计算其最大特征值a 作为d n a 序列的数 值特征。由于每个物种的d n a 序列长度可能不同，为了消除不同长度对相似性 分析的影响，故使用正规化最大特征值a ( a 一z n ，n 为序列长度) 来代替最 大特征值作为d n a 序列的2 d 数值特征。表2 - 2 给出了由1 1 种物种的d n a 序列 的2 d 图形表示( a 型曲线) 得到的商矩阵l l 和m m 的正规化最大特征值a 。 和a “。 表2 21 1 种物种的a 型曲线得到的正规化最大特征值 h u m a ng o a t o p o s s u m g a l l u sl e m u rm o u s er a b b i tr a tg o r i l l ab o v i n ec h i m p a n z e e a 0 2 6 0 80 2 8 0 80 2 9 5 9 0 2 9 3 6 0 2 7 7 0 0 3 0 1 4 0 2 6 5 9 0 2 8 5 1 0 2 6 0 40 2 7 8 9 0 2 5 3 5 五”2 0 9 5 12 1 1 0 01 8 5 4 0 1 9 1 1 91 9 6 9 6 2 0 3 0 4 2 0 4 3 1 1 9 5 4 42 0 1 7 12 1 4 7 41 8 8 4 8 2 4 相似性分析 借助于上面得到的2 d 数值特征，进一步对d 懈列进行相似性分析通过构 造三维向量，以向量间的相似性来确定对应d n a 序列间的相似性。在三维向量基 生物序列的图形表示及相似性分析 础上进行的相似性分析是基于以下假设：在三维空间中，两个向量指向同一个方 向并且长度相同，就说它们对应的序列是相似的。相似性的计算通常有以下三种 方法： ( 王) 计算向量终点之间的欧氏距离，如果两个向量的终点距离较小就认为 所对应的两个序列比较相似。 ( 2 ) 计算向量之间的夹角，如果两个向量所成角比较小就认为所对应的两 个序列比较相似。 ( 3 ) 计算向量夹角的余弦值，如果两个向量所成角的余弦比较大就认为所 对应的两个序列比较相似。 首先，构造三维向量。由上述2 d 图形表示可知，给定一条d n a 序列，对应 于三种读框可以得到三条特征曲线。根据每一条特征曲线都可计算商矩阵三三 和m m 的正规化最大特征值a 和a ”。因此，对于给定d n a 序列，可得到两个 分别由商矩阵l l 和m 材的正规化最大特征值组成的三维向量。例如，对于 人的d n a 序列，在商矩阵工基础上得到的三维向量是( 0 2 6 0 8 ，0 3 2 8 2 ，0 2 5 2 0 ) ， 在商矩阵膨m 基础上得到的三维向量是( 2 , 0 9 5 1 ，1 9 7 4 4 ，2 1 4 1 9 ) 。表2 - 3 给出 了1 1 种物种的d n a 序列分别在商矩阵l l 和mi m 基础上得到的三维向量。 表2 - 31 1 种物种的d n