Sequence graph

In comparative genomics, a sequence graph, also called an alignment graph, breakpoint graph, or adjacency graph, is a bidirected graph in which the vertices represent segments of DNA and the edges represent adjacency between segments in a genome. The segments are labeled by the DNA string they represent, and each edge connects the tail end of one segment with the head end of another segment. Each adjacency edge is labelled by a (possibly empty) string of DNA. Traversing a connected component of segments and adjacency edges (called a thread) yields a sequence, which typically represents a genome or a section of a genome. The segments can be thought of as synteny blocks, with the edges dictating how to arrange these blocks in a particular genome, and the labelling of the adjacency edges representing bases that are not contained in synteny blocks.

Applications

Multiple sequence alignment

Sequence graphs can be used to represent multiple sequence alignments with the addition of a new kind of edge representing homology between segments. For a set of genomes, one can create an acyclic breakpoint graph with a thread for each genome. For two segments $(a,b)$ and $(c,d)$, where $a$,$b$,$c$, and $d$ represent the endpoints of the two segments, homology edges can be created from $a$ to $c$ and $b$ to $d$ or from $a$ to $d$ and $b$ to $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.