第四节DNA片段组装1、片段组装问题定义：给定一组取自特定字母表的字符串集合F，寻找一个最短的字符串s，使得F中的每一个字符串都是s的一个连续子串。这里，集合F的字符串相当于待组装的序列片段，而s则是序列片段组装的结果。（1）碱基标识错误（2）不知道片段的方向（3）存在重复区域（4）缺少覆盖2、序列片段组装模型（1）最短公共超串模型（2）重建模型设f=GCGATAG,g=CAGTCGCTGATCGTACG,则最佳的子序列比对如下-----GC-GATAG----CAGTCGCTGATCGTACG（3）多重连续区模型设F={GTAC，TAATG，TGTAA}3、序列片段覆盖图设P是OM（P）中的一条路径，A是该路径上对应片段的集合，P有A-1条边。将根据P所得到的超串记为S（P）。A的总长度、路径权值及超串的长度关系如下：‖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)取最大求最短的公共超串等价于取权值最大的哈密顿路径最短超串是否总是对应于一条路径呢？答案是肯定的定理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）对于给定的片段集合F，首先去掉那些是子串的序列，形成新的片段集合F’；（2）根据F’生成覆盖多图；（3）求权值最高的哈密顿路径，由此得到最短的公共超串；（4）最终形成组装结果。但是，如何在一个覆盖多图中找出权值最高的哈密顿路径呢？4、贪婪算法5、非循环子图方法定理3.5设S是一个目标序列，F是一个覆盖S的无子串序列片段集合，F的连接强度大于等于t（t0），则覆盖多图OM（F，t）中有一条哈密顿路径P，使超串S（P）=S。定理3.6设F是由目标序列S产生的一个序列片段集合，如果覆盖图OG（F，t）有一回路，则在S中存在一个长度至少为t的重复。定理3.7设S是一个目标序列，F是一个覆盖S的无子串序列片段集合，F的连接强度大于等于t（t0），如果S没有大于等于t长度的重复，则OG（F，t）具有一条唯一的哈密顿路径P，并且S（P）=S。设目标序列和各个片段如下：目标序列S=AGTATTGGCAATCGATGCAAACCTTTTGGCAATCACT各个片段w=AGTATTGGCAATCz=AATCGATGu=ATGCAAACCTx=CCTTTTGGy=TTGGCAATCACT（wk9y和zk3uk3x）解的长度少1个碱基THEEND