Graphm matching

Graph Matching

The graph matching problem is among the most important challenges of graph processing, and plays a central role in various fields of pattern recognition. Roughly speaking, the problem consists in finding a correspondence between vertices of two given graphs which is optimal in some sense. Usually, the optimality refers to the alignment of graph structures and, when available, of vertices labels, although other criteria are possible as well. A non-exhaustive list of graph matching applications includes document processing tasks like optical character recognition, image analysis (2D and 3D), bioinformatics and chemoinformatics.



Related papers:
  1. A Path Following Algorithm for the Graph Matching Problem
  2. Global alignment of protein-protein interaction networks by graph matching methods [paper web page]
  3. The many-to-many graph matching problem
Software: GraphM package
TSP

Statistical Machine Translation & TSP

An efficient decoding algorithm is a crucial element of any statistical machine translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Salesman Problem; We show that any phrase-based SMT decoding problem can be directly reformulated as a TSP. The transformation is very natural, deepens our understanding of the decoding problem, and allows direct use of any of the powerful existing TSP solvers for SMT decoding.


Related papers: Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem
Software: A TSP-based SMT decoder was developed in the XRCE (Xerox Research Center Europe)
Binding pocket

A new similarity measure for protein binding pockets

Prediction of ligands for proteins of known 3D structure is important to understand structure-function relationship, predict molecular function, or design new drugs.We explore a new approach for ligand prediction in which binding pockets are represented by atom clouds. Each target pocket is compared to an ensemble of pockets of known ligands. Pockets are aligned in 3D space with further use of convolution kernels between clouds of points.

Related papers:
    A new protein binding pocket similarity measure based on comparison of 3D atom clouds.
Software: PARIS package

Conditional Random Fields: protein segmentation

Technical reports
Protein segmentation: some machine learning approaches (Master(MVA) report, Master(MVA) slides)
Software: CrfSignal (matlab)