Bhowmik Oieswarya, Rahman Tazin, Kalyanaraman Ananth
School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA, 99164, USA.
BMC Bioinformatics. 2024 Aug 8;25(1):263. doi: 10.1186/s12859-024-05878-4.
Genome assembly, which involves reconstructing a target genome, relies on scaffolding methods to organize and link partially assembled fragments. The rapid evolution of long read sequencing technologies toward more accurate long reads, coupled with the continued use of short read technologies, has created a unique need for hybrid assembly workflows. The construction of accurate genomic scaffolds in hybrid workflows is complicated due to scale, sequencing technology diversity (e.g., short vs. long reads, contigs or partial assemblies), and repetitive regions within a target genome.
In this paper, we present a new parallel workflow for hybrid genome scaffolding that would allow combining pre-constructed partial assemblies with newly sequenced long reads toward an improved assembly. More specifically, the workflow, called Maptcha, is aimed at generating long scaffolds of a target genome, from two sets of input sequences-an already constructed partial assembly of contigs, and a set of newly sequenced long reads. Our scaffolding approach internally uses an alignment-free mapping step to build a contig,contig graph using long reads as linking information. Subsequently, this graph is used to generate scaffolds. We present and evaluate a graph-theoretic "wiring" heuristic to perform this scaffolding step. To enable efficient workload management in a parallel setting, we use a batching technique that partitions the scaffolding tasks so that the more expensive alignment-based assembly step at the end can be efficiently parallelized. This step also allows the use of any standalone assembler for generating the final scaffolds.
Our experiments with Maptcha on a variety of input genomes, and comparison against two state-of-the-art hybrid scaffolders demonstrate that Maptcha is able to generate longer and more accurate scaffolds substantially faster. In almost all cases, the scaffolds produced by Maptcha are at least an order of magnitude longer (in some cases two orders) than the scaffolds produced by state-of-the-art tools. Maptcha runs significantly faster too, reducing time-to-solution from hours to minutes for most input cases. We also performed a coverage experiment by varying the sequencing coverage depth for long reads, which demonstrated the potential of Maptcha to generate significantly longer scaffolds in low coverage settings ( - ).
基因组组装涉及重建目标基因组，它依赖于支架搭建方法来组织和连接部分组装片段。长读长测序技术朝着更准确的长读长快速发展，再加上短读长技术的持续使用，催生了对混合组装工作流程的独特需求。由于规模、测序技术多样性（例如，短读长与长读长、重叠群或部分组装）以及目标基因组内的重复区域，混合工作流程中准确基因组支架的构建变得复杂。
在本文中，我们提出了一种用于混合基因组支架搭建的新并行工作流程，该流程允许将预先构建的部分组装与新测序的长读长相结合，以实现改进的组装。更具体地说，这个名为Maptcha的工作流程旨在从两组输入序列——一组已经构建好的重叠群部分组装和一组新测序的长读长——生成目标基因组的长支架。我们的支架搭建方法在内部使用了一个无比对映射步骤，以长读长作为连接信息构建重叠群-重叠群图。随后，这个图用于生成支架。我们提出并评估了一种图论“布线”启发式方法来执行这个支架搭建步骤。为了在并行设置中实现高效的工作负载管理，我们使用了一种批处理技术，对支架搭建任务进行分区，以便在最后更昂贵的基于比对的组装步骤能够有效地并行化。这一步骤还允许使用任何独立的组装器来生成最终支架。
我们使用Maptcha对各种输入基因组进行的实验，以及与两种最先进的混合支架搭建工具进行比较，结果表明Maptcha能够显著更快地生成更长、更准确的支架。在几乎所有情况下，Maptcha生成的支架比最先进工具生成的支架至少长一个数量级（在某些情况下长两个数量级）。Maptcha运行速度也明显更快，对于大多数输入情况，将解决问题的时间从数小时缩短到了数分钟。我们还通过改变长读长的测序覆盖深度进行了覆盖实验，这证明了Maptcha在低覆盖设置下生成明显更长支架的潜力（-）。
