操作 设是个序列集合，成为基因组。由测序仪处理形成些小的片段， 每个片段长度在。接着去掉些稍长的和稍短的片段，将剩余的片段切成定 长的序列本题提供定长为保存在多重集合中，称中的序列为。本题 操作的具体内容不需要考虑。 操作 找个的子集，满足下列条件 给定阈值，中的上的碱基质量平均值不小于 中所有都是成功的 中的要尽可能的多。 拼接总体思路 将转化成定长的，并将这些存入图中，以备之后查 找使用。此时要设定的个重要参数是的长度。选定值之后，要将长度的 拆成个。 根据定策略，选定个初始，接下来就可以在该为结点开始搜索后 继的。搜索时采用贪婪图策略，每步选择在当时看来最优的后继，直到 满足事先设定的终止条件，结束条的拼接，接着开始下条的拼接。 直到没有合适的初始可供选择，整个拼接过程结束。 简述图的建立过程 基于图数据结构的之间对比拼接算法可概括下几个步骤。 把筛选过得序列集合作为参与比对的库 更 长 把拼接问题转化成图中的欧拉 路径问题，不断迭代得到尽可能长的序列 , 参赛队选择的题号信息与编号 选题∨ 阅卷编号 注选题在对应的题号下打∨。阅卷编号由阅卷组老师在阅卷前填写。 参赛队员信息 队员队员队员 姓名陈英豪张彦军杨哲 学号 学院经济管理学院经济管理学院经济管理学院 专业信息管理与信息 系统 工程管理工程管理 年级级级级 签名 注学院填写学校规定统的各个简称如通信学院理学院自动化学院等。年级 为入学年级如级等，队员签名签名定要手写表示遵守下面的承诺书。 承诺书 我们完全明白，在竞赛开始后参赛队员不能以任何方式包括电话电子邮件网 上咨询等与队外的任何人包括指导教师研究讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或 其他公开的资料包括网上查到的资料，必须按照规定的参考文献的表述方式在正文 引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正 基于图的基因组装算法 是个重复片段两端再加几个碱基组成。 利用解决重复片段问题需要如下两个信息是重复片段两端配对的， 这两个必须不相同二是重复片段中的个配对，只要知道个即可，另 个配对可以不在重复片段中。通过分析已知的基因组，可获得有关重复片段 的更多信息，如，重复片段的长度，重复片段的模式等。 原基因组 拼接之后 原基因组 拼接之后 原基因组 拼接之后 图 三符号约定 四数据分析与模型原理 数据分析 本题中，采用测序技术产生的数据。是目前通量最高的测序 仪器，但产生的读长较短般为本题长度为，使拼接问题变得更加 复杂。 测序仪测出的数据有如下特征 的副本较多，约为 基因组中有些位置被较多的所覆盖，有些位置被较少的覆盖，这 些位置是随机的，不可预测 每个都含有个质量值，该值能反映该的正确率。质量值越高， 的正确率越高 有些上存在个别碱基对识别，无法在比对前甄别出来。 模型原理 由于该问题比较复杂，直接由得到整个基因组想到困难，甚至是不可能的， 故需要降温题划分为几个子问题，分如下几个阶段解决 由集合构建集合 由集合构建集合 由集合构建整个基因组。 符号定义 利用现有的测序技术，可按定的测序策略获得长度约为个碱基对的序列，称为读长 由经过定算法拼接产生以内的些基因组片段 使用作为参考序列延伸，并进行合并得到更长的，即 关键词图贪婪图方法启发式搜索 问题的重述 快速和准确的获取生物体的遗传信息对生命科学研究具有重要意义。随着测序技术 的不断发展，新代测序技术产生的在高通量低成本的同时也带来了率略有则加 读长较短等缺点。本题要求利用数学模型，设计算法解决如下几个问题 测序过程中可能出现的个别碱基对识别 基因组中存在重复片段 快速的处理海量的序列比对。 二问题的分析 本题是基于新代测序技术的基因组装算法问题，要求设计算法针对性的解决新 代测序技术带来的些弊端。 长度较短，数量较多图 新代测序技术所得的长度较短，数量较多，不易发现之间的重叠关系。 可以将转化成定长的，然后寻找之间的重叠关系。然后建立 图，把短序列拼接问题转化为图中的欧拉路径问题。 个别碱基对识别多重对比纠错 通过将多个放在起比对来发现，如图所示。 图中通过途中条比对，可发现中的个碱基的第五个 碱基 图 基因组中存在大量重复片段 重复片段可能导致拼接，或者导致不连续的较短出现。重叠片段类型 主要有以下几种，如图所示 重复片段问题可以用如下问题解决通过对比，可先将重复片段隔离开来，较高的 覆盖度有利于重复片段的隔离，但是，较多的测序将不利于该过程的进行。如果重 复片段比长，可利用来解决如果重复片段比短，那么 该又被称为，个就分析 由测序策略可知，和为相互补的两条单链，故选用的数据带入 算法进行组装，可以作为校准链备用。分析文件可知，本题数据已满足如 下条件 序列片段被切成固定长度 经过复制，原基因至少有个副本 所有片段上的碱基都已经被识别出来，不存在未知碱基 由于技术限制，本文不对质量数进行讨论，假设中的所有片段满足正 确率要求。 带入模型求解 建立图 将值定为。把上述文件中的序列存入库中，开始建立条目的 数据结构和条目的数据结构。预读数据，逐条读取数据，每条进行 升序保存生成该上所有共个，统计这些出现的次数， 填写结构中的字段。如图所示，为相关代码片段。相关数据录入程序源代码 见附录。 遍历图，根据上步统计的数量，申请数组所需要 的内存空间。依次读取每个，填写数组中的第行，填好之后把 值加。 将碱基替换成位二进制数。，。 模型求解 由于数据非常庞大，演算拼接过程不能完整的展示，接下来将列举段算法拼接的 过程 初始定为即，该出现在条上，且 出现在每条上的为这四条开始参与拼接。如图为比对拼接相 关代码 此时为，为，为 初始 后继 八模型评估 模型评价 本模型针对新代测序技术出现的问题逐进行了解决。新代读长较短，不易 发现之间的重叠关系，本文放弃了传统的重叠图算法。把基因重组问题成功的转 化为图中的欧拉路径的问题，配合二分法启发式搜索法实现了在较短的时 间内对海量数据进行比对处理。 由于比赛时间限制，本模型没有对组装中可能出现的误差进行较好的规避。如上 述的基因组中出现重复片段干绕问题对于海量数据比对过程中应有的内存优化问题。 附录 源代码文件 ， 基因数据 基因数组