《第四章序列分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章序列分析精选文档.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章序列分析本讲稿第一页，共六十二页第三节第三节 序列多重比对序列多重比对本讲稿第二页，共六十二页目的：目的：发现多个序列的共性发现多个序列的共性 发现与结构和功能相关的保守序列片段发现与结构和功能相关的保守序列片段设：有设：有k个序列个序列s1,s2,.,sk，每个序列由同一个字，每个序列由同一个字母表中的字符组成，母表中的字符组成，k大于大于2。通过插入操作，使得各序列达到一样的长度。通过插入操作，使得各序列达到一样的长度。本讲稿第三页，共六十二页1、SP（Sum-of-Pairs）模型）模型评价多重序列比对的结果评价多重序列比对的结果本讲稿第四页，共六十二页按照每个对比的列进行打分，然
2、后加和按照每个对比的列进行打分，然后加和处理每一列：处理每一列：k个变量的打分函数个变量的打分函数 用一个用一个k维数组来表示该显式函数（类似于打分矩阵）维数组来表示该显式函数（类似于打分矩阵）期望：期望：函数在形式上应该简单函数在形式上应该简单具有统一的形式具有统一的形式不随序列的个数而发生形式变化不随序列的个数而发生形式变化 本讲稿第五页，共六十二页其中，c1,c2,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。逐对加和逐对加和SP（sum-of-pairs）函数）函数 逐对计算逐对计算p(1,2)，p(1,3)，.，p(1,8)，p(2,3)，p(2,4)，.，p(2,8)，
3、.，p(7,8)的所有得分的所有得分（-7-6-5-4-3-2-1）+2=-26 本讲稿第六页，共六十二页另一种计算方式：先处理每一个序列对另一种计算方式：先处理每一个序列对在处理序列对时，逐个计算字符对，最后加和在处理序列对时，逐个计算字符对，最后加和则则SP得分模型的计算公式如下：得分模型的计算公式如下：是一个多重比对是一个多重比对 ij是由是由 推演出来的序列推演出来的序列s i 和和s j的两两比对的两两比对 本讲稿第七页，共六十二页本讲稿第八页，共六十二页2、多重比对的动态规划算法、多重比对的动态规划算法 多重序列比对的最终目标是通过处理得到一个得分最高多重序列比对的最终目标是通过处
4、理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异似性和差异。本讲稿第九页，共六十二页前趋节点的个数等于前趋节点的个数等于2k-1 本讲稿第十页，共六十二页 假设以k维数组A存放超晶格，则计算过程如下：a 0,0,0 =0 a i =max a i-b +SP-score(Column(s,i,b)(3-37)(3-38)if bj=1if bj=0本讲稿第十一页，共六十二页图3.17 三维晶格节点计算依赖关系问题：问题：计算量巨大计算量巨大时间复杂度为时间复杂度为O(2k i=1,.,k si)O(2kNk)本
5、讲稿第十二页，共六十二页3、优化计算方法优化计算方法标准动态规划算法存在的问题：标准动态规划算法存在的问题：搜索空间大搜索空间大剪枝技术：将搜索空间限定在一个较小的区域范围剪枝技术：将搜索空间限定在一个较小的区域范围内。内。若问题是搜索一条得分最高（或代价最小）的路径，则若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下限（或累积代在搜索时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。再搜索当前路径的后续空间。本讲稿第十三页，共六十二页经过特定断
6、点的最优比对算法：经过特定断点的最优比对算法：设有两条序列设有两条序列s、t，已知它们的两个断点分别是，已知它们的两个断点分别是i、j经过特定断点（经过特定断点（i、j）的最优比对可分为两个部分：）的最优比对可分为两个部分：0:s:i 与与 0:t:j的最优比对的最优比对 i:s:m与与j:t:n的最优比对的最优比对序列S:序列t:ji 本讲稿第十四页，共六十二页为了得到特定断点的最优比对，用两个矩阵为了得到特定断点的最优比对，用两个矩阵A和和B ai,j=sim(0:s:i ,0:t:j)bi,j=sim(i:s:m,j:t:n)矩阵矩阵A的计算和标准算法一样的计算和标准算法一样 矩阵矩阵B
7、的计算则是反方向的，即先对的计算则是反方向的，即先对B的最后一行和最后一列进行初始化，的最后一行和最后一列进行初始化，然后反向推进到（然后反向推进到（0，0）。）。矩阵矩阵A与与B的和的和C=A+B包含了在特定断点（包含了在特定断点（i、j）的最优比对得分。）的最优比对得分。称称C矩阵为总得分矩阵，而矩阵为总得分矩阵，而A、B分别是前缀和后缀的得分矩阵。分别是前缀和后缀的得分矩阵。根据根据C的最大值，可非常容易地找出最优比对所对应的路径。的最大值，可非常容易地找出最优比对所对应的路径。本讲稿第十五页，共六十二页-ATTCGGGATTC-（c）图 （a）前缀矩阵；（b）总得分矩阵；（c）最优比对
8、（a）（b）本讲稿第十六页，共六十二页定理定理3-1：设是关于s1,s2,.,sk的最优比对，如果SP-score()L，则 score(ij)Lij 其中 Lij=L-(sim(sx,sy)xy,(x,y)(i,j)分析一个节点是否处于可能最有路径上分析一个节点是否处于可能最有路径上即判断一个节点是否是相关的即判断一个节点是否是相关的 判断依据：判断依据：C=A+B 元素的值元素的值超晶格中的一个节点超晶格中的一个节点 i=(i1,i2,ik)如果对于所有的如果对于所有的1 x y k，i 满足满足cxyix,iy Lxy 则则 i 是相关的是相关的 本讲稿第十七页，共六十二页4、星形比对、
9、星形比对星形比对的基本思想是：在给定的若干序列中，选择一个核心序星形比对的基本思想是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对列，通过该序列与其它序列的两两比对形成所有序列的多重比对，从而使得，从而使得 在核心序列和任何一个其它序列方向的投影是最优在核心序列和任何一个其它序列方向的投影是最优的两两比对。的两两比对。利用标准的动态规划方法求出所有利用标准的动态规划方法求出所有si和和sc的最优两两比对的最优两两比对时间为时间为O（kn2）将这些两两比对聚集起来将这些两两比对聚集起来并采用并采用“只要是空白，只要是空白，则永远是空白则永远是空白”的
10、原则。的原则。本讲稿第十八页，共六十二页scs1s2sk(sc,s1)(sc,s2)(sc,sk)两两比对两两比对 多重比对多重比对本讲稿第十九页，共六十二页如何选择核心序列？尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。另一种方法是计算所有的两两比对，取下式值最大的一个：sim(si,sc)本讲稿第二十页，共六十二页例如，有5个序列：s1=ATTGCCATT s2=ATGGCCATT s3=ATCCAATTTT s4=ATCTTCTT s5=ACTGACCsc=s1ATTGCCATT ATTGCCATT-ATTGCCATT ATTGCCATTATGGCCATT
11、 ATC-CAATTTT ATCTTC-TT ACTGACC-ATTGCCATT-ATGGCCATT-ATC-CAATTTT ATCTTC-TT-ACTGACC-本讲稿第二十一页，共六十二页引理引理3.1：对于所有的1i，jk，,ij,有dc(si,sj)D(si,sc)+D(sc,sj)（3-43）定理定理3.2（3-44）星形比对是一种近似的方法，可以证明，用该方法所得星形比对是一种近似的方法，可以证明，用该方法所得到多重序列比对的代价不会大于最优多重序列比对代价的到多重序列比对的代价不会大于最优多重序列比对代价的两倍两倍 本讲稿第二十二页，共六十二页5、树形比对、树形比对k个待比对的序列
12、个待比对的序列 具有具有k个叶节点的树个叶节点的树每个叶节点对应一个序列每个叶节点对应一个序列将序列赋予树的内部节点，可以计算树中每个分支的权值。将序列赋予树的内部节点，可以计算树中每个分支的权值。权值代表对应分支连接的两个序列之间的相似性。权值代表对应分支连接的两个序列之间的相似性。所有权值的和就是这棵树所有权值的和就是这棵树寻找一种树的内部节点序列赋予方式，使得树的得分最大。寻找一种树的内部节点序列赋予方式，使得树的得分最大。本讲稿第二十三页，共六十二页将将CT、CG、CT分别赋予节点分别赋予节点x、y、z，则树的得分为，则树的得分为8。这里假设如果这里假设如果a=b，则，则p(a,b)=
13、1，否则否则p(a,b)=0，p(a,-)=-1。CTCGCT多重序列比对多重序列比对 两两序列比对两两序列比对 合并两个比对（比对的比对）合并两个比对（比对的比对）本讲稿第二十四页，共六十二页Alignment of alignments,AA算法算法 假设假设：有两个多重序列比对：有两个多重序列比对 1、2，1代表序列代表序列s1、s2、si的多重比对，的多重比对，2代表序列代表序列t1、t2、tj的多重比对，的多重比对，（s1，s2，si）（t1，t2，tj）=代表代表s1和和t1的两两比对，则计算与的两两比对，则计算与 相一致的相一致的 1和和 2比对的算法如下比对的算法如下：（1）标
14、定）标定 1的各列，如果的各列，如果s1在比对中对应位置的编辑操作不是插入在比对中对应位置的编辑操作不是插入或删除，则这些列分别标记为或删除，则这些列分别标记为s1对应位置上的字符对应位置上的字符a1、a2、als1（ls1为序列为序列s1的长度）；的长度）；（2）标定）标定 2的各列，如果的各列，如果t1在比对中对应的位置编辑操作不是插入或在比对中对应的位置编辑操作不是插入或删除，则这些列分别标记为删除，则这些列分别标记为t1对应位置上的字符对应位置上的字符b1、b2、blt1（lt1为为序列序列t1的长度）；的长度）；（3）对）对a1、a2、als1和和b1、b2、blt1进行比对；进行比
15、对；（4）在所得到的比对中，对于）在所得到的比对中，对于 1、2和和 中原来有插入或删除操作中原来有插入或删除操作的位置，恢复其原有的实际字符或空位字符的位置，恢复其原有的实际字符或空位字符“-”。本讲稿第二十五页，共六十二页例：例：1:s1 -H-LVV 2:t1 L-HCLV ：s1 -H-LVV s2 G-VLVC t2 VLHCL-t1 LHCLV-s3 GN-LVVAA算法的输出为-H-LVV-G-VLVG-GN-LVVL-HC-LV-V-HC-L分别对第1、2列和4、5列进行压缩，则最后结果为HLVVGVLVGGNLVVLHCLV-VHCL-本讲稿第二十六页，共六十二页对于对于n个
16、序列的树形比对的基本算法过程如下：个序列的树形比对的基本算法过程如下：（1）初始化，对于每个序列，生成一个叶节点）初始化，对于每个序列，生成一个叶节点（2）利用）利用AA算法合并两个节点，形成一个新节算法合并两个节点，形成一个新节 点，合并的结果放在新节点中，原来的两点，合并的结果放在新节点中，原来的两 个节点作为新节点的子节点个节点作为新节点的子节点（3）反复执行（）反复执行（2），直到形成），直到形成n个叶节点的树个叶节点的树 根为止，根节点中的序列即为最终的多重根为止，根节点中的序列即为最终的多重 比对结果。比对结果。s1 s2 s3 s41 12 2本讲稿第二十七页，共六十二页6、其它
17、多重序列比对算法、其它多重序列比对算法一般渐进式比对方法所采用的过程：一般渐进式比对方法所采用的过程：（1）先将多个序列进行两两比对，基于这些比较，）先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映每对序列的计算得到一个距离矩阵，该矩阵反映每对序列的关系；关系；（2）利用距离矩阵，建立一棵利用距离矩阵，建立一棵“相关树相关树”；（3）从最接近的一对序列出发，逐步归并形成比）从最接近的一对序列出发，逐步归并形成比对的聚类，直到所有序列处理完。对的聚类，直到所有序列处理完。本讲稿第二十八页，共六十二页例：例：(LYCES,SPIOL 84),(YEAST,(XENLA,(R
18、AT,MOUSE 96),HUMAN 83),CHICK71)66),DROVI 58)本讲稿第二十九页，共六十二页相关树相关树本讲稿第三十页，共六十二页多序列比对多序列比对本讲稿第三十一页，共六十二页目前使用最广泛的多重序列比对程序是ClustalW ClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映了每对序列的关系 EBI的CLUSTALW网址是：http:/www.ebi.ac.uk/clustalw/本讲稿第三十二页，共六十二页本讲稿第三十三页，共六十二页7、统计特征分析、统计特征分析对于所得到的多重序列比对，我们往往需要进行
19、归纳分析，总结这些对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示序列的特征，或者给出这些序列共性的表示 HLVVGVLVGGNLVVLHCLV-VHCL-（1）保守序列）保守序列表示序列每个位置上最可能出现的字符（或者所有可能出现表示序列每个位置上最可能出现的字符（或者所有可能出现的字符）的字符）ATNTSC (N-A,T,C,G;S-G,C)本讲稿第三十四页，共六十二页（2）特征统计图（）特征统计图（Profile）令令P=(P1,P2,PL)，P表示在表示在 的每一列上各种的每一列上各种字符出现的概率分布字符出现的概率分布Pj=(pj0,
20、pj1,pj|A|)A代表字母表，代表字母表，Pjk代表字母表代表字母表A中第中第k个字符在第个字符在第 j 列列出现的概率。出现的概率。第第0个字符是特殊的空位符号个字符是特殊的空位符号“-”。本讲稿第三十五页，共六十二页ATTATAACTTCTTATACTTTAGAAT 1 2 3 4 5 (位置位置)A 0.8 0.2 0.2 0.6 0.0 T 0.0 0.4 0.6 0.4 1.0 C 0.2 0.2 0.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （碱基）（碱基）本讲稿第三十六页，共六十二页利用保守序列或者特征统计图可以判断一个序列是否满足一定的特征利用保守序列
21、或者特征统计图可以判断一个序列是否满足一定的特征给定一个序列s=a1a2am，定义字符a在第j位的代价为 其中，|A|代表字母表A的长度，Ak代表A的第k个字符，特别地A0代表空缺字符“-”。整个序列s的代价为一条序列与特征统计图相对照，如果代价值小，说明该序列具有相一条序列与特征统计图相对照，如果代价值小，说明该序列具有相应的特征，否则该序列不具备相应的特征。应的特征，否则该序列不具备相应的特征。本讲稿第三十七页，共六十二页第四节第四节 DNA片段组装片段组装大规模基因组测序大规模基因组测序得到待测序列的一系列序列片段得到待测序列的一系列序列片段这些序列片段覆盖待测序列这些序列片段覆盖待测序
22、列序列片段之间也存在着相互覆盖或者重叠。序列片段之间也存在着相互覆盖或者重叠。目标序列目标序列序列碎片序列碎片本讲稿第三十八页，共六十二页1、片段组装问题、片段组装问题定义：定义：给定一组取自特定字母表的字符串集合给定一组取自特定字母表的字符串集合F，寻找一个，寻找一个最短的字符串最短的字符串s，使得，使得F中的每一个字符串都是中的每一个字符串都是s的的一个连续子串。这里，集合一个连续子串。这里，集合F的字符串相当于待组装的字符串相当于待组装的序列片段，而的序列片段，而s则是序列片段组装的结果。则是序列片段组装的结果。Input Answer ACCGT -ACCGT-CGTGC -CGTGC
23、 TTAC TTAC-TACCGT -TACCGT-TTACCGTGC本讲稿第三十九页，共六十二页（1）碱基标识错误4个主要问题个主要问题 本讲稿第四十页，共六十二页（2）不知道片段的方向）不知道片段的方向 本讲稿第四十一页，共六十二页（3）存在重复区域）存在重复区域 .本讲稿第四十二页，共六十二页（4）缺少覆盖）缺少覆盖本讲稿第四十三页，共六十二页2、序列片段组装模型、序列片段组装模型序列片段组装过程：序列片段组装过程：三个步骤三个步骤（1）首先进行序列片段的两两比较，确定可能的）首先进行序列片段的两两比较，确定可能的片段之间的覆盖（或者重叠）；片段之间的覆盖（或者重叠）；（2）确定所有片段
24、统一的覆盖模式，即确定各个）确定所有片段统一的覆盖模式，即确定各个序列片段的相对位置；序列片段的相对位置；（3）最后确定片段组装结果，即确定目标序列。）最后确定片段组装结果，即确定目标序列。本讲稿第四十四页，共六十二页（1）最短公共超串模型）最短公共超串模型三种片段组装模型三种片段组装模型 给定一个字符串集合给定一个字符串集合F，求出一个最短的字符串，求出一个最短的字符串S，使得对于所有属于，使得对于所有属于F 的字的字符串符串f，S是是 f 的超串（或者的超串（或者 f 是是 S 的子串）。的子串）。设设F=ACT，CTA，AGT 则则S=ACTAGT 是是 F 的超串的超串由于由于S必须是
25、各片段严格的超串，因此不允许片段的实验误差，必须是各片段严格的超串，因此不允许片段的实验误差，各片段的方向必须是已知的。各片段的方向必须是已知的。本讲稿第四十五页，共六十二页（2）重建模型）重建模型考虑到片段的误差和未知方向的问题考虑到片段的误差和未知方向的问题近似子串近似子串假设假设f、g是代表两条序列的字符串，是代表两条序列的字符串，f 作为作为 g 近似子串的代价为近似子串的代价为：S(g)代表代表 g 所有子串的集合，所有子串的集合，d为一般编辑距离。为一般编辑距离。本讲稿第四十六页，共六十二页设设 f=GCGATAG,g=CAGTCGCTGATCGTACG,则最佳的子序列比对如下则最
26、佳的子序列比对如下-GC-GATAG-CAGTCGCTGATCGTACG设设 是一个介于是一个介于0和和1之间的数，称串之间的数，称串f 是在误差是在误差 下下S 的的近似子串近似子串，如果，如果ds(f,S)f 重建模型：给定一个字符串集合重建模型：给定一个字符串集合F，求一个最短的字符串，求一个最短的字符串S，使得对于所有属于，使得对于所有属于F的的字符串字符串f，下式成立：，下式成立：min(ds(f,S),ds(f,S)f 其中其中 f 是是 f 的反向互补串。的反向互补串。本讲稿第四十七页，共六十二页（3）多重连续区模型）多重连续区模型称一个多重序列比对是称一个多重序列比对是 t-c
27、ontig，如果其最弱连接的交叠长度，如果其最弱连接的交叠长度至少为至少为 t。如果能够根据序列片段集合。如果能够根据序列片段集合F构造一个构造一个t-contig，称，称F允许一个允许一个t-contig。多重连续区模型：给定一个片段集合多重连续区模型：给定一个片段集合F和一个整数和一个整数 t（0），），将将F分割为最小数目的子集分割为最小数目的子集Ci，1 i k，每个，每个Ci允许一个允许一个t-contig。目标序列目标序列序列碎片序列碎片不连续区域本讲稿第四十八页，共六十二页 设设 F=GTAC，TAATG，TGTAA 本讲稿第四十九页，共六十二页3、序列片段覆盖图、序列片段覆盖图
28、覆盖多图覆盖多图OM（F）是一个有向图）是一个有向图其中图中的各个顶点代表其中图中的各个顶点代表F的一个字符串的一个字符串如果如果f、g F，并且，并且f 的的t个字符的后缀与个字符的后缀与g的的t个字符的前个字符的前缀相同缀相同，则图中存在一条权值为则图中存在一条权值为t的有向边。的有向边。产生超串的路径产生超串的路径 本讲稿第五十页，共六十二页本讲稿第五十一页，共六十二页设设P是是OM（P）中的一条路径，）中的一条路径，A是该路径上对应片段的集合，是该路径上对应片段的集合，P有有 A-1条边。条边。将根据将根据 P 所得到的超串记为所得到的超串记为S（P）。）。A的总长度、路径权值及超串的
29、长度关系如下：的总长度、路径权值及超串的长度关系如下：A=w(P)+S(P)A=a A a 是是A中序列的总长度中序列的总长度w(P)是路径是路径P权值的和权值的和 本讲稿第五十二页，共六十二页 任何一条路径对应于一个公共超串任何一条路径对应于一个公共超串一条路径是否通过图中所有的顶点？一条路径是否通过图中所有的顶点？哈密顿路径哈密顿路径 A=F 的共同超串的共同超串 S(P)=F-w(P)F是常数是常数 S(P)取最小等价于对取最小等价于对w(P)取最大取最大 求最短的公共超串等价于取权值最大的哈密顿路径求最短的公共超串等价于取权值最大的哈密顿路径 本讲稿第五十三页，共六十二页最短超串是否总
30、是对应于一条路径呢？最短超串是否总是对应于一条路径呢？答案是肯定的答案是肯定的 定理3.3 设F是一个无子串的串集合，则对于F的任何一个公共的超串S，在OM（F）中存在一条哈密顿路径P，使得S（P）是S的子序列。（与子串有区别）推论3.1 设F是一个无子串的串集合，如果S是F最短的公共超串，则在OM（F）中有一条哈密顿路径P，使得S=S（P）。引理3.2 两个等价的无子串的串集合相同。定理3.4 设F是一个串集合，则存在一个唯一的无子串集合G，使G等价于F。本讲稿第五十四页，共六十二页 根据上述的各个定理，片段组装的一般过程如下：根据上述的各个定理，片段组装的一般过程如下：（1）对于给定的片段
31、集合）对于给定的片段集合F，首先去掉那些是子串的序列，形成新的，首先去掉那些是子串的序列，形成新的片段集合片段集合F；（2）根据）根据F生成覆盖多图；生成覆盖多图；（3）求权值最高的哈密顿路径，由此得到最短的公共超串；）求权值最高的哈密顿路径，由此得到最短的公共超串；（4）最终形成组装结果。）最终形成组装结果。但是，如何在一个覆盖多图中找出权值最高的哈密顿路径呢但是，如何在一个覆盖多图中找出权值最高的哈密顿路径呢？本讲稿第五十五页，共六十二页4、贪婪算法、贪婪算法简化覆盖多图，对每一对顶点仅考虑权值最大的边，而去掉其它的边。称经过处理后的新图为F的覆盖图，记为OG（F）。贪婪算法的核心思想就是
32、逐步加入满足哈密顿路径贪婪算法的核心思想就是逐步加入满足哈密顿路径条件的最大权值的边条件的最大权值的边 无回路无回路节点出度为节点出度为1节点入度为节点入度为1 本讲稿第五十六页，共六十二页ATCACATGCAT22TGCAT ATCA CATGCATCA3CATGAG问题？问题？TGCAT ATCA CATCAGTGCATCAG ATCA期望结果期望结果TGCAT ATCA CATGAGTGCATCATCAG本讲稿第五十七页，共六十二页5、非循环子图方法、非循环子图方法利用非循环子图求解哈密顿路径利用非循环子图求解哈密顿路径 （生成节点的拓扑（生成节点的拓扑 排序）排序）给定一个序列片段集合
33、给定一个序列片段集合F和一个非负整数和一个非负整数t，在原，在原来覆盖图来覆盖图OG（F）中仅保留权值大于等于）中仅保留权值大于等于t的有向边，的有向边，形成一个新图形成一个新图OG（F，t）。）。W1 W2本讲稿第五十八页，共六十二页定理定理3.5 设S是一个目标序列，F是一个覆盖S的无子串序列片段集合，F的连接强度大于等于t（t0），则覆盖多图OM（F，t）中有一条哈密顿路径P，使超串S（P）=S。定理定理3.6 设F是由目标序列S产生的一个序列片段集合，如果覆盖图OG（F，t）有一回路，则在S中存在一个长度至少为t的重复。定理定理3.7 设S是一个目标序列，F是一个覆盖S的无子串序列片段
34、集合，F的连接强度大于等于t（t0），如果S没有大于等于t长度的重复，则OG（F，t）具有一条唯一的哈密顿路径P，并且S（P）=S。本讲稿第五十九页，共六十二页设目标序列和各个片段如下：设目标序列和各个片段如下：目标序列目标序列 S=AGTATTGGCAATCGATGCAAACCTTTTGGCAATCACT各个片段各个片段w=AGTATTGGCAATCz=AATCGATGu=ATGCAAACCTx=CCTTTTGG y=TTGGCAATCACT 本讲稿第六十页，共六十二页（wk9y 和和zk3uk3x）解的长度少解的长度少1个碱基个碱基（wk4zk3uk3xk4y）解与目标序列一样解与目标序列一样本讲稿第六十一页，共六十二页本讲稿第六十二页，共六十二页