Distinguishing between functional and nonfunctional siRNA

We now need to distinguish between functional and non functional siRNA sequences. We explored weighted graph properties to determine whether a distinguishing property exists. The properties that we studied are Maximum Vertex Degree, Minimum Vertex degree, Difference in Max and Min, Diameter, and Girth. A Vertex's degree refers to the number of edges incident (connected) to it. The girth is the shortest graph cycle, which is a path through the graph starting and ending at the same vertex. Diameter is the largest distance in a path, where distance is the shortest path between two vertices. So to find the diameter, first find the shortest paths between each pair of vertices and then take the maximum length of these paths. The following example will illustrate these properties:

The above graph is output from the Maple program that we wrote to create a graph given an input sequence. The program also outputed the properties described on the previous page. I will now explain how we would determine manually what the value of these properties are. First we determine vertex degree:

A	1
U	3
G	4
C	3

So the maximum vertex degree is 4, the minimum is 1, and the difference is 3.

Next to find the girth, we want the shortest graph cycle. Well we see that there is an edge from U to itself (as well as G and C), and this is a cycle of length 1. So our girth is 1. Then to find the diameter, we look at distances between vertices in the graph. We see that U,G, and C are all connected by paths of length 1; however, A requires a path of length 2 to reach U or C, and therefore the diameter of the graph is 2.