Integrating Hi-C links with assembly graphs for chromosome-scale assembly.

Ghurye J, Rhie A, Walenz BP, Schmitt A, Selvaraj S, Pop M, Phillippy AM, Koren S. · 2019

Read Integrating Hi-C links with assembly graphs for chromosome-scale assembly. by Ghurye J, Rhie A, Walenz BP, Schmitt A, Selvaraj S, Pop M, Phillippy AM, Koren S. (2019) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc6719893.txt.

Introduction

Ghurye and co-authors present SALSA, a tool that assembles genomes to chromosome scale. New sequencing methods yield long reads, but joining them into full chromosomes is error-prone. Hi-C data, which shows which DNA parts sit near each other, can guide the joins. Open tools for this task were scarce, and errors stayed high.

SALSA uses the assembly graph, not just finished pieces, to guide its choices. It needs no advance guess of the chromosome count. Tests across Hi-C library types and assembly sizes showed fewer errors than leading methods. The code is free in Python and C++, at a public address given in the paper.

Catalog record

CREATORGhurye J, Rhie A, Walenz BP, Schmitt A, Selvaraj S, Pop M, Phillippy AM, Koren S.
YEAR2019
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
LICENSECC0 1.0 Universal
RIGHTSCC0
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC6719893

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Integrating Hi-C links with assembly graphs for chromosome-scale assembly By Jay Ghurye, Arang Rhie, Brian P Walenz, Anthony Schmitt, Siddarth Selvaraj, Mihai Pop, Adam M Phillippy, Sergey Koren, Ilya Ioshikhes Published in: PLoS Computational Biology DOI: 10.1371/journal.pcbi.1007273 ABSTRACT Abstract Long-read sequencing and novel long-range assays have revolutionized de novo genome assembly by automating the reconstruction of reference-quality genomes. In particular, Hi-C sequencing is becoming an economical method for generating chromosome-scale scaffolds. Despite its increasing popularity, there are limited open-source tools available. Errors, particularly inversions and fusions across chromosomes, remain higher than alternate scaffolding technologies. We present a novel open-source Hi-C scaffolder that does not require an a priori estimate of chromosome number and minimizes errors by scaffolding with the assistance of an assembly graph. We demonstrate higher accuracy than the state-of-the-art methods across a variety of Hi-C library preparations and input assembly sizes. The Python and C++ code for our method is openly available at https://github.com/machinegun/SALSA. "This is a PLOS Computational Biology Methods paper." INTRODUCTION Genome assembly is the process of reconstructing a complete genome sequence from significantly shorter sequencing reads. Most genome projects rely on whole genome shotgun sequencing which yields an oversampling of each genomic locus. Reads originating from the same locus are identified using assembly software, which can use these overlaps to reconstruct the genome sequence [1, 2]. Most approaches are based on either a de Bruijn [3] or a string graph [4] formulation. Repetitive sequences exceeding the sequencing read length [5] introduce ambiguity and prevent complete reconstruction. Unambiguous reconstructions of the sequence are output as “unitigs” (or often “contigs”). Ambiguous reconstructions are output as edges linking unitigs. Scaffolding utilizes long-range linking information such as BAC or fosmid clones [6, 7], optical maps [8–10], linked reads [11–13], or chromosomal conformation capture [14] to order and orient contigs. If the linking information spans large distances on the chromosome, the resulting scaffolds can span entire chromosomes or chromosome arms. Hi-C is a sequencing-based assay originally designed to interrogate the 3D structure of the genome inside a cell nucleus by measuring the contact frequency between all pairs of loci in the genome [15]. The contact frequency between a pair of loci strongly correlates with the one-dimensional distance between them. Hi-C data can provide linkage information across a variety of length scales, spanning tens of megabases. As a result, Hi-C data can be used for genome scaffolding. Shortly after its introduction, Hi-C was used to generate chromosome-scale scaffolds [16–20]. LACHESIS [16] is an early method for Hi-C scaffolding that first clusters contigs into a user-specified number of chromosome groups and then orients and orders the contigs in each group independently to generate scaffolds. Thus, the scaffolds inherit any assembly errors present in the contigs. The original SALSA1 [21] method first corrects the input assembly, using a lack of Hi-C coverage as evidence of error. It then orients and orders the corrected contigs to generate scaffolds. Recently, the 3D-DNA [20] method was introduced and demonstrated on a draft assembly of the Aedes aegypti genome. 3D-DNA also corrects the errors in the input assembly and then iteratively orients and orders contigs into a single megascaffold. This megascaffold is then broken, identifying chromosomal ends based on the Hi-C contact map. There are several shortcomings common across currently available tools. They are sensitive to input assembly contiguity and Hi-C library variations and require tuning of parameters for each dataset. Inversions are common when the input contigs are short, as orientation is determined by maximizing the interaction frequency between contig ends across all possible orientations [16]. When contigs are long, there are few interactions spanning the full length of the contigs, making the true orientation apparent from the higher weight of links. However, in the case of short contigs, there are interactions spanning the full length of the contig, making the true orientation have a similar weight to incorrect orientations. Biological factors, such as topologically associated domains (TADs), also confound this analysis [22]. SALSA1 [21] addressed some of these challenges, such as not requiring the expected number of chromosomes beforehand and correcting assemblies before scaffolding them with Hi-C data. We showed that SALSA1 worked better than the most widely used method, LACHESIS [16]. However, SALSA1 often did not generate chromosome-sized scaffolds. The contiguity and correctness of the scaffolds depended on the coverage of Hi-C data and required manual data-dependent parameter tuning. Building on this work, SALSA2 does not require manual parameter tuning and is able to utilize all the contact information from the Hi-C data to generate near optimal sized scaffolds permitted by the data using a novel iterative scaffolding method. In addition to this, SALSA2 enables the use of an assembly graph to guide scaffolding, thereby minimizing errors, particularly orientation errors. SALSA2 is an open source software that combines Hi-C linkage information with the ambiguous-edge information from a genome assembly graph to better resolve contig orientations. We propose a novel stopping condition, which does not require an a priori estimate of chromosome count, as it naturally stops when the Hi-C information is exhausted. We show that SALSA2 produces fewer orientation, ordering, and chimeric errors across a wide range of assembly contiguities. We also demonstrate its robustness to different Hi-C libraries with varying levels of intra-chromosomal contact frequencies. When compared to 3D-DNA, SALSA2 generates more accurate scaffolds across most conditions. To our knowledge, this is the first method to leverage assembly graph information for scaffolding Hi-C data. METHODS Fig 1(A) shows the overview of the SALSA2 pipeline. SALSA2 begins with a draft assembly generated from long reads such as Pacific Biosciences [23] or Oxford Nanopore [24]. SALSA2 requires the contig sequences and, optionally, a GFA-formatted assembly graph [25] representing the ambiguous reconstructions. Hi-C reads are aligned to the contig sequences, and contigs are optionally split in regions lacking Hi-C coverage. A hybrid scaffold graph is constructed using both ambiguous edges from the GFA and edges from the Hi-C reads, scoring edges according to a “best buddy” scheme. Scaffolds are iteratively constructed from this graph using a greedy weighted maximum matching. A mis-join detection step is performed after each iteration to check if any of the joins made during this round are incorrect. Incorrect joins are broken and the edges blacklisted during subsequent iterations. This process continues until the majority of joins made in the prior iteration are incorrect. This provides a natural stopping condition, when accurate Hi-C links have been exhausted. Below, we describe each of the steps in detail. [Figure: (A) Overview of the SALSA2 scaffolding algorithm. (B) Linkage information obtained from the alignment of Hi-C reads to the assembly. Arrows denote contigs and arcs between arrows denote the inferred linking information from Hi-C reads. Thickness of arcs denote the weight on the Hi-C edge. Thicker edge indicates higher edge weight implied by Hi-C reads (C) Assembly graph obtained from the assembler, where arrows are contigs and arcs denote overlap between contigs(D) Hybrid scaffold graph constructed from the links obtained from the Hi-C read alignments and the overlap graph. Solid edges indicate the linkages between different contigs and dotted edges indicate the links between the ends of the same contig. B and E denote the start and end of contigs, respectively. The E-E edge between

Read the complete text