Key Lab of Intelligent Information Processing, Big-Data Academy, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100190, China.
Institute of Biology, University of Chinese Academy of Sciences, Beijing, 100049, China.
BMC Bioinformatics. 2021 Oct 30;22(1):533. doi: 10.1186/s12859-021-04448-2.
Optical maps record locations of specific enzyme recognition sites within long genome fragments. This long-distance information enables aligning genome assembly contigs onto optical maps and ordering contigs into scaffolds. The generated scaffolds, however, often contain a large amount of gaps. To fill these gaps, a feasible way is to search genome assembly graph for the best-matching contig paths that connect boundary contigs of gaps. The combination of searching and evaluation procedures might be "searching followed by evaluation", which is infeasible for long gaps, or "searching by evaluation", which heavily relies on heuristics and thus usually yields unreliable contig paths.
We here report an accurate and efficient approach to filling gaps of genome scaffolds with aids of optical maps. Using simulated data from 12 species and real data from 3 species, we demonstrate the successful application of our approach in gap filling with improved accuracy and completeness of genome scaffolds.
Our approach applies a sequential Bayesian updating technique to measure the similarity between optical maps and candidate contig paths. Using this similarity to guide path searching, our approach achieves higher accuracy than the existing "searching by evaluation" strategy that relies on heuristics. Furthermore, unlike the "searching followed by evaluation" strategy enumerating all possible paths, our approach prunes the unlikely sub-paths and extends the highly-probable ones only, thus significantly increasing searching efficiency.
光学图谱记录了长基因组片段中特定酶识别位点的位置。这种长距离信息可用于将基因组组装 contigs 比对到光学图谱上，并将 contigs 排序到支架中。然而，生成的支架通常包含大量的缺口。为了填补这些缺口，可以通过在基因组组装图中搜索最佳匹配的 contig 路径来连接缺口的边界 contigs。搜索和评估过程的组合可能是“先搜索后评估”，对于长缺口来说是不可行的，或者是“通过评估进行搜索”，这严重依赖于启发式方法，因此通常会产生不可靠的 contig 路径。
我们在这里报告了一种利用光学图谱填补基因组支架缺口的准确高效方法。使用来自 12 个物种的模拟数据和来自 3 个物种的真实数据，我们展示了该方法在缺口填补方面的成功应用，提高了基因组支架的准确性和完整性。
我们的方法应用了一种顺序贝叶斯更新技术来测量光学图谱和候选 contig 路径之间的相似度。利用这种相似度来指导路径搜索，我们的方法比依赖启发式的现有“通过评估进行搜索”策略具有更高的准确性。此外，与枚举所有可能路径的“先搜索后评估”策略不同，我们的方法仅修剪不太可能的子路径，并扩展高度可能的路径，从而显著提高搜索效率。
