[发明专利]核酸序列拼接方法及装置

摘要

本发明公开了一种核酸序列拼接方法及装置，包括接收测序序列，测序序列包括读段和测通数据；根据读段构建原始拼接图；将测通数据比对到原始拼接图的边上；从原始拼接图的边集中选择锚点边；构建以锚点边为中心的局部子图；化简局部子图，在化简结果中重复选择锚点边进行处理直至不存在新的锚点边；对处理后剩余的局部子图进行合并，将合并结果作为拼接结果输出。依据本发明的方法，通过将测通数据比对到由读段构建得的原始拼接图，从中选择出锚点边并据此构建局部子图，再通过对局部子图的化简和合并得到更长的路径，达到解决锚点边之间的重复序列的路径选择问题，进而可完成测序序列的拼接任务，为提升scaffold构建效果提供可能。

主权项

一种核酸序列拼接方法，其特征在于，包括：接收测序序列，所述测序序列包括读段和测通数据；根据所述读段构建原始拼接图；将所述测通数据比对到所述原始拼接图的边上；从原始拼接图的边集中选择锚点边，所述锚点边的两端没有分叉且跨过该锚点边的读段的路径没有冲突；构建以所述锚点边为中心的局部子图；化简所述局部子图，在化简结果中重复选择锚点边进行处理直至不存在新的锚点边；对处理后剩余的局部子图进行合并，将合并结果作为拼接结果输出；从原始拼接图的边集中选择锚点边这一步骤包括：根据比对结果和拓扑结构，去除原始拼接图中含有测序错误的读段及该读段关联的所有边；根据原始拼接图的边集中各条边的边覆盖深度信息和边末端分叉信息，从原始拼接图的边集中确定出各边的类型；选择原始拼接图的边集中的非错误边和非重复边作为锚点边。