Theory Lunch Seminar

"Mathematical and Algorithmic Analysis of Biological data and Networks"

Charalampos Tsourakakis, Carnegie Mellon University

Tuesday, April 16, 2013 at 12:00 Noon

Lubrano Conference Room (CIT 4th floor)

In this talk I will discuss the following projects.

[1] A major computational problem in cancer biology is assessing DNA copy number variations in individual organisms or tissues. We present a simple model for inferring DNA copy numbers from noisy array Comparative Genomic Hybridization (aCGH) data. We develop two approximation algorithms for our optimization problem. The first is based on halfspace queries and the second on decomposing the problem carefully into a small number of Monge problems. The techniques we develop could be of independent interest.

Joint work with Gary Miller, Richard Peng, Russell Schwartz and Maria Tsiarli.

[2] An edge-colored graph is rainbow connected if there is a rainbow path between each pair of vertices. The rainbow connectivity of a connected graph is the minimum number of colors needed to make it rainbow connected. We prove that at the connectivity threshold, the rainbow connectivity of G(n,p) is asymptotically equal to the maximum of the number of vertices of degree one and the diameter.

Host: Eli Upfal