基于贪心算法与短路径的基因组组装最优拼接问题---1411.doc

基于贪心算法与最小路径的基因组组装优化问题 摘要 随着人类基因组计划的实施和,通过对比多条任意切割后相似的基因组从而找出个别碱基对存在的识别错误。而对于基因组中存在的重复片段可以通过两个read之间的DNA片段的长度满足一定的分布规律即pared end read来解决。 接下来对比任意两个和是否相等，通过MATLAB软件建立nm阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。 针对问题二，先把附件给出的数据提取出来导入MATLAB中，再结合问题一给出的模型对基因组进行重组，从而得到新的基因。 最后，基于对的研究， 关键词：基因组组装 全基因鸟枪法测序 贪心算法 最短路径 一、 问题的重述 1.1问题背景 快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。 1.2问题提出 确定基因组碱基对序列的过程称为测序（sequencing）。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为 ATACCTTGCTAGCGT GCTAGCGTAGGTCTGA 则有可能基因组序列中包含有ATACCTTGCTAGCGTAGGTCTGA这一段。当然，由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的（多条）序列长度尽可能长；完整性要求组装序列的总长度占基因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。 利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。 具体解决问题如下： 问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。 问题二：现有一个全长约为120,000个碱基对的细菌人工染色体BAC）， 采用Hiseq2000测序仪equencing depth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。 二、 问题分析 2.1 问题一分析 本题要求我们的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。故在下列分别对个别碱基识别错误和基因组中存在重复片段进行分析。 2.1.1个别碱基对识别错误分析 read 中每一个碱基都有一个质量值，来表示该碱基被正确测出的概率。一 般来说，5端的碱基正确的概率较大，而 3端 1 到 3 个碱基可能是错误的。这就要求拼接软件在拼接时能够纠错，但是，可纠错的软件也可能把正确的碱基当作错 误来纠正。所以不仅要求拼接软件在拼接时能够纠错，尽可能多的发现真正的错误，而且要求拼接软件尽可能少的将正确的碱基识别成错误的。 2.1.2基因重复片段分析 基因组中存在大量重复片段，重复片段可能导致拼接错误，或者导致不连续的较短contig出现。重叠片段类型主要有以下几种，如下图所示。 图1 基因组重叠片段类型图 2.2问题二分析 本题题目提供全长约为120,000个碱基对的细菌人工染色体，采用新一代的Hiseq2000测序仪进行测序。附件提供了筛选好的定长reads数据文件。先