A Sequence Distance Graph framework for genome assembly and analysis

Abstract

The Sequence Distance Graph (SDG) framework works with genome assembly graphs and raw data from paired, linked and long reads. It includes a simple deBruijn graph module, and can import graphs using the graphical fragment assembly (GFA) format. It also maps raw reads onto graphs, and provides a Python application programming interface (API) to navigate the graph, access the mapped and raw data and perform interactive or scripted analyses. Its complete workspace can be dumped to and loaded from disk, decoupling mapping from analysis and supporting multi-stage pipelines. We present the design and implementation of the framework, and example analyses scaffolding a short read graph with long reads, and navigating paths in a heterozygous graph for a simulated parent-offspring trio dataset. SDG is freely available under the MIT license at https://github.com/bioinfologics/sdg.

Keywords: Genome graph; genome assembly.

Figure 1.. A simple Sequence Distance Graph with 5 nodes, including links with d<0, representing overlaps, and a link representing a gap of 10bp.

Sequences appear in only one direction and their reverse complement can be obtained by traversing the node in opposite direction, from - to +. The two largest possible paths are [1, 2, 4, 5] and [1, -3, 4, 5], and their reverse complements [-5, -4, -2, -1] and [-5, -4, 3, -1] respectively.

Figure 2.. Structure of a WorkSpace and access via an Python interactive session.

The WorkSpace holds the information for a project and contains the graphs, the mappers and k-mer counts. From Python, a previously saved WorkSpace is loaded from disk (1). The NodeView object is centred on a specific node and can be used to access node characteristics (ie. size and sequence), graph topology from the perspective of the node you are on (i.e. neighbours in both directions (2)) and can also retrieve information projected onto the selected node (ie. mappings (3) and k-mer coverage (4)). Operations such as adding a KmerCounter to the WorkSpace and adding a count (5) can be performed, and the WorkSpace can be saved back to disk (6). Once loaded, the bulk of the WorkSpace is held in memory for fast access with the raw read data from the DataStores remaining on disk accessible through random access.

Figure 3.

Linkage at different stages of the long read scaffolding example, visualised using Bandage: A) SequenceDistanceGraph generated by sdg-dbg from short reads, B) DistanceGraph generated after using make_nextselected_linkage on the long read data, linking all nodes of 1100bp and more, C) DistanceGraph after eliminating all nodes with multiple connections (repeats).

Figure 4.. Trio analysis: k-mer coverage for each side of the largest bubble structure in the child’s assembly by each of the three read sets.

Coverage drops to 0 on the opposite parent for k-mers that are unique to a parent.