Some Recent Applications

New distributed algorithm for the Steiner tree problem over networks. Many upper bounds of unsolved classes of benchmarks on the SteinLib library have been improved.

Pathways identification.

A technique for matching protein networks and gene expression data - based on our Steiner tree algorithm - has been validated on Yeast. A prediction concerning signaling in sphingolipid biosynthesis and transport has been confirmed by experiments at the INSA Lab in Toulouse (France).

Phylogenetic reconstructions. A technique which couples MPA and Monte Carlo sampling is being developed with the aim of performing large scale maximum parsimony and
maximum likelihood reconstructions.

Inference of interactions in large scale systems from correlation data. A Survey Propagation algorithm has been developed for inferring interaction topologies and couplings from noisy data by maximum likelihood.

Clustering. A message-passing technique which interpolates between Affinity Propagation (spherical clustering in high dimensions) and Single Linkage has been introduced and appliedsuccessfully to proteins family data, neural activity patterns in monkeys and social data.

Further results on optimization over graphs include rigorous studies and applications to source coding
(lossy compression in GF(q)), Constraint Satisfaction Problems over networks (sub-graph isomorphism), graphical games and e-commerce (Resources Allocation Problems and Adwords).