Simona E. Rombo, University of Palermo, Italy

Basic graph and network alignment algorithms
In the last few years, biological networks received great attention, also due to the increasing amount of interactions among cellular components retrieved by experimental, computational and high-throughput techniques. Comparing and aligning such graphs can be useful in many applications, for example to infer knowledge about conservation across species. However, biological network comparison often involves difficult tasks, such as sub-graph isomorphism checking. Thus approximation algorithms and heuristics approaches have been proposed to solve this problem.
In this tutorial some basic notions about graph theory and classification/statistics analysis will be recalled, and recent developed network alignment algorithms will be described and discussed, also illustrating the main differences among local, global and asymmetric graph alignment.

References