Description of Edge Function

1. Assign each time point of every gene a label depending on whether it is a local minima or maxima. While comparing the expression value of neighboring points, we allow a given expression error level, typically 10%. Whenever the difference of expression value between two points is less than expression error level, neither point can define a local optima.

2. For each gene, the labeled minima and maxima are connected using a four-step edge construction process:

Primary edges links neighboring local maxima and minima.

Secondary edges line all primary edges whose height

is greater than a threshold, typically 30%. This accounts for the minimal biologically significant expression level change. Any changes below this level are probably due to experimental error.

Tertiary edges result from merging adjacent secondary edges of similar direction.

Quadrary edges result from eliminating narrow peaks or troughs.

Finally, each gene is represented by an array of quadrary edges which we consider as biologically significant and reliable expression level changes.

3. Pairs of genes are scored solely based on their quadrary edges. To score genes G_a and G_b, we score each quadrary edge (e_a) of G_a against each quadrary edge (e_b) of G_b. Provided the time difference between the two edges is ≤ max_gap. the similarity score Sg between G_a and G_b is given as:

where d denotes the agreement of the slopes of e_a and e_b. Specifically, d =1 if the signs of the slopes agree, otherwise d = –1. max_gap defines the maximum time difference (in minutes) between the middle of e_a and e_b. A typical setting is 15 minutes for yeast expression datasets. real_gap denotes the real time difference (minutes) between the middle of e_a and e_b. Thus 0 ≤ real_gap ≤ max_gap. Edge pairs with time difference > max_gap is considered meaningless and is simply ignored. Larger values of real_gap imply less similarity between the edges. The counts n_a and n_b denote the total number of quadrary edges of G_a and G_b, respectively.