Sequence graph

Before constructing a sequence graph, there must be at least two genomes represented as directed graphs with edges as threads (adjacency edges) and vertices as DNA segments. The genomes should be labeled P and Q, while the sequence graph is labeled as BreakpointGraph(P, Q).^[2]

The directional vertices of Q and their edges are arranged in the order of P. Once completed, the edges of Q are reconnected to their original vertices. After all edges have been matched the vertex directions are removed and instead each vertex is labeled as v^h (vertex head) and v^t (vertex tail).

Similarity between genomes is represented by the number of cycles (independent systems) within the sequence graph. The number of cycles is equal to cycles (P, Q). The max number of cycles possible is equal to the number of vertices in the sequence graph.

Figure example.

Upon receiving genomes P (+a +b -c) and Q (+a +b -c),^[1] Q should be realigned to follow the direction edges (red) of P. The vertices should be renamed from a, b, c to a^h a^t, b^h b^t, c^h c^t and the edges of P and Q should be connected to their original vertices (P edges = black, Q edges = green). Remove the directional edges (red). The number of cycles in G(P, Q) is 1 while the max possible is 3.

Alekseyev and Pevzner use sequence graphs to create their own algorithm to study the genome rearrangement history of several mammals, as well as a way to overcome problems with current ancestral reconstruction of genomes.^[1]

Sequence graphs can be used to represent multiple sequence alignments with the addition of a new kind of edge representing homology between segments.^[3] For a set of genomes, one can create an acyclic breakpoint graph with a thread for each genome. For two segments ${\displaystyle (a,b)}$ and ${\displaystyle (c,d)}$, where ${\displaystyle a}$,${\displaystyle b}$,${\displaystyle c}$, and ${\displaystyle d}$ represent the endpoints of the two segments, homology edges can be created from ${\displaystyle a}$ to ${\displaystyle c}$ and ${\displaystyle b}$ to ${\displaystyle d}$ or from ${\displaystyle a}$ to ${\displaystyle d}$ and ${\displaystyle b}$ to ${\displaystyle c}$ - representing the two possible orientations of the homology. The advantage of representing a multiple sequence alignment this way is that it is possible to include inversions and other structural rearrangements that wouldn't be allowable in a matrix representation.

If there are multiple possible paths when traversing a thread in a sequence graph, multiple sequences can be represented by the same thread. This means it is possible to create a sequence graph that represents a population of individuals with slightly different genomes - with each genome corresponding to one path through the graph. These graphs have been proposed as a replacement for the reference human genome.^[4]