生物信息学序列拼接

连接基因组序列，连接片段，连接序列，连接序列，连接序列，连接通过决定序列生成的reads短片片段，恢复原来的序列。 该问题是序列分析的最基本任务，是基因组研究成功与失败的关键，衔接结果直接影响序列标记、基因预测、基因组比较等后续任务。 基因组序列的连接也是基因组研究应解决的首要课题。 其困难不仅是大量的数据(以人类基因组序列为例，从数量为10兆级的片段中恢复长度为亿级的原始序列)，还包含高度重复的序列。 连接问题的难点，DNA序列数据具有固有的四个特点，它们也是解决实际序列连接问题的难点：1.序列存在误差2 .具有不完全独占性3 .具有序列不确定序列4 .具有重复序列干扰， 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 (以重建的fragments序列形式，复盖基因组上的连续区域)，这一contig最终指导了序列决定项目finishing阶段的实验方法，构建了DNA的完整序列。 目前，国际上对拼接软件的公认评估标准包括两个方面：重建的contig的数量和准确性。 我们发展的基因组序列新算法的目标是在确保准确性的基础上，构建尽可能少的contig，减少序列决策后期的大量人才和财力投入。 另一种是基因组拼接算法的研究现状，目前最常用的拼接算法能够分为两类：将拼接问题转换成图中寻找的Hamilton路径的问题，即在具有拼接问题的特殊情况下图的欧拉电路他们都有成功的典型算法。 此外，转化为HamiltonPath问题，DNA片段(read )相当于图中的节点，是在两个片段之间存在重复关系的情况下，在两个节点之间定义边缘，沿着DNA原始数组始终仅通过节点一次的Hamilton路径。 contig表示图中的简单路径，这样的算法以Phrap、TIGRAssembler、CAP3、GigAssemble等为代表。 遵循“overlap-layout-consensus”框架。 首先，为了构筑地图。 计算任意两个读取之间的可能归类。接着，通过去除模糊和不确定的边，得到更正确的图，在此基础上寻找不交叉的单纯的道路集合，该集合与contig的集合相对应。 最后，通过对简单路径中包含的所有read进行多序列对照，按照每个consensussequence构筑consensussequence。 2 .转换为Euler path问题。 欧拉是这种算法的代表。 与传统的OverlapLayoutConsensus课程不同，不计算每个读取之间的Overlap，没有Overlap步骤。 其大致的想法是，为了排除read中的错误，取得Error-Free的read，将所有的read切成小片n-mers。 此外，通过对每个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图。 现在算法的主要问题是，已经开发出了以上的算法，但基因组序列的连接问题尚未完全解决，以上两种算法都存在各自的缺陷。 在第一类算法中，实际上在图中寻找使评价函数值最佳化的哈密顿路径是NP完全问题。 一般使用greedy-merging算法近似求解。 由于这种step-by-step局部贪婪算法，其明显的局部特性忽略了reads之间的“长距离”或整体连接，连接错误，即连接结果与真实的DNA原始序列不同。 最近的研究指出，在流感菌基因组对已知序列的结合过程中，Phrap、TIGRAssembler、CAP3均发生了结合错误。 另外，在第二类算法中，只能在特殊情况下简化问题求欧拉回路，最终从多个欧拉回路候补中选择。 Euler算法仍存在拼接错误，结果选择过程缺乏理论依据。 Euler软件实际数据集的执行速度与第一类算法相同。 更重要的是Euler采用的算法过于独立，难以利用其他辅助生物信息，实用性和流行性大大降低。 本地搜索(LocalSearch )方法、胡杰和本地搜索方法应用于具体问题需要明确定义以下四个方面： 1 .将原始问题表示为优化问题，并定义可执行域及其可执行域上的目标函数。 2 .定义可执行域的邻域结构。 也就是说，说明满足哪个条件的两点相邻。 3 .决定在附近的搜索方法。 4 .局部极值点的处理。 在当前解点附近的所有点的目标函数值大于当前点的情况下，该点被称为局部极值点。 局部极值点是一些问题中全局最大的优势。 在其他问题上，局部极值点已经满足了解实际问题的需要。 相反，基于局部搜索的序列拼接算法的框架主要目标是在可能精确的前提下在layout阶段获得较长的contig。 具体地说，使用本地搜索算法求出数据集上近似全局的最短超串，并基于与求出的最短公共超串对应的fragment的数组关系获得 consensussegment ，1.Overlap定义， 如果一个字符串的前缀是另一个字符串的后缀，则认为这两个字符串之间存在overlap，从over-lap构建超字符串。 对于给定的字符串f和g，存在多个可能的overlap关系。 例如，在f=ACTGGGAGCAGC，g=AGCAGCTTTTACT的情况下，在它们之间存在至少两种overlap格式。此外，在我们的算法中，仅考虑两个串之间的最大overlap状况，overlap(f，g )定义为表示在f和g之间存在的多个overlap关系中包含在最长的overlap中的字符数。 在上述例子中overlap(f，g)=6. 如果f和g之间的overlap区域的长度小于m (m是足够小的正整数)，则overlap(f，g)=0。 2 .优化目标定义，对reads集合s的各个元素在其左端最初出现在超串t上的位置进行排序，沿着超串t从左到右依次读取，并且对应于序列S=sl，s2，sn。 以该字符串为要素的数组用P(S )表示。 在序列P(S )中，对于每个连续的字符串元素对si，si 1存在overlap(si，si 1)。 因此，字符串的一个排列等价于一个超字符串t和作用于其的函数overlap，是在超字符串t的长度length(t)=铿锵锵锵锵6给出的集合s中确定了ssIs的值，所以进一步寻找排列p的问题3 .在使用局部搜索方法之前定义邻域的概念。 我们被称为问题的解答。 reads集合s为具有n个要素的字符串集合，P(S )为reads集合s的所有解的集合。 定义操作rshift(i，j )，即解PP(S )，将p的第I位置的要素定义为第j位置(1iM1但是overlap(r2， r3)Overlap30，两种可能性：1. overlap4overlapoverlapoverlapoverlap 2，基于上述Neighborho