基于贪心算法与最小路径的基因组组装优化问题摘要随着人类基因组计划的实施和飞速发展，基因组测序拼接作为生物信息学的核有着极其重要的应用价值。新的测序技术大量涌现，产生的reads长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。本文通过如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法，建立数学模型来解决基因组组装问题。针对问题一，首先，利用相应的软件对原基因组G进行切割，利用全基因鸟枪法测序对切割后的短基因进行测序，得到较小的基因组Gj，通过对比多条任意i切割后相似的基因组Gj从而找出个别碱基对存在的识别错误。而对于基因组中i存在的重复片段可以通过两个read之间的DNA片段的长度满足一定的分布规律即paredendread来解决。接下来对比任意两个read1和read3是否相等，通过MATLAB软件建立nmnmnm阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。针对问题二，先把附件给出的数据提取出来导入MATLAB中，再
