BIOINFORMATICS Vol. 26 no. 6 2010, pages 853–854 doi:10.1093/bioinformatics/btq091 ERRATUM Erratum Biological network comparison using graphlet degree distribution Nataša Pržulj Department of Computing, Imperial College London, SW7 2AZ, UK, E-mail: natasha@imperial.ac.uk Bioinformatics, 23 (2): e177. (2007) A j (G, ±H) = 1−D j (G, H), (1) where ±H is a typo and it should be just: A j (G, H) = 1−Dj (G, H) (2) to be between 0 and 1. In Next, D j (G, H) was mistakenly claimed √ fact, this distance is between 0 and 2. Since it can be greater than 1 (consider, e.g. D1 (G, H) where G is 5-node cycle and H is 5-node path, see Fig. 1), formula (2) can result in negative values. H G Fig. 1. An example of two graphs G and H for which D1 (G, H) > 1. For orbit number 1 (see Fig. 1 in Pržulj (2007)), using formulas (1)–(4) from Pržulj (2007) we can calculate for graph G that NG1 (2) = 1, and for all k = 2, 4 NG1 (k) = 0, while for graph H, NH1 (1) = 4.5 , NH1 (2) = 0.5 4.5 , and for all k > 2, NH1 (k) = 0. Then D1 (G, H) = √ 32 4.5 > 1. j Therefore, we √ correct the formula for D (G, H) by simply dividing it by 2: ⎞1 ⎛ ∞ 2 2 1 j j Dj (G, H) = √ ⎝ (3) N (k)−NH (k) ⎠ 2 k=1 G Dj (G, H) defined in this way is guaranteed to be between 0 and 1. All other formulas from Pržulj (2007) remain correct. Below we prove that Dj (G, H) defined in this way is between 0 and 1. j Proof. According to formula (3) from Pržulj (2007), NG (k) = j SG (k) j TG . Therefore, we can rewrite formula (3) above as 2 12 1 ∞ j j NG (k)−NH (k) Dj (G, H) = √ k=1 2 2 2 12 ∞ 1 j j ≤√ NG (k) + NH (k) k=1 2 ⎡ ⎛ 2 j 2 ⎤⎞ 12 j S (k) S (k) ∞ 1 ⎣ G ⎦⎠ =√ ⎝ + Hj j k=1 2 TG TH G H 1 ≤ √ (1+1) = 1 2 1 2 since, according j j TG = ∞ k=1 SG (k). to formula (2) from Pržulj The upper bound of 1 for Dj (G, H) is reachable, for example, if G is a 5-node cycle and H is a 3-node path. We reanalyzed all the results from Pržulj (2007) and this correction does not affect them qualitatively; there is only a small quantitative difference in the results. Figure 2 presents the results of the same analysis as Figure 3 from Pržulj (2007), but performed with the formula corrected as described above. As shown in Figure 2, the model ordering remains unchanged, with GEO-3D model being superior to other models. As in Pržulj (2007), to gauge the range of this agreement measure, we computed the average agreements between various model (i.e. theoretical) networks. For example, when comparing networks of the same type that are of the same size and are generated with the same parameters (ER versus ER, ER-DD versus ER-DD, SF-BA versus SF-BA, or GEO-3D versus GEO-3D), we found that the mean GDD agreement is the smallest for two SF networks (0.86 ± 0.01) and the highest for two GEO-3D networks (0.95 ± 0.002). To verify that our agreement measure can give low values for networks that are very different, we also constructed a straw-man model graph called a circulant and compared it with some actual PPI network data. A circulant graph is constructed by adding chords to a cycle on n nodes so that the i-th node on the cycle is connected to the [(i+j) mod n]-th and [(i−j) mod n]-th node on the cycle. Clearly, a large circulant with an equal number of nodes and edge density as the data would not be very representative of a PPI network and indeed we find that the agreement between such a circulant, with chords defined by j ∈ {5,10,15,20,25,30}, and the data is < 0.26. The author apologizes for these mistakes. ACKNOWLEDGEMENTS The author thanks Zi Wang, a PhD student of Prof Gesine Reinert and Dr Charlotte Deane, Department of Statistics, University of Oxford, for noticing that the interval was wrong in the original paper; he also noticed that the upper bound of 1 can be achieved. Many thanks to Oleksii Kuchaiev, Computer Science, Univeristy of California, Irvine, for helping with the proof and the data analysis using the corrected formula in this erratum. © The Author 2010. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org [16:55 10/3/2010 Bioinformatics-btq091.tex] (2007), Downloaded from http://bioinformatics.oxfordjournals.org at Imperial College London on June 14, 2010 In Pržulj (2007), the formula for GDD agreement has a typo. The j-th GDD agreement was defined [formula (5) in Pržulj (2007)] as ⎛ 2 ⎞ 12 j 2 ∞ S j (k) 1 ⎝∞ SG (k) H ⎠ + =√ j j k=1 k=1 2 T T 853 Page: 853 853–854 Erratum (A) GDD-Agreement (arithmetic mean) Between the Data and Model Networks 0.9 0.85 0.75 0.7 0.65 ER ER-DD SF-BA GEO-3D 0.6 0.55 YHCY11KYIC YU YICU FE FH WE WC HS HG HB HH HM Real-World Networks (B) GDD-Agreement (geometric mean) Between the Data and Model Networks 0.9 0.85 GDD-Agreement 0.8 0.75 0.7 0.65 0.6 ER ER-DD SF-BA GEO-3D 0.55 0.5 YHCY11KYIC YU YICU FE FH WE WC HS HG HB HH HM Real-World Networks Fig. 2. Agreements between the 14 PPI networks and their corresponding model networks from Pržulj (2007). Labels on the horizontal axes are described in Section 2.1 of Pržulj (2007). Averages of agreements between 25 model networks and the corresponding PPI network are presented for each random graph model and each PPI network, i.e. at each point in the figure. As described in Section 2.3 of Pržulj (2007), the agreement between a PPI and a model network is based on the: (A) arithmetic average of j-th GDD agreements; and (B) geometric average of j-th GDD agreements. REFERENCES Downloaded from http://bioinformatics.oxfordjournals.org at Imperial College London on June 14, 2010 GDD-Agreement 0.8 Pržulj,N. (2007) Biological network comparison using graphlet degree distribution. Bioinformatics, 23 (2): e177–e183. 854 [16:55 10/3/2010 Bioinformatics-btq091.tex] Page: 854 853–854