Rosalba Giugno, University of Catania, Catania, Italy

Fast Heuristics for Matching and Comparison of Biological Networks
In biological networks, locating subgraphs is useful to characterize or to understand specific functionalities. Such a localization may arise from networks comparison (extract unknown significant subgraphs) or from querying networks (looking for a specific pattern). Subgraph queries are also useful to identify similar chemical compounds and targets during drug discovery. In all of the above applications, subgraph searching must tolerate some differences in nodes, edges, and structures. These tasks are computationally hard. The complexity is partially due to subgraph isomorphism, a decision problem known to be NP-complete. To overcome the complexity problem, a variety of graph indices and data structures similar to tree structures used in spatial access methods have been introduced. The basic idea of many approaches is to break a graph into paths, fragments or classes of nodes used as filtering features in graph or as a guide for comparison. Classical fast matching algorithms have been also adapted for searching in networks. This tutorial describes basic graph algorithms, indexing techniques and data structures for network comparison, network querying and large graph databases querying, with particular attention to biological datasets.

Ferro A, Giugno R, Mongioví M, Pulvirenti A, Skripin D, Shasha D. (2007). GraphBlast: multi-feature graphs database searching. Network Tools and Applications in Biology (NETTAB).

Ferro A, Giugno R, Pigola G, Pulvirenti A, Skripin D, Bader GD, Shasha D. (2007). NetMatch: a cytoscape plugin for searching biological networks. Bioinformatics , 23 :910-912.

Shasha D., Wang J.T-L, Giugno R. (2002). Algorithmics and Applications of Tree and Graph Searching. Proceeding of the ACM Symposium on Principles of Database Systems (PODS).

Giugno R, Shasha D. (2002). GraphGrep: A Fast and Universal Method for Querying Graphs. Proceeding of the IEEE International Conference in Pattern recognition (ICPR).

Sharan R, Ideker T. (2006). Modelling cellular machinery through biological network comparison. Nature Biotechnology , 24 : 4.

Tian Y, McEachin RC, Santos C, States DJ, Patel JM. (2006). SAGA: a subgraph matching tool for biological graphs. Bioinformatics, 23 :232-239.

Huahai He; Singh, A.K. (2006). Closure-Tree: An Index Structure for Graph Queries. Proceedings of the 22nd International Conference on Data Engineering (ICDE).

Flannick J, Novak A, Srinivasan BS, McAdams HH, Batzoglou S. Græmlin: General and robust alignment of multiple large interaction networks. (2006). Genome Res . 16 :1169-1181,.

Koyuturk, Kim Y, Subramaniam S, Szpankowski W, Grama A. (2006). Detecting Conserved Interaction Patterns in Biological Networks. Journal of Computational Biology , 13 (7): 1299-1322 .

Alon N., Yuster R, Zwick U. (1995). Colour-Coding J. ACM , 42 (4): 844-856.