Related Experiment Video
Updated: Aug 3, 2026
Detecting Somatic Genetic Alterations in Tumor Specimens by Exon Capture and Massively Parallel Sequencing
Published on: October 18, 2013
A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data
Iman Hajirasouliha1, Ahmad Mahmoody2, Benjamin J Raphael1
1Department of Computer Science and Center for Computational Molecular Biology, Brown University, Providence, RI, 02906, USADepartment of Computer Science and Center for Computational Molecular Biology, Brown University, Providence, RI, 02906, USA.
This study introduces a new method to analyze tumor heterogeneity by modeling cell subpopulation relationships. The binary tree partition (BTP) approach accurately reconstructs tumor cell populations from mutation data, outperforming existing methods.
Area of Science:
- Computational Biology
- Genomics
- Cancer Research
Background:
- Tumor samples exhibit significant intra-tumor heterogeneity, with multiple cell subpopulations containing distinct somatic mutations.
- Existing methods quantify heterogeneity by clustering mutations but overlook the ancestral relationships between cell subpopulations.
- Understanding these relationships is crucial for accurate cancer subtyping and treatment strategies.
Purpose of the Study:
- To develop a novel computational framework for reconstructing tumor cell subpopulations.
- To address the limitations of current clustering approaches by incorporating subpopulation ancestry.
- To provide an accurate method for analyzing intra-tumor heterogeneity.
Main Methods:
- Introduced the binary tree partition (BTP), a combinatorial formulation for constructing tumor cell subpopulations.
- Addressed the NP-complete nature of finding a BTP with an approximation algorithm.
- Developed a recursive algorithm to identify BTPs even with noisy sequencing data.
Main Results:
- Demonstrated that finding a BTP is an NP-complete problem.
- The proposed BTP algorithm outperforms existing clustering methods on both simulated and real sequencing data.
- Successfully reconstructed tumor cell subpopulations by analyzing variant allele frequencies.
Conclusions:
- The binary tree partition (BTP) offers a more accurate method for analyzing intra-tumor heterogeneity.
- This approach enhances our ability to understand cancer evolution and identify therapeutic targets.
- The developed algorithms provide valuable tools for cancer genomics research.
