基因组序列拼接序列拼接拼接问题的难点1．测序有误差由于测序技术的局限，难免会出现测序错误，尤其是在序列的末端，一般错误率可控制在1％以下。所以对每个碱基一般有一个正确概率，以质量打分的形式给出。因此每个ri都有个可信度。而read与read之间有不同程度的重叠，由此导致有的重叠可信度高，有的重叠可信度低。2．不完全覆盖性不是所有的碱基被测序的次数都等于平均测序覆盖度。极端的情况，可能会出现源基因组序列上部分区域未被测序的情况(这段区域称为gap)。即，测序的reads集合不是原始基因组序列一个完整覆盖。此时需要借助于各种图谱如：基因组指纹图谱(genomefingerprintmap)，基因组级物理图谱(genome-widephysicalmap)，细胞发生图谱(cytogeneticmaps)等协助对reads进行定位．3．序列所在链不确定由于测序过程中无法确定特定片断属于DNA双链中的哪一条链上，所以我们在拼接过程中并不清楚使用的是read的正义链，还是其互补链。4．重复序列的干扰DNA序列自身含有高度重复的子序列，它们一种表现为短序列的串级重复，比如：(GGAA)n。或AmTn等。另一种表现为大量相似序列(其拷贝数可达几十万)散布在基因组的各个地方。Repeat的存在，将导致fragments间overlap的不真实性，进而产生错拼的结果。因此在拼接过程中耍确定这些序列的形式及大小，才能保证以高概率恢复出其在原始真实序列中的位置．拼接算法评价目前，国际上对拼接软件的公认评价标准包括两方面，即重建出的contig的数目和准确度。我们发展的基因组序列拼接新算法的目标是在确保准确性的前提下，构建尽量少的contig，以减少测序后期大量的人力和财力的投入。基因组序列拼接算法研究现状1.转化为HamiltonPath问题他们都是遵循“overlap-layout-consensus”的框架。首先，为了构建图。计算任意两个read间可能的比对情况。其次，通过去除歧义的或者不确信的边得到较为准确的图，并在其上寻找非交叉的简单路的集合，该集合对应于contig的集合。最终，通过对包含在一个简单路上的所有read进行多序列比对，为每一个contig构建一个一致性序列(consensussequence)。2.转化为EulerPath问题将每个read和Gk的近似进行比对，寻求read的最小改变能够使得read的所有n-mers包含在Gk的近似集合中。从而构建了高质量序列，而对于Poorread，直接抛弃，对Chimericread(两端在n-mers中但整体不在的reads)进行特殊处理。初始的想法是要实现去除reads中的测序错误的目的，如果知道原始序列G，那么直接使用测序获得的read和G进行比较即可。但是实际上G并不可知，那么退而求其次，G的序列片断Gk亦可，事实上Gk亦不可知。所以将所有的read切割成小片n-mers，所有Solid的n-mers形成的集合称为Gk的近似。最后，构造DeBruijn图。现有算法的主要问题对于第一类算法来说，实际上是在图中寻找一条使得评价函数值最优的Hamilton路径，这是一个NP完全问题。一般都采用greedy-merging的算法近似求解。由于这种step-by-step的局部贪心算法，其明显的局部特性忽略了reads间“长距离”或者整体性的联系，从而导致了拼接错误，即拼接结果和真实的DNA原始序列不同。最近研究指出，在对已知序列的流行性感冒嗜血杆菌基因组的拼接过程中，无论是Phrap，TIGRAssembler，还是CAP3，都发生了拼接错误的现象。对于第二类算法来说，它只能在特殊的情况下，才能将问题简化成寻求一条Euler路径，最终的结果是从多条候选的Euler超路中选择出来的。EULER算法依然存在拼接错误，且结果选择的过程没有理论依据。EULER软件在实际数据集的运行速度上和第一类算法相当。更重要的是，EULER采用的算法过于独立，很难利用其他辅助生物信息，导致其实用性和流行性大打折扣。局部搜索(LocalSearch)方法将局部搜索方法运用于一个具体的问题，需要对以下四项进行明确的定义。1．将原同题表示成一个优化问题，即定义一个可行域以及在该可行域上的一个目标函数。2．定义可行域中的邻域结构，即说明满足什么条件的两个点相邻。3．确定在邻域中的搜索方式。4．局部极值点的处理。如果当前解点邻域中的所有点的目标函数值都比当前点大，那么这点就称为局部极值点。在一些问题中，局部极值点就是全局最优点。而对另一些问题而言，局部极值点已经满足求解实际问题的需求。基于局部搜索的序列拼接算法框架1.Overlap定义在我们的算法中，仅考虑两个串之间最大的over