目录摘要 (2)一、问题的重述 (3)二、问题的分析 (3)三、模型假设 (4)四、符号说明 (4)五、模型的建立与问题的求解 (5)5.1问题一的解答 (5)5.1.1模型的建立 (5)5.1.2模型的求解 (5)5.2问题二的解答 (5)六、模型的评价 (6)6.1模型的优点 (6)6.2模型的缺点 (6)七、模型的改进与推广 (6)7.1模型的改进 (6)7.2模型的推广 (6)八、参考文献 (6)附录 (7)基因组组装问题摘要基因组测序是生物信息学的核心，有着极其重要的应用价值。
新的测序技术大量涌现，产生的reads长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。
所以测序之前DNA分子要经过复制若干份、随机打断成短片段。
要获取整个DNA片段，需要把这些片段利用重合部分信息组织连接。
如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法是本题的关键。
本文主要研究在测序策略已知前提下，基于所获读长（reads）序列信息，如何组装出相对合理的目标基因组。
本文通过对问题进行分解，预处理相关读长（reads）数据，将问题明确为尽可能使组装序列总长度最大，从而设计了基因组组装优化算法，并根据既有数据对模型进行检验与修正。
针对问题一，首先我们查阅相关文献资料，在理解De Bruijn图核心思想的基础之上，然后根据碱基数目尽可能大及组装序列的总长度的比例尽可能大要求，确定k-mer长度为4，然后将这些k-mer片段存入de bruijn图中，让图中有边连接的k－mer 顶点之间相互错开4位或者更多的位数，将reads里面的读长序列进行两两比较并进行匹配，从而还原基因组。
针对问题二，根据对全长约为120,000个碱基对的细菌人工染色体（BAC）进行测序得出的序列，首先我们对数据进行预处理，然后采用问题一设计的算法与程序，得出拼接后完整的基因组，由于数据非常庞大，具体结果请见附录二。
生物信息学中的基因组组装技术随着技术的不断进步和数据的增长，基因组组装技术在生物信息学中扮演着越来越重要的角色。
基因组组装是一种将一系列碎片化的基因组序列拼接成完整基因组的过程，对于了解物种遗传信息和基因的功能具有极大的意义。
随着技术的进步，目前已经有了多种基因组组装技术，本文将概述这些技术的基本原理、应用范围以及优缺点。
二代测序技术组装二代测序技术由于其高通量、低成本、快速和可靠的优点成为了基因组组装领域中的主流技术。
二代测序技术主要有Illumina 和Ion Torrent两种。
Illumina测序技术Illumina是目前最常用的二代测序技术之一，采用双端读取的方式，因为其高精度、高深度、高覆盖度和低成本特点，成为了基因组组装中的主流技术。
Illumina测序技术使用一个称为bridgePCR的技术，将大量DNA分子固定在测序芯片的表面上，然后通过核少体扩增的方式在其表面上形成一个桥，这个桥上的每一处都带有一个DNA分子，然后将这个桥再通过物理隔离的方式分成小的区域，每个小的区域包含了上千万个DNA分子，然后再通过序列的方法将其读出。
Illumina测序技术的基因组组装使用了两个核心算法：de Bruijn 图和覆盖度法。
de Bruijn图是一种用于序列组装的图形化技术，将DNA序列分割成长度为k的节，每个节都可以表示为一个节点，所有相邻的节之间的距离可以表示为一个边。
通过构建de Bruijn 图，可以将基因组序列的碎片拼接为完整的序列。
覆盖度法是通过计算每个碎片所覆盖的其他碎片的比例，来决定如何将碎片拼接在一起。
对于Illumina测序技术的基因组组装来说，主要的问题是如何解决重复序列和基因组重组的问题。
重复序列往往会使得deBruijn图的复杂度增加，导致基因组组装的难度增加。
基因组重组也会导致序列的缺失和歧义的出现，从而降低基因组组装的质量。
Ion Torrent测序技术Ion Torrent是一种基于半导体芯片的二代测序技术，其主要工作原理是通过检测DNA分子扩增过程中产生的静电信号来实现DNA测序。
基因组的组装策略
基因组组装是指将测序得到的DNA片段按照其在染色体上的位置顺序拼接成完整的基因组。
基因组组装策略主要包括以下几个步骤：
1. 数据预处理：对原始测序数据进行质控和过滤，去除低质量序列和
污染物等。
2. 序列拼接：将高质量的测序片段按照它们之间的重叠区域进行拼接，形成较长的连续序列（contig）。
3. 比对与排序：将不同contig之间进行比对，找到它们在染色体上的相对位置，并根据位置信息进行排序。
4. 填补gap：由于测序技术的限制，有些区域无法被覆盖或者覆盖不足，形成了gap。
通过多种方法填补gap，如PCR扩增、克隆等。
5. 校正错误：由于测序技术本身存在误差，在组装过程中需要进行错
误校正。
常用方法包括比对、图像处理等。
6. 组装评估：通过计算N50值、连续性、完整性等指标来评估组装结果的质量和可靠性。
7. 后处理：进一步优化组装结果，并进行注释和分析。
在基因组组装中，不同的测序技术和算法会影响组装结果的质量和可靠性。
因此，在选择组装策略时需要考虑测序技术、数据量、样本来源等多个因素，并根据实际情况进行调整和优化。
