摘要：SummaryDe novogenome assembly is a fundamental problem in computational molecular biology that aims to reconstruct an unknown genome sequence from a set of short DNA sequences (orreads) obtained from the genome. The relative ordering of the reads along the target genome isnotknowna priori, which is one of the main contributors to the increased complexity of the assembly process. In this article, with the dual objective of improving assembly quality and exposing a high degree of parallelism, we present a partitioning-based approach. Our framework, BOA (bucket-order-assemble), uses a bucketing alongside graph- and hypergraph-based partitioning techniques to produce a partial ordering of the reads. This partial ordering enables us to divide the read set into disjoint blocks that can be independently assembled in parallel using any state-of-the-art serial assembler of choice. Experimental results show that BOA improves both the overall assembly quality and performance.Graphical abstractDisplay OmittedHighlights•A graph/hypergraph partitioning based method to improve assembly quality and runtime•Bucketing and graph/hypergraph partitioning to partition reads into blocks•Each block is then independently assembled using any standalone assembler•Hypergraph variant produces more precise contigs and is faster than state-of-the-art assemblersGenomics; Bioinformatics; High-performance computing in bioinformatics; Algorithms.
