Title: Combinatorial Algorithms, Genome Variations, and Cancer Progression Abstract: Large-scale sequencing projects involving thousands of genomes are underway and require advanced algorithmic methods, for the purpose of analysis. In this talk, we review the fundamental concepts of genome variations and applications in massive genomic studies (e.g. the 1000 Genomes Project). We then focus specifically on combinatorial algorithms to identify different types of genome variations. Using next-generation sequencing, we demonstrate that our algorithms are capable of handling multiple genomes simultaneously. Next-generation sequencing technologies have also enabled the sequencing of many cancer genomes. Recent studies of tumor samples have shown that most tumors exhibit extensive intra-tumor heterogeneity, with multiple subpopulations of tumor cells containing different somatic mutations. We introduce Binary Tree Partition, a novel combinatorial formulation of the problem of constructing the subpopulations of tumor cells. We show that finding a binary tree partition is NP-complete; derive an approximation algorithm for an optimization version of the problem; and present a recursive algorithm to find a binary tree partition with errors in the input.