Events

Image Proteomics: from the 2DE gel images to the protein network

Carlo Cannistraci

2D-electrophoresis (2DE) and western blot (WB) are used to investigate protein differential expression in cells and tissues by comparative image analysis. We propose the expression image proteomics (IP), to identify the collection of techniques, like 2DE and WB, that are based on codification of biological information by images in which protein separation is represented. A problematic data set of 2DE maps and a second one of 2D-WB images are used to examine the pitfalls of the existing image processing techniques offering novel solutions validated by means of different machine learning evaluations. We also apply affinity propagation obtaining excellent sample clustering in both cases, and propose a mixed SVD/SVM technique generating a protein differential fingerprint (PDF) for automatic expression analysis. Finally the correlation network of the protein identified and quantified in the PDF is obtained.

Online vs. offline problems, with an application to AdWords

Fabrizio Altarelli

Online optimization problems are characterized by incomplete information. In ordinary (i.e. offline) problems, one is given an instance and is asked to find an 'optimal solution', i.e. an assignment of the variables of the problem that minimizes some cost function. In online problems, the instance of the problem is not fully known in advance, but is instead 'revealed' progressively: as time evolves, new information about the instance is acquired, and some of the variables have to be assigned based on this partial information. The study of online problems raises new questions and requires the introduction of new concepts, which I will describe briefly. I shall then apply them to the AdWords problem.

Approximation Algorithms for Budget-Constrained Auctions

John Realpe

Recently there has been a surge of interest in auctions research triggered on the one hand by auctions of bandwidth and other public assets and on the other by the popularity of Internet auctions and the possibility of new auction formats enabled by e-commerce. Simultaneous auction of items is a popular auction format. We consider the problem of maximizing total revenue in the simultaneous auction of a set of items where the bidders have individual budget constraints. Each bidder is permitted to bid on all the items of his choice and specifies his budget constraint to the auctioneer, who must select bids to maximize the revenue while ensuring that no budget constraints are violated. We show that the problem of maximizing revenue is such a setting is NP-hard, and present a factor-1.62 approximation algorithm for it. We formulate the problem as an integer program and solve a linear relaxation to obtain a fractional optimal solution, which is then deterministically rounded to obtain an integer solution. We argue that the loss in revenue incurred by the rounding procedure is bounded by a factor of 1.62.

References:
[1] R. Garg, V. Kumar and V. Pandit.

Rigorous results on the cavity method for matchings (II)

Alfredo Braunstein

We will review one recent rigorous result about the Free energy/Entropy given by the cavity method and Belief Propagation for the problem of matchings [1]. Convergence of the equations is proven for arbitrary graphs, while accuracy of the Free Energy is proven under certain conditions on the graph topology.

References:
[1] Mohsen Bayati, Chandra Nair, A rigorous proof of the cavity method for counting matchings, http://arxiv.org/abs/cond-mat/0607290

Rigorous results on the cavity method for matchings (I)

Alfredo Braunstein

We will review one recent rigorous result about the Free energy/Entropy given by the cavity method and Belief Propagation for the problem of matchings [1]. Convergence of the equations is proven for arbitrary graphs, while accuracy of the Free Energy is proven under certain conditions on the graph topology.

References:
[1] Mohsen Bayati, Chandra Nair, A rigorous proof of the cavity method for counting matchings, http://arxiv.org/abs/cond-mat/0607290

Add to calendar
Syndicate content