A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data. Academic Article uri icon

Overview

MeSH

  • Cluster Analysis
  • Gene Frequency
  • Humans
  • Leukemia, Myeloid, Acute
  • Mutation

MeSH Major

  • Algorithms
  • High-Throughput Nucleotide Sequencing
  • Neoplasms
  • Sequence Analysis, DNA

abstract

  • High-throughput sequencing of tumor samples has shown that most tumors exhibit extensive intra-tumor heterogeneity, with multiple subpopulations of tumor cells containing different somatic mutations. Recent studies have quantified this intra-tumor heterogeneity by clustering mutations into subpopulations according to the observed counts of DNA sequencing reads containing the variant allele. However, these clustering approaches do not consider that the population frequencies of different tumor subpopulations are correlated by their shared ancestry in the same population of cells. We introduce the binary tree partition (BTP), a novel combinatorial formulation of the problem of constructing the subpopulations of tumor cells from the variant allele frequencies of somatic mutations. We show that finding a BTP is an NP-complete problem; derive an approximation algorithm for an optimization version of the problem; and present a recursive algorithm to find a BTP with errors in the input. We show that the resulting algorithm outperforms existing clustering approaches on simulated and real sequencing data. Python and MATLAB implementations of our method are available at http://compbio.cs.brown.edu/software/ . © The Author 2014. Published by Oxford University Press.

publication date

  • June 15, 2014

has subject area

  • Algorithms
  • Cluster Analysis
  • Gene Frequency
  • High-Throughput Nucleotide Sequencing
  • Humans
  • Leukemia, Myeloid, Acute
  • Mutation
  • Neoplasms
  • Sequence Analysis, DNA

Research

keywords

  • Journal Article

Identity

Language

  • eng

PubMed Central ID

  • PMC4058927

Digital Object Identifier (DOI)

  • 10.1093/bioinformatics/btu284

PubMed ID

  • 24932008

Additional Document Info

start page

  • i78

end page

  • i86

volume

  • 30

number

  • 12