（基础数学专业论文）生物序列进化树的构建.pdf

摘要 随着一些微生物基因组、人类基因组、拟南芥基因组和水稻基因组全序列测定项 目的完成和快速进展，以及各种生物的基因和蛋白序列的研究，产生了越来越多庞大的 分子序列数据。 计算分子生物学是- - i - 崭新的交叉学科，主要是研究分子生物学应用上具有计算复 杂度的问题，它吸引了许多计算机科学家，分子生物学家，数学家，物理学家投入研究 计算分子生物学的研究对象是与基因和蛋白序列有关的组合和计算问题。计算分子生物 学的主要课题有：序列组合，序列分析，生物信息资料库，基因认定，种族树的构建以 及结构预测等。 本文皆在探索一些简而有效的分析生物数据的方法，主要内容可以概括为以下几 方面： 1 ) 简单介绍了分子生物学的一些基础知识，包括常用的术语和基本概念都做了简 要的介绍。以及系统发生树构建主要方法和软件的介绍。 2 ) 在进化树的构建方面提出了条件l z 复杂度的新方法，应用于d n a 序列与蛋 白质序列的进化树构建。这个方法对序列的长度没有要求，并且时间复杂度不 高，也不涉及任何模型的假设。 3 )对线粒体d n a 序列通过图形表示及计算曲线的散度均值来构造模糊论中的相 似矩阵，由此我们提出一种新的方法，用模糊聚类的图论法中的k r u s k a l 算法 来进行系统进化树的重构。+ 关键词：d n a 序列：蛋白质序列；进化树；l e m p e l z i v 复杂度；条件l e m p e l z i v 复杂 度；特征序列；k r u s k a l 算法；模糊聚类 a b s t r a c t b a s e do nt h ec o m p l e t e n e s so fg e n o m es e q u e n c i n gp r o j e c t so ft h eh u m a n ，a r a b i d o p s i s t h a l i a n a ，r i c ea n dt h er e s e a r c ho np r o t e i ns e q u e n c e s ，m o r ea n dm o r em o l e c u l a rs e q u e n c e s d a t ah a v e b e e ng e n e r a t e d t h ec o m p u t a t i o nm o l e c u l a rb i o l o g yi sab r a n d n e wi n t e r d i s c i p l i n a r y m a i n l yr e s e a r c ho n t h ea p p l i c a t i o no fm o l e c u l a rb i o l o g yw i t hc o m p u t a t i o n a lc o m p l e x i t yo fi n t e r - t i t l e ，i ta t t r a c t e d m a n yc o m p u t e r ss c i e n t i s t s ，t h em o l e c u l a rb i o l o g i s t ，t h em a t h e m a t i c i a n ，t h ep h y s i c i s t i n v e s t e d t h er e s e a r c h t h ec o m p u t a t i o nm o l e c u l a rb i o l o g yr e s e a r c ho b j e c ti sa n dt h eg e n ea n dt h ep r o t 。 e i ns e q u e n c e sr e l a t e dt ot h ec o m p o s i t i o na n dc a l c u l a t i o np r o b l e m s t h ec o m p u t a t i o nm o l e c u l a rb i o l o g ym a i nt o p i ci n c l u d e s ：s e q u e n c ec o m p o s i t i o n ，s e q u e n c ea n a l y s i s ，b i o i n f o r m a t i c sd a t a b a s e s ，g e n ei d e n t i f i e d ，c o n s t r u c t i n gp h y l o g e n e t i ct r e e s ，a n dp h y l o g e n e t i ct r e e ss t r u c t u r ep r e d - l c t l o n t h i sd i s s e r t a t i o ni sa i m e da te x p l o r i n gs i m p l ea n de f f i c i e n tm e t h o d sf o ra n a l y z i n gb i o l o g i c a ld a t a ，t h em a i nc o n t e n ti nt h i sd i s s e r t a t i o nc a nb eo u t l i n e da sf o l l o w s ： 1 ) w ei n t r o d u c e ss o m eb a s i ck n o w l e d g eo fm o l e c u l a rb i o l o g y m o s to ft h et e r m sa n d c o n c e p t su s e di nt h i sp a p e r a r ee x p l a i n e db r i e f l yh e r e 2 ) f o rt h es t u d yo nc o n s t r u c t i n gp h y l o g e n e t i ct r e e s ，w ep r o p o s en e wm e t h o db a s e do n c o n d i t i o nl zc o m p l e x i t y ，w h i c hu s ep r o t e i ns e q u e n c e sa n dd n as e q u e n c e sf o r c o n s t r u c t i o n p h y l o g e n e t i c t r e e s t h e s e a p p r o a c h e s d o n t r e q u e s tl e n g t h o f s e q u e n c e ，a n di td o n ti n v o l v ee v o l u t i o n a r ym o d e lh y p o t h e s e sa n dt h e i rt i m ec o m p l e x i t ya r en o th i g h 3 ) t h r o u g hg r a p h i cr e p r e s e n t a t i o n sa n d t h ea v e r a g ev a l u e so fd i v e r g e n c eo ft h ec u r v e s o fg i v e nm i t o c h o n d r i a ld n a s e q u e n c e st oc o n s t r u c tt h es i m i l a rm a t r i c e si nt h ef u z z y t h e o r y , w ep r o p o s ea n e wa p p r o a c hb a s e do nt h e s e k r u s k a la l g o r i t h mo ff u z z yc l u s t e r i n go fg r a p ht h e o r 3 , m e t h o d sf o rp h y l o g e n e t i cr e c o n s t r u c t i o n k e y w o r d s ：d n as e q u e n c e s ；p r o t e i ns e q u e n c e s ；p h y l o g e n e t i ct r e e s ；l e m p e l - z i vc o m p l e x i t y ； c o n d i t i o nl e m p e l z i vc o m p l e x i w ：c h a r a c t e r i s t i cs e q u e n c e ；k r u s k a la l g o r i t h m ；f u z z yc l u s t e r ! 1 1 图索引 图2 1 核酸中的糖，符号1 一5 表示碳原子。两种糖的唯一差别是27 碳原子中的氧， r n a 中是核糖，d n a 中是脱氧核糖6 图2 2d n a 中氮化的碱基。两种w a t s o n c r i c k 配对，留意腺嘌呤与胸腺嘧啶，鸟嘌呤 与胞嘧啶之间所形成的键，图中用点线表示6 图2 3 一个d n a 链分子结构的图示7 图2 - 4 单链d n a 分子的简单示意图7 图2 5d n a 分子碱基互补图7 图2 - 6 双链d n a 链分子结构的图一8 图2 7d n a 的三维结构8 图2 8 三叶草二级结构的一般表示一9 图2 - 9 三叶草二级结构半圆表示9 图2 1 0 氨基酸分子结构通式1 0 图2 1 1 细胞内的遗传信息流动：分子生物学中心法则1 3 图3 1 蛋白质超家族的系统进化树2 6 图4 一l 八个d n a 序列的最大树3 4 图4 2 八个d n a 序列的进化树3 4 图4 32 2 个d n a 序列在r ( s ( i ) ) 变换下所构建的系统发生树3 8 图4 42 2 个d n a 序列在m ( s ( i ) ) 变换下所构建的系统发生树3 8 图4 52 2 个d n a 序列在w ( s ( i ) ) 变换下所构建的系统发生树3 9 v l i 表索引 表2 1 蛋白质中发现的2 0 种常见氨基酸以及氨基酸的遗传密码1 1 表4 1cc h i m 和h o r s e 线粒体d n a 序列的前1 0 个字符对应的坐标3 l 表4 2 八个线粒体d n a 物种名称及g e n b a n k 索取号；3 2 表4 3 八个物种的线粒体d n a 序列对应曲线的散度均值3 2 表4 _ 4 八个物种的线粒体d n a 序列对应的相似矩阵3 3 表4 5 十个哺乳动物的球蛋白基因的第一个外显子区序列3 6 表4 61 2 组禽流感基因序列的物种序号，访问号，长度，年份和病毒基因名称3 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。除文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得海南师范大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：扭萎拯 日 学位论文著作权声明 本论文作者声明： 影本论文全部成果均为本人和指导教师合作研究取得，本人和指导教师都有权使 用本成果学术内容( 有第三方约定者除外) 。 口本论文为指导教师指导下，本人独自完成。本人独自享有 学位论文作者签名：扭蓄鉴 指导教师签名： 日 期：2 翌垒垒因f 徊 日 作权。 学位论文版权使用授权书 本学位论文作者完全了解海南师范大学有关保留、使用学位论文的规定，即：海南 师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子文本，允许论 文被查阅和借阅。本人授权海南师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 指导教师签名：壁垒丝 日 期：半? 日 第一章绪论 本章介绍了生物序列研究的背景、理论意义及应用价值、生物序列系统进化树的构 建概况。同时简要概括了本论文的研究内容和工作。 1 1 生物序列研究的背景、理论意义及应用价值 计算分子生物学这个术语首先在1 9 8 3 年被w a r r e nw a v e r 使用。它是2 0 世纪发展最 快的学科和领域之一。随着人类基因组计划( h g p ) 实施的进一步深入，生命科学己步入 后基因时代。基因和蛋白质已成为现代生命科学的主要研究对象。过去，生物科学家们 研究单个基因或蛋白质，现在和将来，科学家们将着重于研究d n a 序列信息，蛋白质 结构信息，以及它们之间的相互作用。生物信息的的急剧增长也带来了对计算机科学的 挑战为此，计算分子生物学与生物信息学便应运而生。 计算分子生物学是数学、计算机科学和生物科学交叉的新兴领域之一它是一个十 分活跃的研究领域，它致力于应用可计算的技术研究生物学问题，包括存储，抽取和分 析生物学数据，如核酸( d n a 或r n a ) ，蛋白质序列、结构、功能、调控网络等。 计算分子生物学不仅是生物信息学的前身，更是生物信息学的核心部分。广义地说， 生物信息学是对生物信息的获取、加工、储存、分配、分析和释读，并综合运用数学、 信息科学、计算机科学、系统科学和生物学工具，以达到理解数据库中各种数据的生物 学含义的目的。因此，生物信息学具有三方面的科学基础：首先，它需要发达的、复杂 的、可互相交流的数据库系统：其次，它需要强有力的创新算法和软件来获得持续的发 展：最后也是最重要的是计算分子生物学需要一个大规模、高通量的生物学研究方法和 平台技术，这些技术既是产生生物信息的数据的主要方法又是在利用生物信息分析结果 的基础上进一步获取或验证生物学知识的关键手段。具体地说，生物信息学是把基因组 d n a 序列信息分析作为源头，找到基因组序列中代表蛋白质和r n a 基因的编码区，阐 明非编码区的信息实质、破译隐藏在d n a 序列中的遗传语言规律：同时，归纳、整理与 基因组遗传语言信息释放及调控相关的转录谱和蛋白质谱的数据，从而认识代谢、发育、 分化、进化的规律。生物信息学的内容包括三个层次：基因组信息学、蛋白质的结构计 算与模拟以及分子药物设计。这里基因组信息学是生物信息学的源头和基础：蛋白质的 海南师范大学硕士学位论文 结构计算与模拟是基因组信息学发展的必然结果：分子药物设计是利用蛋白质结构与功 能信息造福人类的有力工具。生物信息学的研究内容非常丰富，例如序列的比较和分析、 构造进化树、基因预测、r n a 和蛋白质结构预测、d n a 和蛋白质序列的表示、药物设 计等等。其中序列的比较是生物信息学中最基本也是最重要的问题，因为对于d n a 序 列，即使我们考虑它的一个很短的片段，我们也不可能直接得出它表示的对象所具有的 信息，然而如果我们比较不同的序列就有可能得到某些信息。例如，通过比较人类的基 因组与黑猩猩的基因组，我们可以研究哪个基因或者哪些基因与疟疾等人类疾病( 黑猩 猩从来不会患) 有关，进而为疾病预防、药物设计提供宝贵的参考；通过将一个未知功 能的蛋白质与一批已知功能的蛋白质进行比较，我们可以预测它的结构及功能；通过序 列比较，我们能够获知序列之间的相似关系，进而判别序列之间的同源性，推测序列之 间的进化关系。总之，对生物序列进行分析和比较是生物信息学的最基本也是最重要 的课题之一，同时对生命科学的研究具有深远的意义【卜1 0 1 。 当前，每天都有成千上万的生物数据被源源不断地输入到相应的生物信息数据库 中。据n c b i 统计，2 0 0 7 年1 0 月g e n b a n k 中的序列记录达到了7 7 ，6 3 2 ，8 1 3 ，总共包含了8 l ， 5 6 3 ，3 9 9 ，7 6 5 个碱基对。除此之外，各种二级生物数据也相继产生，如，蛋白质疏水性数 据、二级结构数据等。我们已经不觉间处于生物信息爆炸的年代。这些海量的生物数据， 需要生物科学家去处理、去认识。生物信息学以其自身独有的优势成为生命科学中极其 重要的一部分。它综合利用生物学、数学、计算机科学和信息科学等知识来分析、处理 及管理庞杂的生物学观测数据，发展计算方法，为世界的研发工作者提供理论指导和分 析手段。虽然生物信息学的发展历史并不长，但是到目前为止，它已经发展了大量独具 特色的分析方法，开发了强有力的分析软件，为生物学家获取信息提供了重要途径。计 算分子生物学的发展，将对各种物种的基因组学、新兴生物技术产业等领域的发展也产 生重大的影响。 1 2 本文的组成和主要贡献 计算分子生物学的研究对象是与基因和蛋白序列有关的组合和计算问题。本文主要 对序列相似性分析与构建系统进化树进行了深入研究，对于每种方法我们都给予了实例 验证。本论文的主要工作分为以下几部分： 2 第一章绪论 第2 章简单介绍了分子生物学的一些基础知识，包括常用的术语和基本概念都 在这里做了简要的介绍。 第3 章序列的相似性分析是许多研究工作的基础。基于序列比对的比较方法具有 较高的时间复杂度，并且比较的结果受到打分函数的影响。为此，我们应 用信息论中著名的l e m p e l z i v 压缩算法和条件l e m p e l z i v 复杂度来对序列 之间进行相似性分析来构建系统发生树，考虑氨基酸物化性质对蛋白质功 能影响的基础上对蛋白质序列作了进一步的分析。 第4 章在图形表示法分析生物大分子序列的基础之上，提出应用模糊聚类图论 k r u s k a l 算法来对系统进化树的重构方法。应用线粒体d n a 序列对此进行 验证。在前一章的基础上，对d n a 的四个碱基进行三种不同趋向的分类， 应用l e m p e l z i v 算法和条件l e m p e l z i v 算法对构建系统进化树。 最后总结本文主要贡献，并对计算分子生物学的发展趋势进行分析和预测。 第二章预备知识 本章节介绍分子生物学的一些基础知识和系统发生树构建目前较为普遍采用方法 的一些介绍。 2 1 分子生物学知识概论 分子生物学是在各门生物分支学科发展的基础上建立起来的新学科，其后随着发展 的新理论和新技术又为研究各种生物学现象鉴定了坚实的分子基础。细胞是生命的基本 单位，它是由细胞膜、细胞质和细胞核三者组成，遗传信息储存在细胞核中。细胞的分 子有两类：大分子和小分子。大分子有三种类型：d n a 、r n a 和蛋白质阎，它们是由某 些小分子聚合在一起形成的。以下主要介绍他们的结构和一些性质功能。 2 1 1 核酸 核酸( n u c l e i ca c i d ) 是生物体的基本组成物质，是遗传信息的携带者，它在生物的个 体生长、发育、繁殖、遗传和变异等生命过程中起着极为重要的作用生物体包含两类 核酸：脱氧核糖核酸( d e 幻x y r i b o n u c l e i ca c i d ) ，简写为d n a ；核糖核酸( r i b o n u c l e i ca c i d ) ， 简写为r n a 。 2 1 1 1d n a d n a 是由称为核苷酸的小分子组成的链实际上d n a 是双链，两条链缠绕在一起 形成双螺旋，此著名的双螺旋( d o u b l eh e l i x ) 结构是由j a m e sw a t s o n 和f r a n c i sc r i c k 在 1 9 5 3 年发现的。核苷酸有四种，可以用四种基来区分他们。四个基分别是，a ，c ，g ， t ，d n a 分子可以看成是四个字母字符集k = a ，c ，g ，t ) 上的词。先认识一下d n a 的单链( s t a r n d ) ，它是由重复的基本单元照一定的方式、数量和排列顺序而组成的骨架。 这种基本单元由一个称做2 脱氧核糖的糖分子和一个磷酸残基组成糖分子含有5 个 碳原子，标记为1 一5 ( 如图2 1 所示) 。形成骨架的键是在一个单元的37 碳原子和下一 个单元的5 碳原子之间因此，d n a 分子具有方向性( o r i e n t a t i o n ) ，一般从5 开始到3 结 束，左端通常记为5 ，另一端记为3 5 海南师范大学硕士学位论文 - _ - _ l - _ _ _ _ i _ - i _ - l _ _ - - i - l - - l _ - l - - - _ - _ - - _ _ l _ - _ - - i - - i - - - _ 一_ - 一一 h l h o 5 h i l h 0o h 核糖 h 般) 一5 t i h 2 脱氧核糖 图2 1 核酸中的糖，符号1 一5 表示碳原子。两种糖的唯一差别是 27 碳原子中的氧，r n a 中是核糖，d n a 中是脱氧核糖 在骨架中与17 碳原子相连的分子为碱基a s e ) 。在d n a 分子中有4 种碱基，分别 是：腺嘌呤( a d e l l i n e a ) 、鸟嘌呤( g u a d j n eg ) 、p 咆嘧啶( c y t o s i n ec ) 、胸腺嘧啶( m y i n i n e t ) 。图2 - 2 显示了每种碱基的分子结构，图2 - 3 为单链d n a 分子的示意图。 l s 一一( c a d e n i n e j c 一夕 一弋旷。 ，e 一。 r k尸 一 一吗 t h y m i n e - 圈 h - 之 陈勰o c 2 - h 巨圈nc 图2 - 2d n a 中氮化的碱基。两种w a t s o n - c rc k 配对，留意腺嘌呤与胸腺嘧啶， 鸟嘌呤与胞嘧啶之间所形成的键，图中用点线表示 6 第二章预备知识 图2 - 3 一个d n a 链分子结构的图示 5 agtgagtg 口3 图2 4 单链i ) n a 分子的简单示意图 d n a 蕴含的复制机制的关键特征是碱基互补，即a 和t 配对，g 和c 配对。这种 配对是由于氢键作用。原理是由d n a 单链( 按57 到3 的次序的简单示意图) ( 图2 _ 4 所示) 与相反方向互补的链配对( 图2 5 所示) 。 图2 - 5i ) n a 分子碱基互补图 d n a 分子是双链结构，图2 - 6 给出了双链d n a 链分子结构的图。由图2 - 6 我们能 看出，在a t 配对时，有两个氢键连接，而在g c 配对时有三个氢键连接。因此， 我们把a ，t 称为弱氢键碱基，而把g ，c 称为强氢键碱基。两条链缠绕在一起形成双 螺旋，即著名的双螺旋( d o u b l e h e l i x ) 结构。这种碱基互补配对的机制使得d n a 在细胞 中得以复制。三维结构是螺旋状，图2 7 指出这些字母或基是附在一个线上或骨架上。 掣 g 一 一 一 一 一 一 a l t a i t g l c t 1 a c l g a l t t i a 一 一 一 一 一 一 一 t s 3 海南师范大学硕士学位论文 图2 - 6 双链d n a 链分子结构的图 图中标明氢键的杠删去了，为准确地看这个图，把它想象为两个边是对应骨架的缎带拧 成一令螺旋状如图2 7 ： 2 1 1 2r n a 图2 - 7d n a 的三维结构 r n a ( r i b o n u c l e i ca c i d ) 是具有重要生物学功能的另一种核酸，r n a 分子与d n a 分 子很相似，但在组成和结构上也有一些重要的不同：( 1 ) 在r n a 分子中，核糖取代了 8 第二章预备知识 d n a 分子中的2 一脱氧核糖。( 如图2 1 所示) ( 2 ) 胸腺嘧啶t 被u ( 尿嘧啶u r a c i l ) u 与t 样能够与a 配对。( 3 r n a 并不形成双螺旋。( 4 ) r n a 能够通过碱基互补与 闻一分子的其他部分结合。 r n a 分子同样可以著作是字符集黔 a ，c ，g ，u ；上的字符搴露榉具有方向性豹， 左端通常记隽弘另端记为3 。在p , 2 q a 分予孛互替的核营酸g c 和a u 产生 w a t s o n 。- c r i c k 碱基，人稍已经根据基解析的r n a = 级结构，识别出这些碱基对和其他 一些碱基对 】。r n a 二级结构是平面图，磷酸骨架用实线表示，基用点表示，氢键或 基对表示为两个非相邻闻的线，在生物学通常的二级结构的表示中基对线与基连接。对 于a _ ：c a g c a u c a c a c c c g c o 同3 g u a a a c c 汇u 的所谓三叶革结构的个例子，见图 2 8 所示其r n a 二级结构。在图2 - 9 给出同样序列的= 级结构的表示法，初级结构沿水 平方向画出，基对用弧线表示。 c 圈2 - 8 三时草二级结构的一般裘示 e agegue 矗c ac cc ( e 嚣0go uaa 磊, eg 0u 委2 啕三蛄蕈：缀结檬半圆淡示 孽 海南雾摹范大学硕士学位论文 2 ，1 2 蛋白质 1 9 世纪中时，费兰位学家g 。m u l d e r 从植物体中提出一茅孛共有的物质，并认为这霉巾 物质在有规界是最重要的。根据瑞典化学家的建议，m u l d e r 给这种物质命名为“p r o t e i n ”， 即蛋囱质。蛋白质在生物体内占有特殊的地位。蛋白质和核酸是构成细胞内原生质 ( p r o t o p l a s m ) 的主要成分。而原生质是生命现象的物质基础。 蛋白质是由类称为氨基酸( a m i n oa c i d ) 的简单分子组成。每个氨基酸有一个中心 碳原予，谓之a 碳原子或c c 伍连接1 个氢原子( 薹壬) 、1 个氨基( - n h 2 ) 、1 个羧基( c o o h ) 和1 个r 基匿 j ，那么s ( i ，j 3 = q o 。将序y l j q 和序列r 连接起来，我们得到一个新的 序歹i j s = q r 。这时序y l j q 被称为序y u s 的前缀。如果存在一个整数i ，使得q = s ( 1 ，i ) ，那么 序y o s 被称为是序列q 的扩展。 序y l j q 的扩展序y t j s = q r 被称为是序列q 再生的，如果下面条件成立：存在一个整数 psl ( q ) ，使得r ( k ) = s ( p + k - 1 ) 对k = - i ，2 ，l ( r ) 都成立。这时我们记为q _ s 。例如，序列 a d d e f d e f 是从序歹u a d d e f 再生而来的，即a d d e f a d d e f d e f ，这时p = 3 和 a a c g t a a c g t a c ，这时p = 2 。一个非空序列s 被称为是其前缀s ( 1 4 d 可生的，如果 s ( 1 t ) 一s ( 1 以$ 一1 ) 。这时我们记为s ( 1 0 ) 令s 。例如，s c c e f 兮s c c e f c c e g ，因为存 在整数p = 2 ，使得s c c e f s c c e f c c e 。 0 wqm 岛 p r 吼b 琢e弭磊e 饼岛d = = = = 国国鹋 副s s s 舞三鬻蛋瓯爨痔粼蓉统发垒辩熊缝建 根攥上述靛定义，簌鬻一个菲空謦燕s 豢可弑款一个爵篷性遵簇建立起寒。建立 过程串戆每一个步骤，不妨浚纂i 令多骤，罄要潢是这样翡条箨：s l 趣泠s ( 1 ，攀。 遮萋溪定，謦裂酶第一令字蒋燕卷空字警哥垒懿，露警嚣s ( 1 赫燎s ( 1 ，兰。塑粜说棼空 窿裂在蜀生过糕孛经惩了辍步，并显在越过程孛，我们在每个步骤麴缝荣处做标记，那 么我们会褥捌麴下的般牲结果s ( 1 0 s ( h l ，h 2 ) s 妒一l ，k ) ，k 在数值上 等于序列s 的长度。这个一般性结果被称为是序列s 的群历史，简记为h ( s ) ，期 芰差( s 净s ( 1 ，瓤抄s ( h l h 0 s ( k l ，k ) 其中s ( h 扣一l h 沁茂( 研被称为h ( s ) 附第f 个 缀分。例如，s = a a c g t a c c ， ( s ) 舔a c - g * t * a c * c ，薹差( s ) 祛啭o g 小矗c c h ( s ) = a o