Article

A rigorous analysis of population stratification with limited data

Authors:

Kamalika Chaudhuri,

Eran Halperin,

Satish Rao,

Shuheng ZhouAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1046 - 1055

Published: 07 January 2007 Publication History

Get Access

Abstract

Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major difficulties in these studies, is the fact that the genetic components of an individual not only depend on the disease, but also on its ethnicity. Therefore, it is crucial to find methods that could reduce the population structure effects on these studies. This can be formalized as a clustering problem, where the individuals are clustered according to their genetic information.

Mathematically, we consider the problem of clustering bit "feature" vectors, where each vector represents the genetic information of an individual. Our model assumes that this bit vector is generated according to a prior probability distribution specified by the individual's membership in a population. We present methods that can cluster the vectors while attempting to optimize the number of features required. The focus of the paper is not on the algorithms, but on showing that optimizing certain objective functions on the data yields the right clustering, under the random generative model. In particular, we prove that some of the previous formulations for clustering are effective.

We consider two different clustering approaches. The first approach forms a graph, and then clusters the data using a connected components algorithm, or a max cut algorithm. The second approach tries to estimate simultanously the feature frequencies in each of the populations, and the classification of vectors into populations. We show that using the first approach Θ(logN/γ²) data (i.e., total number of features times number of vectors) is sufficient to find the correct classification, where N is the number of vectors of each population, and γ is the average l²₂ distance between the feature probability vectors of the two populations. Using the second approach, we show that O(log N/α⁴) data is enough, where α is the average l₁ distance between the populations.

We also present polynomial time algorithms for the resulting max margin which, for now, needs only slightly more data than stated above. Our methods can also be used to give a simple combinatorial algorithm for finding a bisection in a random graph that matches Boppana's convex programming approach (and McSherry's spectral results).

References

[1]

D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In Proceedings of the 18th Annual Conference on Learning Theory, pages 458--469, 2005.

Abstract

References

Cited By

Recommendations

Adjusting population distance for the dual-population genetic algorithm

A dual-population genetic algorithm for adaptive diversity control

Rigorous hitting times for binary mutations

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations