String Reconstruction with Overlap Graph: Graph Representation

Graph representation

If you’ve never worked with graphs before, you may be wondering how to represent graphs in your programs. To make a brief digression from our discussion of genome assembly, consider the graph in the figure below (top left); we can move around this graph’s nodes without changing the graph. (For another example, the graphs in this figureFIGURE3_7 and this figureFIGURE3_8 are the same). As a result, when we’re representing a graph computationally, the only information we need to store is the pair of nodes that each edge connects.

There are two standard ways of representing a graph. For a directed graph with n nodes, the n × n adjacency matrix (A ...