Backend Graph Specification

[6br]

((Updated by Josiah 2019-07-10))
((Updated by Josiah 2019-08-15: Removed PathIndex and Slices))

Version 1 - Basics

• GraphGenome is the top level object which holds references to:
  • The set of all nodes in the Graph by uuid
  • Set of all Paths in the Graph by accession name
    • One path per accession (contiguous). Each chromosome = ?
  • Method for topological sort to present graph nodes in a consistent order every time
• Paths contain
  • One unique accession (a.k.a. specimen) name
  • List of NodeTraversals in order (reverse lookup)
  • Can visit the same node multiple times
    • Each node traversal is tracked by NodeTraversal and annotations (epigenetic state, etc.) is tied to a NodeTraversal, not the Node itself.
  • Ex. 5+ 9+ 10+ 50+ 23- 78+
• Node contains:
  • Sequence (optional)
  • uuid to distinguish from other nodes of same sequence
  • Set of Node Traversals intersecting the node (reverse lookup)
    • You can ask each Traversal what is the next "downstream" or "upstream" node. Meaning you can build a set of neighboring nodes, including self for duplications.
    • Ex. { (Path5, Order 67, +) (Path10, Order 160, -), (Path5, Order 2756, +) }
• NodeTraversal
  • Node - being traversed
  • Path - the specimen doing the traversing
  • strand: either + or - represents reverse complements and inversions
  • Order - order in which the traversal occurs in this path
    • e.g. 5 would be the 5th node visited by the Path and N+1 is the downstream node

[6br]

Version 2 - Summary Layers

• GraphGenome has a list of SummaryLayers, at increasing levels of summarization.
• Node Changes:
  • Node has link to summary_parent: a node in the next SummaryLayer up.
  • Backlinks from one node can lead to multiple, more specific nodes when zooming in.
• Nodes: Tracking Alternative Haplotypes
  • While summarizing some sequence information was lost. We need to quantify how much.
  • Nodes from split_groups contain a link to their alternative_allele and a sequence size and percentage identity.
  • alternative_allele ForeignKey(Node)
  • alternative_overlap_bp number of base pairs the two alleles agree on
    • When simple_merge Nodes with alternative_allele, alternative_overlap_bp can be added to ensure percentages don't drift based on nodes of differing sizes.
• Path changes:
  • Each specimen will have one Path per SummaryLayer
  • Paths belong to one summary level. Paths can be built using the transitive property on Node summary_parents.

((Updated by Josiah 2019-08-15: Clarified Ribbon vs. Path. Added AggregateTraversal))

Version 3 - Ribbon Haplotypes

• Key idea: instead of sending 1,000 paths for 1,000 specimens, there are ~20 Ribbons sent with specimens counts. A detail query returns a list of specimens in each ribbon. Ribbons are a container to summarize many paths that share commonality i.e. a haplotype.
• Ribbons contain:
  • Dendrogram of paths computed like a gene tree of similar sequences, show how diverged each pair of specimens are
    • Similarity is defined by the sequence of nodes along their path
  • Branch lengths for similarity
  • Presented Ribbons are not hard boundaries, just a cutoff based on data and level of detail. There is a fundamental problem with coloring local versus global solutions will not match. Further discussion/investigation is required.
• AggregateTraversal (NodeTraversal): Ribbons have higher level traversal objects
  • coverage_count The number of specimens inside this ribbon that actually traverse this node. From this can be calculated the number of specimens bypassing a node.
  • Possibly sum in copy number expansion as well (this is summarizing)

Version 4 - Annotation

• Annotation Stack is a list of annotations
• Annotation metadata is a tree/graph of annotations that represents relationship between annotations
  • For example, a gene contains isoforms, and an isoform contain introns and exons.
• Annotation has two types of
  • Contiguous annotation (i.e. paths)
  • Continuous value annotation (vg pack format, gGFF format)
    (WIP)

[josiahseaman]

• Did you end up choosing Node storing a Path index, or Nodes and Paths both pointing to an Intersection object? Both versions are currently in the spec. Once you've decided, let's remove the redundant spec.
• In version 2, checkpoints should probably be their own object. Paths would contain a list of segments with a checkpoint at the beginning of every segment. I'm still not convinced checkpoints are ideal, but it's an acceptable rough draft.

[6br]

For the first issue, I prefer to store a Path index into Node. Because it is simpler than using Intersection object.

[6br]

For the second issue, checkpoints seem ad-hoc ideas to represent nucleotide coordinates on paths, but they are useful when users wish to understand what part of the whole genome do they see. Suppose if paths contain a list of segments with a checkpoint, and if you want to merge two segments across the checkpoint, then it becomes unclear how to handle the checkpoint. However, if you specify checkpoints on the farthest view (aka. bird's eyes), then the checkpoints can propagate to all zoom layers including nucleotide zoom level because we can assume that we do not merge nodes on zooming up. I wonder if there is a good way to represent checkpoints in this spec.

[josiahseaman]

Check points are ad hoc, but they may scale very nicely all the same. To be clear, checkpoints are just a speed optimization feature. It's possible to start at the beginning of a path and count every nucleotide in every node until you reach the index you are looking for. Checkpoints are just a precomputed sum stored haphazardly throughout the path. So you can delete a checkpoint and nothing bad happens, it just takes fractionally longer to calculate. As the graph is iteratively summarized, checkpoints would become increasingly dense and outnumber nodes, which is bad. So every time a merge operation spans a checkpoint, just delete the checkpoint and append the two lists together. That way there's roughly the same ratio of checkpoint to node. The nice thing about preserving checkpoints at large scale that were precomputed at nucleotide scale is that there's no rounding error propagation. They'll stay as accurate as the graph allows.

The competitor solution is to have a "coordinate mapping" service that's a completely separate data structure. This may be cleaner in the long run. Either way, we don't have to decide yes/no on checkpoints immediately. We need to decide #5 first.

@ekg Does VG already have a better solution for the problem of mapping old TAIR10 coordinates onto a graph in random access?

[ekg]

@josiahseaman what's a TAIR10 coordinate?

In vg we have the xg index, which handles coordinate mappings of the graph. I've submitted a proposal for the upcoming Biohackathon that extends this model with a server interface that could be used by graph genome browsers.

[josiahseaman]

Great! That sounds like exactly what we're looking for. So we'd use the service you create at BioHackathon in combination with the links from node to summary node (Version 2 - Summary Stacks) to be able to find for example, the beginning and end node at zoom level 3 corresponding to nucleotides 23,758,110 and 45,687,084. That'd be two calls to Erik's service and three lookups to iterate up zoom levels. I think we can put that question to rest now.

P.S. TAIR10 is just an example of a particular genome assembly, I could also have said Hg38 coordinate just to point out the coordinate concept is dependent on a particular assembly.

[ekg]

xg provides graph to genome path position mappings. That's pretty much the basis for these assembly coordinate systems.

[6br]

My goal: I have a python data interface to interact with xg server on version 1.