Lecture

A matching-related property of bipartite graphs with applications in signal processing and bioinformatics

Speaker:	Epameinondas Fritzilas
Date:	Thursday, 27 August 2009
Time:	16:00-18:00
Location:	"Mediterranean Studies" Seminar Room, FORTH. Heraklion, Crete
Host:	I. Tollis

Abstract:

In many signal processing applications we need to write a given matrix Y as a product Y=AX. Both matrices A and X have to be determined and we assume that from the specifics of the application we can derive some constraints for them. We consider a class of constraints which arise in applications that involve a bipartite network of signal sources and sensors. In this context, Y contains sensor measurements over time, X contains source signals over time and A contains the source-sensor mixing coefficients. We assume that the connectivity of the network is fixed and known a-priori. Does this contribute anything to the uniqueness of the factorization? There are two applications from bioinformatics that can be modeled in this framework: Processing of microarray measurements with non-specific probes and quantification of transcription factor activities in simple regulatory networks.
We first present a characterization of uniqueness up to diagonal scaling in the factorization Y=AX. This characterization is combinatorial, in the sense that it depends only on the structure of the bipartite source-sensor graph; more specifically, on the existence of perfect matchings in certain subgraphs.
Then, we investigate two optimization problems that arise in practice. We sketch their NP-hardness and develop integer linear programs for their exact solution. Moreover, for one of them we present a greedy algorithm that guarantees a logarithmic approximation ratio.
Finally, we turn to a question that arises from the need to model uncertainty in the network structure. Given a "good" graph, how robust is it with respect to edge modifications? We present a polynomial-time algorithm for the computation of robustness.

Bio:

He is currently a post-doc researcher at Bielefeld University, where he also earned his Ph.D. degree in Computational Biology in April 2009. He holds an M.Sc. in Bioinformatics from the University of Athens and a Diploma in Electrical and Computer Engineering from the National Technical University of Athens. In general, he is interested in investigating the connections between the theoretical methods of computer science and the practical problems that arise in modern molecular biology from the analysis of quantitative data.