论文部分内容阅读
测定基因组序列可以帮助人类认知生物体的生命规律,从而对农业,医学,环境等领域产生深远的影响;然而受限于测序技术,测序仪每次只能读出基因组上的一个短片段,而不是一次读出完整的基因组序列。因此,从短片段中恢复出完整基因组序列(即拼接)是生物信息学的一个基本问题。 测序技术的不断发展,给基因组序列拼接带来了新的可能,也带来了新的挑战。第三代的测序数据具有读段(reads,即测序仪测得的碱基序列片段)长、错误率高(ins/del错误多)的特点,其长读段给解决拼接问题中的难题-重复序列带来了希望;但是因为其高错误率,所以要想直接使用三代数据进行拼接,则需要较高的测序深度,导致测序成本很高。与之相反,二代测技术可以产生准确率高的、短的读段。因此,使用三代(低测序深度)和二代测序数据进行联合拼接,具有低花费、高质量的优势。 本文提出了一种新的二、三代测序数据联合的拼接算法,开发了拼接器ARCS23,主要思想是:先用已有的二代拼接软件对二代数据进行拼接,得到拼接图,再将该图分解成若干个小的局部拼接图;并行地将三代数据联配到局部拼接图上,给图中的边加权,对每个局部拼接图选择最重路径进行简化,对最重路径中最后一个结点重新建局部拼接图并简化,得到一些最重路径相连的contigs路径;检查这些contigs路径的覆盖和连接情况,并做去覆盖、连路径的操作;联配三代数据与contigs路径,从而指导contigs路径的先后顺序,得到最后的拼接结果。 本文的创新点主要有: (1)提出了划分拼接图的思想,对比直接处理复杂的拼接图,该方法简便可行,同时,划分后的局部拼接图可以并行处理,大大降低了程序的运行时间; (2)引入最重路的思想简化局部拼接图; (3)充分利用了拼接图的连接信息。 实验结果表明,ARCS23可以部分解决了仅用二代数据无法解决的重复序列的问题,使拼接结果长度大大增加。与SSPACE-LongRead和HyBridPBcR的对比实验表明:在二代拼接结果好的情况下,ARCS23的长度和准确率上都有很大的优势,而且ACRCS23不需要高的三代的测序深度,从而有效降低了成本。