基于双端读数insert size统计特征的scaffolding方法

摘要

本发明公开了一种基于双端读数insert size统计特征的scaffolding方法，首先对双端读数比对到contig上的噪音进行预处理。接着构建scaffold图，图中每个节点代表一个contig；基于insert size分布估计两个节点之间比对上双端读数的期望值；再根据两个节点之间比对上双端读数的实际个数和期望值，确定两个节点之间是否存在边以及边的权重。然后采用迭代和线性规划的方法解决scaffold图中可能存在的冲突。最后利用广度优先遍历算法从scaffold图中确定scaffold。本发明简单易用，在不同的真实数据上表现出良好的scaffolding结果，较其它scaffolding方法具有更高的准确性。

主权项

一种基于双端读数insert size统计特征的scaffolding方法，其特征在于，包括以下步骤：1)首先将双端读数数据集合比对到contig上，得到比对结果；对比对结果进行预处理：1.1)对于双端读数中的每个读数，保留比对得分值最高的位置信息，删除其它位置信息；1.2)计算contig上每个碱基位置的单个读数覆盖度，如果该覆盖度大于该contig上所有碱基位置的平均读数覆盖度的k倍，则删除比对到该碱基位置的所有双端读数信息；其中2≤k≤4；1.3)删除不符合insert size统计特征的双端读数的比对信息；insert size统计特征是指insert size服从正态分布N(μ_is,σ_is)，其中μ_is为均值，σ_is为标准差；比对到同一条contig上的双端读数的insert size需要在[μ_is‑3*σ_is,μ_is+3*σ_is]这一区间，否则删除该双端读数的比对信息；2)根据保留下来的比对结果，构建带权重的scaffold图，图中每个节点代表一个contig；并利用insert size分布估计两个节点之间比对上双端读数的期望值；再根据两个节点之间比对上双端读数的实际个数和期望值，确定两个节点之间是否存在边以及边的权重；3)确定scaffold图中的冲突，并移除造成冲突的边：根据双端读数比对到两个节点上的位置和方向，确定两个节点之间的距离，及两个节点是否在同一个方向上，也就是说，在scaffold图中每条边约束了两个节点之间的距离，以及两个节点是否方向一致；移除部分边来保证scaffold图中不存在距离和方向冲突，以移除边的权重之和最小为优化目标，进行冲突发现和移除；4)生成scaffold集合；根据节点的长度，把scaffold图中的节点分为长节点和短节点；首先，抽取出只包含长节点的简单路径集合，将这些简单路径集合作为初始的scaffold集合；其次，如果一个短节点和scaffold中两个相邻的长节点都存在边，则把该短节点插入到两个长节点中间，形成新的scaffold；如果在两个相邻的长节点中，存在多个短节点和它们相连，则先根据短节点和长节点的距离由小到大对短节点进行排序，再按顺序把短节点插入到长节点之间，形成新的scaffold；最后，选择一个scaffold从其末端节点出发，基于scaffold图进行广度优先遍历，并把遍历的节点合并到当前scaffold，对scaffold进行扩展；当遇到另一个scaffold的末端时，合并这两个scaffold；当没有其它节点可以扩展时，则停止该scaffold的遍历；输出scaffold集合。