Graph matching and its application in computer vision and bioinformatics.

Summary The graph alignment problem, which plays a central role in various areas of pattern recognition, is one of the biggest challenges in graph processing. We propose an approximate method for the alignment of labeled and weighted graphs based on concave convex programming. An important application of the graph alignment problem is the alignment of protein interaction networks, which plays a central role in the search for evolutionarily conserved signaling pathways, conserved protein complexes between species, and the identification of functional orthologs. We reformulate the interaction network alignment problem as a graph alignment problem, and study how existing graph alignment algorithms can be used to solve it. In the classical formulation of the graph alignment problem, only bijective correspondences between the nodes of two graphs are considered. In many applications, however, it is more interesting to consider correspondences between sets of nodes. We propose a new formulation of this problem as a discrete optimization problem, as well as an approximate algorithm based on a continuous relaxation. We also present two independent results in the fields of statistical machine translation and bioinformatics. First, we show how the sentence-based statistical translation problem can be reformulated as a traveling salesman problem. On the other hand, we propose a new measure of similarity between protein binding sites, based on the 3D comparison of atomic clouds.