Network alignment
Date:
Networks are a powerful model of representing and analyzing biological data. One important question is, how much two different biological networks of same category are similar to each other. The mathematical translation of this question is the network alignment problem. In general, network alignment identifies a bijection between the full (or partial) vertex sets of two networks such that the size of the corresponding common subgraph is maximized. This problem is closely related to the quadratic assignment problem and is known to be NP-hard not only to solve, but even to approximate. Because of its applications in different areas like systems biology or social sciences, finding an efficient algorithm to approximate the optimal alignment is an essential problem. This talk will cover applications of this problem in biology, review some known algorithms which are mainly based on spectral techniques, and state some of our new results at the end.