Skip to content

Latest commit

 

History

History
55 lines (38 loc) · 3.19 KB

VERSION2.md

File metadata and controls

55 lines (38 loc) · 3.19 KB

Plans for GBWT v2.0

Version 2.0 will be a breaking change that will simplify the GBWT and align it more closely with other data models used in (human) pangenomics. A conversion tool will be provided for old GBWT and GBZ files.

BWT encoding

There are currently two encodings for BWT runs, depending on local alphabet size (outdegree of the node):

  • If the outdegree is at most 254, the first byte encodes the edge rank of the successor node and as much of the run length as possible. Short runs are encoded in a single byte. The remaining run length is encoded using ByteCode.
  • Otherwise we first encode the edge rank and then the run length, both using ByteCode.

The threshold for the first encoding can be safely increased from 254 to 256.

Endmarker

The endmarker record 0 will no longer be included in the BWT itself. It will be stored separately and decompressed as DecompressedRecord. There will be separate encodings for unidirectional and bidirectional GBWTs. In the latter, we either encode runs (ab)^k or have separate endmarker records for forward and reverse paths.

Locate functionality

GBWT use a rather inefficient structure for finding the sequence identifier corresponding to a GBWT position. The Rust implementation does not support the locate structure. Version 2 will remove the structure and replace it with an optional r-index (FastLocate), which is larger but much faster. Removing the locate support should also simplify the construction algorithm and make it faster.

Dynamic GBWT

Dynamic GBWT will be simplified and optimized. It will only be used for GBWT construction. Runs in BWT records will be stored as successor node ids instead of edge ranks. There will be no queries or a locate structure. Path metadata will be provided in the construction interface itself.

Metadata

The current GBWT metadata model is based on haplotype paths generated from a phased VCF file. A path name consists of four integer components: sample, contig, haplotype / phase, and fragment / phase block. Path names are optional in the metadata, and sample / contig identifiers may be associated with string names.

Version 2 will make path, sample, and contig names mandatory if metadata is present. There will also be higher-level metadata for fragmented sequences consisting of multiple paths. That metadata will, for example, tell whether the fragment field stores the rank of the path fragment or its starting offset in the full sequence. Ideally there will be corresponding changes to the GFA specification.

We will also need data structures that support finding paths by metadata. The current approach of scanning the path metadata does not work well with frequency-filtered graphs that may have tens of millions of paths.

Serialization

GBWT currently supports two serialization formats: one based on SDSL serialization, and another on Simple-SDS serialization. The Simple-SDS format is more versatile and better documented, and it is also supported by the Rust implementation. It will become the only format supported in version 2.