Search⌘ K
Home
Courses
Bioinformatics Algorithms

String Reconstruction with Overlap Graph: Graph Representation

Explore how to represent graphs computationally to support genome assembly. Understand adjacency matrices and adjacency lists as standard ways to store graph edges efficiently. This lesson helps you grasp the foundational graph concepts necessary for assembling genomes from DNA data.

We'll cover the following...

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 ...