A rigorous analysis of population stratification with limited data

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²2 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 l1 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.
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: Arora Sanjeev , Ravi Kannan, Learning mixtures of arbitrary gaussians, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.247-257, July 2001, Hersonissos, Greece [doi>10.1145/380752.380808]
• 4: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.238, November 16-19, 2002
• 5: R. Boppana. Eigenvalues and graph bisection: An average case analysis. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 280--285, 1987.
• 6: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 7: Ted Carson , Russell Impagliazzo, Hill-climbing finds random planted bisections, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.903-909, January 07-09, 2001, Washington, D.C., United States
• 8: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with Qualitative Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.524, October 11-14, 2003
• 9: Anne Condon , Richard M. Karp, Algorithms for graph partitioning on the planted partition model, Random Structures & Algorithms, v.18 n.2, p.116-140, March 1,2001 [doi>10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2]
• 10: Anirban Dasgupta , John Hopcroft , Jon Kleinberg , Mark Sandler, On Learning Mixtures of Heavy-Tailed Distributions, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.491-500, October 23-25, 2005 [doi>10.1109/SFCS.2005.56]
• 11: Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
• 12: Mark Jerrum and Gregory Sorkin. Simulated annealing for graph bisection. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 94--103, 1993.
• 13: Jon Kleinberg , Mark Sandler, Convergent algorithms for collaborative filtering, Proceedings of the 4th ACM conference on Electronic commerce, p.1-10, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779929]
• 14: Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007439]
• 15: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
• 16: F. McSherry, Spectral Partitioning of Random Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.529, October 14-17, 2001
• 17: A. Panconesi and D. Dubhashi. Concentration of measure for the analysis of randomised algorithms. Draft.
• 18: Alkes L. Price, Nick J. Patterson, Robert M. Plenge, Michael E. Weinblatt, Nancy A. Shadick, and David Reich. Principal components analysis corrects for stratification in genome-wide association studies. Nature Genetics, 38(8):904--909, July 2006.
• 19: J. K. Pritchard, M. Stephens, and P. Donnelly. Inference of population structure using multilocus genotype data. Genetics, 155:954--959, June 2000.
• 20: Ron Shamir , Roded Sharan , Dekel Tsur, Cluster Graph Modification Problems, Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, p.379-390, June 13-15, 2002
• 21: Chaitanya Swamy, Correlation Clustering: maximizing agreements via semidefinite programming, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 22: Santosh Vempala , Grant Wang, A Spectral Algorithm for Learning Mixtures of Distributions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.113, November 16-19, 2002
• 23: Shuheng Zhou , Gregory R. Ganger , Bruce M. Maggs, Routing, disjoint paths, and classification, Carnegie Mellon University, Pittsburgh, PA, 2006