SYSTEMS AND METHODS FOR ENCODING GENOMIC GRAPH INFORMATION

1 . A method of encoding a genomic graph representing variations in genetic sequence, the method comprising:

providing a genomic graph comprising nodes connected by edges, wherein the nodes and edges are stored as objects in non-transitory memory of a computer system and wherein an edge within the genomic graph represents a genomic sequence;

selecting at least one edge from the genomic graph, the at least one edge representing a single genetic sequence and having a position on the genomic graph;

encoding the at least one edge as a string of bits, in which at least a first component of the string of bits stores at least a portion of the position of the branch on the genomic graph.

2 . The method of claim 1 , wherein selecting at least one edge comprises selecting edges having an associated identifier.

3 . The method of claim 1 , wherein selecting at least one edge from the genomic graph further comprises traversing the genomic graph and identifying paths beginning with nodes having multiple outgoing edges, ending at nodes having multiple incoming edges, and having at least one directed edge specifying a linear path between.

4 . The method of claim 3 , wherein selecting at least one edge from the genomic graph comprises selecting the at least one directed edge specifying a linear path between a node having multiple outgoing edges and a node having multiple incoming edges.

5 . The method of claim 1 , wherein selecting at least one edge from the genomic graph further comprises determining an ordering of the edges in the genomic graph.

6 . The method of claim 5 , wherein determining an ordering comprises identifying a longest path in the graph from a source vertex to a sink vertex.

7 . The method of claim 1 , wherein the position of the at least one edge on the genomic graph further comprises a starting position and an ending position; and further wherein encoding the branch as a string of bits comprises encoding at least a portion of the starting position and a least a portion of the ending position of the at least one edge on the genomic graph.

8 . The method of claim 1 , wherein the starting position and the ending position share a common prefix, and encoding the branch as a string of bits further comprises including third component that includes the common prefix.

9 . The method of claim 1 , wherein encoding the branch as a string of bits further comprises encoding the length of the associated genomic sequence.

10 . The method of claim 1 , wherein encoding the at least one edge as a string of bits further comprises encoding the associated genomic sequence.

11 . The method of claim 1 , wherein encoding the branch as a string of bits further comprises encoding the type of variation represented by the genomic sequence.

12 . The method of claim 11 , wherein the type of variation is encoded as a vector.

13 . The method of claim 11 , wherein the type of variation is a deletion of a single nucleotide, a single nucleotide polymorphism, a single nucleotide insertion, a multiple nucleotide insertion, or a replacement of one nucleotide by multiple nucleotides.

14 . The method of claim 13 , wherein encoding the at least one edge as a string of bits comprises encoding only a start position of the at least one edge on the genomic graph.

15 . The method of claim 1 , wherein encoding the branch as a string of bits further comprises encoding the associated genomic sequence.

16 . The method of claim 1 , further comprising removing the at least one edge from the graph.

17 . The method of claim 16 , further comprising selecting and encoding at least one second edge from the genomic graph.

18 . The method of claim 1 , wherein the first component includes length bits indicating a length of the first component and representation bits that include the portion of the starting coordinate.

19 . The method of claim 18 , wherein each component is stored as a sub-string of the string of bits wherein a first portion of the sub-string represents a length of the sub-string and a second portion of the sub-string includes stored information.

20 . The method of claim 19 , further comprising performing the selection and encoding steps to convert the genomic graph into a linear string of bits comprising a representation of each of the plurality of edges.

21 . The method of claim 1 , further comprising storing a plurality of edges from the genomic graph, each as its own string of bits.

22 . The method of claim 1 , further comprising storing all of the edges from the genomic graph so that the entire genomic graph is stored as a sequence of strings of bits, each string of bits comprising a first portion representing a length of the string and a second portion representing the position.

23 . A method of decoding a genomic graph from a serialized specification, the method comprising:

receiving a representation of a genomic sequence;

associating the genetic sequence with a first edge of a genomic graph;

receiving a representation of a variation of the genetic sequence, the representation further comprising a position on the genomic graph of the variation;

associating the representation of the variation with a second edge; and

inserting the second edge into the genomic graph at the position.

24 . The method of claim 23 , further comprising segmenting the first edge at the position of the variation.