Operations Research Seminar - 26/3/2014

Wednesday, 26 March 2014, 2:30 p.m.

Lecturer: Pedro Martins (CIO/Instituto Politécnico de Coimbra-ISCAC)

Title: "Using cliques for mining biological networks"

Local: Sala de Seminários, Edifício VII
Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: A network/graph provides an abstract representation, establishing the relationships among a set of elements. It helps organizing the information and provides an overall view of the underlying system.
These structures are being used in a large number of areas and scientific domains, namely in Sociology, Financial Markets, Marketing, Engineering, Chemistry, Biology, among others, contributing for knowledge progress and deeper understanding of hidden underlying information. 
A clique is a complete subgraph, revealing a strongly related group of nodes (elements). When assigning weights to the edges of the graph, addressing the frequency of the linkage, we are conducted to (edge)-weight clique problems. In this case we are no longer interested on the cardinality of the clique but on its total weight.
From the modeling standpoint, the weighted version usually requires many more variables and constraints than the classical maximum clique problem, leading to larger formulations. These models are much more challenging when addressing larger sized real-world problems.
In this seminar, we discuss formulations for the maximum edge-weight clique problem, exploring new extended and discretized models (in a joint work with Luis Gouveia), and compare these results with other clustering techniques. We also discuss their applicability on some real-world environments, namely on networks of interacting pathways and genes/samples co-expression networks.