Mining κ-median chromosome association graphs from a population of heterogeneous cells

Finding the structural pattern from a set of objects is a commonly encountered prototype learning problem in machine learning and pattern recognition. In graph domain, such a structure is called median graph. Existing research has demonstrated that computing an accurate median graph could be rather challenging. In this paper, we present a new technique for mining κ-median graphs from a population of heterogeneous cells. Each median graph is a representative structure of chromosome associations of a subset of the cells in the population. Comparing to existing techniques, our technique has several unique advantages. Firstly, it reveals, for the first time, the level of associations (or degree of associations) among the chromosomes. Secondly, it generates multiple median graphs simultaneously, and therefore can be used to handle heterogeneous data. Our technique is based on a number of interesting ideas, such as adaptive sampling, semi-definite programming model, embedding, and local search on uncertain data. Experimental results on both random and biological data sets suggest that our technique yield near optimal solutions.