Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors

Mutation order in acute myeloid leukemia identifies uncommon patterns of evolution and illuminates phenotypic heterogeneity

Acute myeloid leukemia (AML) has a poor prognosis and a heterogeneous mutation landscape. Although common mutations are well-studied, little research has characterized how the sequence of mutations relates to clinical features. Using published, single-cell DNA sequencing data from three institutions, we compared clonal evolution patterns in AML to patient characteristics, disease phenotype, and outcomes. Mutation trees, which represent the order of select mutations, were created for 207 patients from targeted panel sequencing data using 1 639 162 cells, 823 mutations, and 275 samples. In 224 distinct orderings of mutated genes, mutations related to DNA methylation typically preceded those related to cell signaling, but signaling-first cases did occur, and had higher peripheral cell counts, increased signaling mutation homozygosity, and younger patient age. Serial sample analysis suggested that NPM1 and DNA methylation mutations provide an advantage to signaling mutations in AML. Interestingly, WT1 mutation evolution shared features with signaling mutations, such as WT1-early being proliferative and occurring in younger individuals, trends that remained in multivariable regression. Some mutation orderings had a worse prognosis, but this was mediated by unfavorable mutations, not mutation order. These findings add a dimension to the mutation landscape of AML, identifying uncommon patterns of leukemogenesis and shedding light on heterogeneous phenotypes.

Sc-TUSV-ext: Single-cell clonal lineage inference from single nucleotide variants (SNV), copy number alterations (CNA) and structural variants (SV)

Clonal lineage inference ("tumor phylogenetics") has become a crucial tool for making sense of somatic evolution processes that underlie cancer development and are increasingly recognized as part of normal tissue growth and aging. The inference of clonal lineage trees from single cell sequence data offers particular promise for revealing processes of somatic evolution in unprecedented detail. However, most such tools are based on fairly restrictive models of the types of mutation events observed in somatic evolution and of the processes by which they develop. The present work seeks to enhance the power and versatility of tools for single-cell lineage reconstruction by making more comprehensive use of the range of molecular variant types by which tumors evolve. We introduce Sc-TUSV-ext, an integer linear programming (ILP) based tumor phylogeny reconstruction method that, for the first time, integrates single nucleotide variants (SNV), copy number alterations (CNA) and structural variations (SV) into clonal lineage reconstruction from single-cell DNA sequencing data. We show on synthetic data that accounting for these variant types collectively leads to improved accuracy in clonal lineage reconstruction relative to prior methods that consider only subsets of the variant types. We further demonstrate the effectiveness on real data in resolving clonal evolution in the presence of multiple variant types, providing a path towards more comprehensive insight into how various forms of somatic mutability collectively shape tissue development.

ConDoR: tumor phylogeny inference with a copy-number constrained mutation loss model

A tumor contains a diverse collection of somatic mutations that reflect its past evolutionary history and that range in scale from single nucleotide variants (SNVs) to large-scale copy-number aberrations (CNAs). However, no current single-cell DNA sequencing (scDNA-seq) technology produces accurate measurements of both SNVs and CNAs, complicating the inference of tumor phylogenies. We introduce a new evolutionary model, the constrained k-Dollo model, that uses SNVs as phylogenetic markers but constrains losses of SNVs according to clusters of cells. We derive an algorithm, ConDoR, that infers phylogenies from targeted scDNA-seq data using this model. We demonstrate the advantages of ConDoR on simulated and real scDNA-seq data.

Evolutionary signatures of human cancers revealed via genomic analysis of over 35,000 patients

Recurring sequences of genomic alterations occurring across patients can highlight repeated evolutionary processes with significant implications for predicting cancer progression. Leveraging the ever-increasing availability of cancer omics data, here we unveil cancer's evolutionary signatures tied to distinct disease outcomes, representing "favored trajectories" of acquisition of driver mutations detected in patients with similar prognosis. We present a framework named ASCETIC (Agony-baSed Cancer EvoluTion InferenCe) to extract such signatures from sequencing experiments generated by different technologies such as bulk and single-cell sequencing data. We apply ASCETIC to (i) single-cell data from 146 myeloid malignancy patients and bulk sequencing from 366 acute myeloid leukemia patients, (ii) multi-region sequencing from 100 early-stage lung cancer patients, (iii) exome/genome data from 10,000+ Pan-Cancer Atlas samples, and (iv) targeted sequencing from 25,000+ MSK-MET metastatic patients, revealing subtype-specific single-nucleotide variant signatures associated with distinct prognostic clusters. Validations on several datasets underscore the robustness and generalizability of the extracted signatures.

Single-cell phylogenies reveal changes in the evolutionary rate within cancer and healthy tissues

Cell lineages accumulate somatic mutations during organismal development, potentially leading to pathological states. The rate of somatic evolution within a cell population can vary due to multiple factors, including selection, a change in the mutation rate, or differences in the microenvironment. Here, we developed a statistical test called the Poisson Tree (PT) test to detect varying evolutionary rates among cell lineages, leveraging the phylogenetic signal of single-cell DNA sequencing (scDNA-seq) data. We applied the PT test to 24 healthy and cancer samples, rejecting a constant evolutionary rate in 11 out of 15 cancer and five out of nine healthy scDNA-seq datasets. In six cancer datasets, we identified subclonal mutations in known driver genes that could explain the rate accelerations of particular cancer lineages. Our findings demonstrate the efficacy of scDNA-seq for studying somatic evolution and suggest that cell lineages often evolve at different rates within cancer and healthy tissues.

COMPASS: joint copy number and mutation phylogeny reconstruction from amplicon single-cell sequencing data

Reconstructing the history of somatic DNA alterations can help understand the evolution of a tumor and predict its resistance to treatment. Single-cell DNA sequencing (scDNAseq) can be used to investigate clonal heterogeneity and to inform phylogeny reconstruction. However, most existing phylogenetic methods for scDNAseq data are designed either for single nucleotide variants (SNVs) or for large copy number alterations (CNAs), or are not applicable to targeted sequencing. Here, we develop COMPASS, a computational method for inferring the joint phylogeny of SNVs and CNAs from targeted scDNAseq data. We evaluate COMPASS on simulated data and apply it to several datasets including a cohort of 123 patients with acute myeloid leukemia. COMPASS detected clonal CNAs that could be orthogonally validated with bulk data, in addition to subclonal ones that require single-cell resolution, some of which point toward convergent evolution.

Improving cellular phylogenies through the integrated use of mutation order and optimality principles

The study of tumor evolution is being revolutionalized by single-cell sequencing technologies that survey the somatic variation of cancer cells. In these endeavors, reliable inference of the evolutionary relationship of single cells is a key step. However, single-cell sequences contain many errors and missing bases, which necessitate advancing standard molecular phylogenetics approaches for applications in analyzing these datasets. We have developed a computational approach that integratively applies standard phylogenetic optimality principles and patterns of co-occurrence of sequence variations to produce more expansive and accurate cellular phylogenies from single-cell sequence datasets. We found the new approach to also perform well for CRISPR/Cas9 genome editing datasets, suggesting that it can be useful for various applications. We apply the new approach to some empirical datasets to showcase its use for reconstructing recurrent mutations and mutational reversals as well as for phylodynamics analysis to infer metastatic cell migrations between tumors.

Joint inference of exclusivity patterns and recurrent trajectories from tumor mutation trees

Cancer progression is an evolutionary process shaped by both deterministic and stochastic forces. Multi-region and single-cell sequencing of tumors enable high-resolution reconstruction of the mutational history of each tumor and highlight the extensive diversity across tumors and patients. Resolving the interactions among mutations and recovering recurrent evolutionary processes may offer greater opportunities for successful therapeutic strategies. To this end, we present a novel probabilistic framework, called TreeMHN, for the joint inference of exclusivity patterns and recurrent trajectories from a cohort of intra-tumor phylogenetic trees. Through simulations, we show that TreeMHN outperforms existing alternatives that can only focus on one aspect of the task. By analyzing datasets of blood, lung, and breast cancers, we find the most likely evolutionary trajectories and mutational patterns, consistent with and enriching our current understanding of tumorigenesis. Moreover, TreeMHN facilitates the prediction of tumor evolution and provides probabilistic measures on the next mutational events given a tumor tree, a prerequisite for evolution-guided treatment strategies.

Application of high-throughput single-nucleus DNA sequencing in pancreatic cancer

Despite insights gained by bulk DNA sequencing of cancer it remains challenging to resolve the admixture of normal and tumor cells, and/or of distinct tumor subclones; high-throughput single-cell DNA sequencing circumvents these and brings cancer genomic studies to higher resolution. However, its application has been limited to liquid tumors or a small batch of solid tumors, mainly because of the lack of a scalable workflow to process solid tumor samples. Here we optimize a highly automated nuclei extraction workflow that achieves fast and reliable targeted single-nucleus DNA library preparation of 38 samples from 16 pancreatic ductal adenocarcinoma patients, with an average library yield per sample of 2867 single nuclei. We demonstrate that this workflow not only performs well using low cellularity or low tumor purity samples but reveals genomic evolution patterns of pancreatic ductal adenocarcinoma as well.

Single-cell genomics in AML: extending the frontiers of AML research

The era of genomic medicine has allowed acute myeloid leukemia (AML) researchers to improve disease characterization, optimize risk-stratification systems, and develop new treatments. Although there has been significant progress, AML remains a lethal cancer because of its remarkably complex and plastic cellular architecture. This degree of heterogeneity continues to pose a major challenge, because it limits the ability to identify and therefore eradicate the cells responsible for leukemogenesis and treatment failure. In recent years, the field of single-cell genomics has led to unprecedented strides in the ability to characterize cellular heterogeneity, and it holds promise for the study of AML. In this review, we highlight advancements in single-cell technologies, outline important shortcomings in our understanding of AML biology and clinical management, and discuss how single-cell genomics can address these shortcomings as well as provide unique opportunities in basic and translational AML research.

ConDoR: Tumor phylogeny inference with a copy-number constrained mutation loss model

Tumors consist of subpopulations of cells that harbor distinct collections of somatic mutations. These mutations range in scale from single nucleotide variants (SNVs) to large-scale copy-number aberrations (CNAs). While many approaches infer tumor phylogenies using SNVs as phylogenetic markers, CNAs that overlap SNVs may lead to erroneous phylogenetic inference. Specifically, an SNV may be lost in a cell due to a deletion of the genomic segment containing the SNV. Unfortunately, no current single-cell DNA sequencing (scDNA-seq) technology produces accurate measurements of both SNVs and CNAs. For instance, recent targeted scDNA-seq technologies, such as Mission Bio Tapestri, measure SNVs with high fidelity in individual cells, but yield much less reliable measurements of CNAs. We introduce a new evolutionary model, the constrained k-Dollo model, that uses SNVs as phylogenetic markers and partial information about CNAs in the form of clustering of cells with similar copy-number profiles. This copy-number clustering constrains where loss of SNVs can occur in the phylogeny. We develop ConDoR (Constrained Dollo Reconstruction), an algorithm to infer tumor phylogenies from targeted scDNA-seq data using the constrained k-Dollo model. We show that ConDoR outperforms existing methods on simulated data. We use ConDoR to analyze a new multi-region targeted scDNA-seq dataset of 2153 cells from a pancreatic ductal adenocarcinoma (PDAC) tumor and produce a more plausible phylogeny compared to existing methods that conforms to histological results for the tumor from a previous study. We also analyze a metastatic colorectal cancer dataset, deriving a more parsimonious phylogeny than previously published analyses and with a simpler monoclonal origin of metastasis compared to the original study.

Code availability

Software is available at https://github.com/raphael-group/constrained-Dollo.

Tumor heterogeneity: preclinical models, emerging technologies, and future applications

Heterogeneity describes the differences among cancer cells within and between tumors. It refers to cancer cells describing variations in morphology, transcriptional profiles, metabolism, and metastatic potential. More recently, the field has included the characterization of the tumor immune microenvironment and the depiction of the dynamics underlying the cellular interactions promoting the tumor ecosystem evolution. Heterogeneity has been found in most tumors representing one of the most challenging behaviors in cancer ecosystems. As one of the critical factors impairing the long-term efficacy of solid tumor therapy, heterogeneity leads to tumor resistance, more aggressive metastasizing, and recurrence. We review the role of the main models and the emerging single-cell and spatial genomic technologies in our understanding of tumor heterogeneity, its contribution to lethal cancer outcomes, and the physiological challenges to consider in designing cancer therapies. We highlight how tumor cells dynamically evolve because of the interactions within the tumor immune microenvironment and how to leverage this to unleash immune recognition through immunotherapy. A multidisciplinary approach grounded in novel bioinformatic and computational tools will allow reaching the integrated, multilayered knowledge of tumor heterogeneity required to implement personalized, more efficient therapies urgently required for cancer patients.

SIEVE: joint inference of single-nucleotide variants and cell phylogeny from single-cell DNA sequencing data

We present SIEVE, a statistical method for the joint inference of somatic variants and cell phylogeny under the finite-sites assumption from single-cell DNA sequencing. SIEVE leverages raw read counts for all nucleotides and corrects the acquisition bias of branch lengths. In our simulations, SIEVE outperforms other methods in phylogenetic reconstruction and variant calling accuracy, especially in the inference of homozygous variants. Applying SIEVE to three datasets, one for triple-negative breast (TNBC), and two for colorectal cancer (CRC), we find that double mutant genotypes are rare in CRC but unexpectedly frequent in the TNBC samples.

MEDICC2: whole-genome doubling aware copy-number phylogenies for cancer evolution

Aneuploidy, chromosomal instability, somatic copy-number alterations, and whole-genome doubling (WGD) play key roles in cancer evolution and provide information for the complex task of phylogenetic inference. We present MEDICC2, a method for inferring evolutionary trees and WGD using haplotype-specific somatic copy-number alterations from single-cell or bulk data. MEDICC2 eschews simplifications such as the infinite sites assumption, allowing multiple mutations and parallel evolution, and does not treat adjacent loci as independent, allowing overlapping copy-number events. Using simulations and multiple data types from 2780 tumors, we use MEDICC2 to demonstrate accurate inference of phylogenies, clonal and subclonal WGD, and ancestral copy-number states.

Single-cell mutation calling and phylogenetic tree reconstruction with loss and recurrence

Motivation

Tumours evolve as heterogeneous populations of cells, which may be distinguished by different genomic aberrations. The resulting intra-tumour heterogeneity plays an important role in cancer patient relapse and treatment failure, so that obtaining a clear understanding of each patient’s tumour composition and evolutionary history is key for personalized therapies. Single-cell sequencing (SCS) now provides the possibility to resolve tumour heterogeneity at the highest resolution of individual tumour cells, but brings with it challenges related to the particular noise profiles of the sequencing protocols as well as the complexity of the underlying evolutionary process.

Results

By modelling the noise processes and allowing mutations to be lost or to reoccur during tumour evolution, we present a method to jointly call mutations in each cell, reconstruct the phylogenetic relationship between cells, and determine the locations of mutational losses and recurrences. Our Bayesian approach allows us to accurately call mutations as well as to quantify our certainty in such predictions. We show the advantages of allowing mutational loss or recurrence with simulated data and present its application to tumour SCS data.

Availability and implementation

SCIΦN is available at https://github.com/cbg-ethz/SCIPhIN.

Supplementary information

Supplementary data are available at Bioinformatics online.

Detection of early seeding of Richter transformation in chronic lymphocytic leukemia

Richter transformation (RT) is a paradigmatic evolution of chronic lymphocytic leukemia (CLL) into a very aggressive large B cell lymphoma conferring a dismal prognosis. The mechanisms driving RT remain largely unknown. We characterized the whole genome, epigenome and transcriptome, combined with single-cell DNA/RNA-sequencing analyses and functional experiments, of 19 cases of CLL developing RT. Studying 54 longitudinal samples covering up to 19 years of disease course, we uncovered minute subclones carrying genomic, immunogenetic and transcriptomic features of RT cells already at CLL diagnosis, which were dormant for up to 19 years before transformation. We also identified new driver alterations, discovered a new mutational signature (SBS-RT), recognized an oxidative phosphorylation (OXPHOS)^high–B cell receptor (BCR)^low-signaling transcriptional axis in RT and showed that OXPHOS inhibition reduces the proliferation of RT cells. These findings demonstrate the early seeding of subclones driving advanced stages of cancer evolution and uncover potential therapeutic targets for RT.

Single-cell genomic and transcriptomic analyses of longitudinal samples of patients with Richter syndrome reveal the presence and dynamics of clones driving transformation from chronic lymphocytic leukemia years before clinical manifestation

Accounting for errors in data improves divergence time estimates in single-cell cancer evolution

Single-cell sequencing provides a new way to explore the evolutionary history of cells. Compared to traditional bulk sequencing, where a population of heterogeneous cells is pooled to form a single observation, single-cell sequencing isolates and amplifies genetic material from individual cells, thereby preserving the information about the origin of the sequences. However, single-cell data is more error-prone than bulk sequencing data due to the limited genomic material available per cell. Here, we present error and mutation models for evolutionary inference of single-cell data within a mature and extensible Bayesian framework, BEAST2. Our framework enables integration with biologically informative models such as relaxed molecular clocks and population dynamic models. Our simulations show that modeling errors increase the accuracy of relative divergence times and substitution parameters. We reconstruct the phylogenetic history of a colorectal cancer patient and a healthy patient from single-cell DNA sequencing data. We find that the estimated times of terminal splitting events are shifted forward in time compared to models which ignore errors. We observed that not accounting for errors can overestimate the phylogenetic diversity in single-cell DNA sequencing data. We estimate that 30-50% of the apparent diversity can be attributed to error. Our work enables a full Bayesian approach capable of accounting for errors in the data within the integrative Bayesian software framework BEAST2.

CONET: copy number event tree model of evolutionary tumor history for single-cell data

Copy number alterations constitute important phenomena in tumor evolution. Whole genome single-cell sequencing gives insight into copy number profiles of individual cells, but is highly noisy. Here, we propose CONET, a probabilistic model for joint inference of the evolutionary tree on copy number events and copy number calling. CONET employs an efficient, regularized MCMC procedure to search the space of possible model structures and parameters. We introduce a range of model priors and penalties for efficient regularization. CONET reveals copy number evolution in two breast cancer samples, and outperforms other methods in tree reconstruction, breakpoint identification and copy number calling.

Reconstructing Complex Cancer Evolutionary Histories from Multiple Bulk DNA Samples Using Pairtree

Cancers are composed of genetically distinct subpopulations of malignant cells. DNA-sequencing data can be used to determine the somatic point mutations specific to each population and build clone trees describing the evolutionary relationships between them. These clone trees can reveal critical points in disease development and inform treatment. Pairtree is a new method that constructs more accurate and detailed clone trees than previously possible using variant allele frequency data from one or more bulk cancer samples. It does so by first building a Pairs Tensor that captures the evolutionary relationships between pairs of subpopulations, and then it uses these relations to constrain clone trees and infer violations of the infinite sites assumption. Pairtree can accurately build clone trees using up to 100 samples per cancer that contain 30 or more subclonal populations. On 14 B-progenitor acute lymphoblastic leukemias, Pairtree replicates or improves upon expert-derived clone tree reconstructions.

SIGNIFICANCE

Clone trees illustrate the evolutionary history of a cancer and can provide insights into how the disease changed through time (e.g., between diagnosis and relapse). Pairtree uses DNA-sequencing data from many samples of the same cancer to build more detailed and accurate clone trees than previously possible. See related commentary by Miller, p. 176. This article is highlighted in the In This Issue feature, p. 171.

Fluctuating methylation clocks for cell lineage tracing at high temporal resolution in human tissues

Molecular clocks that record cell ancestry mutate too slowly to measure the short-timescale dynamics of cell renewal in adult tissues. Here, we show that fluctuating DNA methylation marks can be used as clocks in cells where ongoing methylation and demethylation cause repeated 'flip-flops' between methylated and unmethylated states. We identify endogenous fluctuating CpG (fCpG) sites using standard methylation arrays and develop a mathematical model to quantitatively measure human adult stem cell dynamics from these data. Small intestinal crypts were inferred to contain slightly more stem cells than the colon, with slower stem cell replacement in the small intestine. Germline APC mutation increased the number of replacements per crypt. In blood, we measured rapid expansion of acute leukemia and slower growth of chronic disease. Thus, the patterns of human somatic cell birth and death are measurable with fluctuating methylation clocks (FMCs).

An overview of mutational and copy number signatures in human cancer

The genome of each cell in the human body is constantly under assault from a plethora of exogenous and endogenous processes that can damage DNA. If not successfully repaired, DNA damage generally becomes permanently imprinted in cells, and all their progenies, as somatic mutations. In most cases, the patterns of these somatic mutations contain the tell‐tale signs of the mutagenic processes that have imprinted and are termed mutational signatures. Recent pan‐cancer genomic analyses have elucidated the compendium of mutational signatures for all types of small mutational events, including (1) single base substitutions, (2) doublet base substitutions, and (3) small insertions/deletions. In contrast to small mutational events, where, in most cases, DNA damage is a prerequisite, aneuploidy, which refers to the abnormal number of chromosomes in a cell, usually develops from mistakes during DNA replication. Such mistakes include DNA replication stress, mitotic errors caused by faulty microtubule dynamics, or cohesion defects that contribute to chromosomal breakage and can lead to copy number (CN) alterations (CNAs) or even to structural rearrangements. These aberrations also leave behind genomic scars which can be inferred from sequencing as CN signatures and rearrangement signatures. The analyses of mutational signatures of small mutational events have been extensively reviewed, so we will not comprehensively re‐examine them here. Rather, our focus will be on summarising the existing knowledge for mutational signatures of CNAs. As studying CN signatures is an emerging field, we briefly summarise the utility that mutational signatures of small mutational events have provided in basic science, cancer treatment, and cancer prevention, and we emphasise the future role that CN signatures may play in each of these fields. © 2022 The Authors. The Journal of Pathology published by John Wiley & Sons Ltd on behalf of The Pathological Society of Great Britain and Ireland.

Monitoring of Leukemia Clones in B-cell Acute Lymphoblastic Leukemia at Diagnosis and During Treatment by Single-cell DNA Amplicon Sequencing

Acute lymphoblastic leukemia (ALL) is characterized by the presence of chromosomal changes, including numerical changes, translocations, and deletions, which are often associated with additional single-nucleotide mutations. In this study, we used single cell–targeted DNA sequencing to evaluate the clonal heterogeneity of B-ALL at diagnosis and during chemotherapy treatment. We designed a custom DNA amplicon library targeting mutational hotspot regions (in 110 genes) present in ALL, and we measured the presence of mutations and small insertions/deletions (indels) in bone marrow or blood samples from 12 B-ALL patients, with a median of 7973 cells per sample. Nine of the 12 cases showed at least 1 subclonal mutation, of which cases with PAX5 alterations or high hyperdiploidy (with intermediate to good prognosis) showed a high number of subclones (1 to 7) at diagnosis, defined by a variety of mutations in the JAK/STAT, RAS, or FLT3 signaling pathways. Cases with RAS pathway mutations had multiple mutations in FLT3, NRAS, KRAS, or BRAF in various clones. For those cases where we detected multiple mutational clones at diagnosis, we also studied blood samples during the first weeks of chemotherapy treatment. The leukemia clones disappeared during treatment with various kinetics, and few cells with mutations were easily detectable, even at low frequency (<0.1%). Our data illustrate that about half of the B-ALL cases show >2 subclones at diagnosis and that even very rare mutant cells can be detected at diagnosis or during treatment by single cell–targeted DNA sequencing.

SCONCE: a method for profiling copy number alterations in cancer evolution using single-cell whole genome sequencing

MOTIVATION

Copy number alterations (CNAs) are a significant driver in cancer growth and development, but remain poorly characterized on the single cell level. Although genome evolution in cancer cells is Markovian through evolutionary time, CNAs are not Markovian along the genome. However, existing methods call copy number profiles with Hidden Markov Models or change point detection algorithms based on changes in observed read depth, corrected by genome content and do not account for the stochastic evolutionary process.

RESULTS

We present a theoretical framework to use tumor evolutionary history to accurately call CNAs in a principled manner. To model the tumor evolutionary process and account for technical noise from low coverage single-cell whole genome sequencing data, we developed SCONCE, a method based on a Hidden Markov Model to analyze read depth data from tumor cells using matched normal cells as negative controls. Using a combination of public data sets and simulations, we show SCONCE accurately decodes copy number profiles, and provides a useful tool for understanding tumor evolution.

AVAILABILITYAND IMPLEMENTATION

SCONCE is implemented in C++11 and is freely available from https://github.com/NielsenBerkeleyLab/sconce.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Same-Cell Co-Occurrence of RAS Hotspot and BRAF V600E Mutations in Treatment-Naive Colorectal Cancer

PURPOSE

Mitogen-activated protein kinase pathway-activating mutations occur in the majority of colorectal cancer (CRC) cases and show mutual exclusivity. We identified 47 epidermal growth factor receptor/BRAF inhibitor-naive CRC patients with dual RAS hotspot/BRAF V600E mutations (CRC-DD) from a cohort of 4,561 CRC patients with clinical next-generation sequencing results. We aimed to define the molecular phenotypes of the CRC-DD and to test if the dual RAS hotspot/BRAF V600E mutations coexist within the same cell.

MATERIALS AND METHODS

We developed a single-cell genotyping method with a mutation detection rate of 96.3% and a genotype prediction accuracy of 92.1%. Mutations in the CRC-DD cohort were analyzed for clonality, allelic imbalance, copy number, and overall survival.

RESULTS

Application of single-cell genotyping to four CRC-DD revealed the co-occurrence of both mutations in the following percentages of cells per case: NRAS G13D/KRAS G12C, 95%; KRAS G12D/NRAS G12V, 48%; BRAF V600E/KRAS G12D, 44%; and KRAS G12D/NRAS G13V, 14%, respectively. Allelic imbalance favoring the oncogenic allele was less frequent in CRC-DD (24 of 76, 31.5%, somatic mutations) compared with a curated cohort of CRC with a single-driver mutation (CRC-SD; 119 of 232 mutations, 51.3%; P = .013). Microsatellite instability-high status was enriched in CRC-DD compared with CRC-SD (23% v 11.4%, P = .028). Of the seven CRC-DD cases with multiregional sequencing, five retained both driver mutations throughout all sequenced tumor sites. Both CRC-DD cases with discordant multiregional sequencing were microsatellite instability-high.

CONCLUSION

Our findings indicate that dual-driver mutations occur in a rare subset of CRC, often within the same tumor cells and across multiple tumor sites. Their presence and a lower rate of allelic imbalance may be related to dose-dependent signaling within the mitogen-activated protein kinase pathway.

Biallelic mutations in cancer genomes reveal local mutational determinants

The infinite sites model of molecular evolution posits that every position in the genome is mutated at most once1. By restricting the number of possible mutation histories, haplotypes and alleles, it forms a cornerstone of tumor phylogenetic analysis2 and is often implied when calling, phasing and interpreting variants3,4 or studying the mutational landscape as a whole5. Here we identify 18,295 biallelic mutations, where the same base is mutated independently on both parental copies, in 559 (21%) bulk sequencing samples from the Pan-Cancer Analysis of Whole Genomes study. Biallelic mutations reveal ultraviolet light damage hotspots at E26 transformation-specific (ETS) and nuclear factor of activated T cells (NFAT) binding sites, and hypermutable motifs in POLE-mutant and other cancers. We formulate recommendations for variant calling and provide frameworks to model and detect biallelic mutations. These results highlight the need for accurate models of mutation rates and tumor evolution, as well as their inference from sequencing data.

CellPhy: accurate and fast probabilistic inference of single-cell phylogenies from scDNA-seq data

We introduce CellPhy, a maximum likelihood framework for inferring phylogenetic trees from somatic single-cell single-nucleotide variants. CellPhy leverages a finite-site Markov genotype model with 16 diploid states and considers amplification error and allelic dropout. We implement CellPhy into RAxML-NG, a widely used phylogenetic inference package that provides statistical confidence measurements and scales well on large datasets with hundreds or thousands of cells. Comprehensive simulations suggest that CellPhy is more robust to single-cell genomics errors and outperforms state-of-the-art methods under realistic scenarios, both in accuracy and speed. CellPhy is freely available at https://github.com/amkozlov/cellphy .

Somatic variant calling from single-cell DNA sequencing data

Single-cell sequencing has gained popularity in recent years. Despite its numerous applications, single-cell DNA sequencing data is highly error-prone due to technical biases arising from uneven sequencing coverage, allelic dropout, and amplification error. With these artifacts, the identification of somatic genomic variants becomes a challenging task, and over the years, several methods have been developed explicitly for this type of data. Single-cell variant callers implement distinct strategies, make different use of the data, and typically result in many discordant calls when applied to real data. Here, we review current approaches for single-cell variant calling, emphasizing single nucleotide variants. We highlight their potential benefits and shortcomings to help users choose a suitable tool for their data at hand.

Simpler and Faster Development of Tumor Phylogeny Pipelines

In the recent years, there has been an increasing amount of single-cell sequencing studies, producing a considerable number of new data sets. This has particularly affected the field of cancer analysis, where more and more articles are published using this sequencing technique that allows for capturing more detailed information regarding the specific genetic mutations on each individually sampled cell. As the amount of information increases, it is necessary to have more sophisticated and rapid tools for analyzing the samples. To this goal, we developed plastic (PipeLine Amalgamating Single-cell Tree Inference Components), an easy-to-use and quick to adapt pipeline that integrates three different steps: (1) to simplify the input data, (2) to infer tumor phylogenies, and (3) to compare the phylogenies. We have created a pipeline submodule for each of those steps and developed new in-memory data structures that allow for easy and transparent sharing of the information across the tools implementing the above steps. While we use existing open source tools for those steps, we have extended the tool used for simplifying the input data, incorporating two machine learning procedures-which greatly reduce the running time without affecting the quality of the downstream analysis. Moreover, we have introduced the capability of producing some plots to quickly visualize results.

DeCiFering the elusive cancer cell fraction in tumor heterogeneity and evolution

The cancer cell fraction (CCF), or proportion of cancerous cells in a tumor containing a single-nucleotide variant (SNV), is a fundamental statistic used to quantify tumor heterogeneity and evolution. Existing CCF estimation methods from bulk DNA sequencing data assume that every cell with an SNV contains the same number of copies of the SNV. This assumption is unrealistic in tumors with copy-number aberrations that alter SNV multiplicities. Furthermore, the CCF does not account for SNV losses due to copy-number aberrations, confounding downstream phylogenetic analyses. We introduce DeCiFer, an algorithm that overcomes these limitations by clustering SNVs using a novel statistic, the descendant cell fraction (DCF). The DCF quantifies both the prevalence of an SNV at the present time and its past evolutionary history using an evolutionary model that allows mutation losses. We show that DeCiFer yields more parsimonious reconstructions of tumor evolution than previously reported for 49 prostate cancer samples.

Exact site frequency spectra of neutrally evolving tumors: A transition between power laws reveals a signature of cell viability

The site frequency spectrum (SFS) is a popular summary statistic of genomic data. While the SFS of a constant-sized population undergoing neutral mutations has been extensively studied in population genetics, the rapidly growing amount of cancer genomic data has attracted interest in the spectrum of an exponentially growing population. Recent theoretical results have generally dealt with special or limiting cases, such as considering only cells with an infinite line of descent, assuming deterministic tumor growth, or taking large-time or large-population limits. In this work, we derive exact expressions for the expected SFS of a cell population that evolves according to a stochastic branching process, first for cells with an infinite line of descent and then for the total population, evaluated either at a fixed time (fixed-time spectrum) or at the stochastic time at which the population reaches a certain size (fixed-size spectrum). We find that while the rate of mutation scales the SFS of the total population linearly, the rates of cell birth and cell death change the shape of the spectrum at the small-frequency end, inducing a transition between a 1/j² power-law spectrum and a 1/j spectrum as cell viability decreases. We show that this insight can in principle be used to estimate the ratio between the rate of cell death and cell birth, as well as the mutation rate, using the site frequency spectrum alone. Although the discussion is framed in terms of tumor dynamics, our results apply to any exponentially growing population of individuals undergoing neutral mutations.

Conifer: clonal tree inference for tumor heterogeneity with single-cell and bulk sequencing data

BACKGROUND

Genetic heterogeneity of a cancer tumor that develops during clonal evolution is one of the reasons for cancer treatment failure, by increasing the chance of drug resistance. Clones are cell populations with different genotypes, resulting from differences in somatic mutations that occur and accumulate during cancer development. An appropriate approach for identifying clones is determining the variant allele frequency of mutations that occurred in the tumor. Although bulk sequencing data can be used to provide that information, the frequencies are not informative enough for identifying different clones with the same prevalence and their evolutionary relationships. On the other hand, single-cell sequencing data provides valuable information about branching events in the evolution of a cancerous tumor. However, the temporal order of mutations may be determined with ambiguities using only single-cell data, while variant allele frequencies from bulk sequencing data can provide beneficial information for inferring the temporal order of mutations with fewer ambiguities.

RESULT

In this study, a new method called Conifer (ClONal tree Inference For hEterogeneity of tumoR) is proposed which combines aggregated variant allele frequency from bulk sequencing data with branching event information from single-cell sequencing data to more accurately identify clones and their evolutionary relationships. It is proven that the accuracy of clone identification and clonal tree inference is increased by using Conifer compared to other existing methods on various sets of simulated data. In addition, it is discussed that the evolutionary tree provided by Conifer on real cancer data sets is highly consistent with information in both bulk and single-cell data.

CONCLUSIONS

In this study, we have provided an accurate and robust method to identify clones of tumor heterogeneity and their evolutionary history by combining single-cell and bulk sequencing data.

Studying the History of Tumor Evolution from Single-Cell Sequencing Data by Exploring the Space of Binary Matrices

Single-cell sequencing (SCS) data have great potential in reconstructing the evolutionary history of tumors. Rapid advances in SCS technology in the past decade were followed by the design of various computational methods for inferring trees of tumor evolution. Some of the earliest methods were based on the direct search in the space of trees with the goal of finding the maximum likelihood tree. However, it can be shown that instead of searching directly in the tree space, we can perform a search in the space of binary matrices and obtain maximum likelihood tree directly from the maximum likelihood matrix. The potential of the latter tree search strategy has recently been recognized by different research groups and several related methods were published in the past 2 years. Here we provide a review of the theoretical background of these methods and a detailed discussion, which are largely missing in the available publications, of the correlation between the two tree search strategies. We also discuss each of the existing methods based on the search in the space of binary matrices and summarize the best-known single-cell DNA sequencing data sets, which can be used in the future for assessing performance on real data of newly developed methods.

doubletD: detecting doublets in single-cell DNA sequencing data

Motivation

While single-cell DNA sequencing (scDNA-seq) has enabled the study of intratumor heterogeneity at an unprecedented resolution, current technologies are error-prone and often result in doublets where two or more cells are mistaken for a single cell. Not only do doublets confound downstream analyses, but the increase in doublet rate is also a major bottleneck preventing higher throughput with current single-cell technologies. Although doublet detection and removal are standard practice in scRNA-seq data analysis, options for scDNA-seq data are limited. Current methods attempt to detect doublets while also performing complex downstream analyses tasks, leading to decreased efficiency and/or performance.

Results

We present doubletD, the first standalone method for detecting doublets in scDNA-seq data. Underlying our method is a simple maximum likelihood approach with a closed-form solution. We demonstrate the performance of doubletD on simulated data as well as real datasets, outperforming current methods for downstream analysis of scDNA-seq data that jointly infer doublets as well as standalone approaches for doublet detection in scRNA-seq data. Incorporating doubletD in scDNA-seq analysis pipelines will reduce complexity and lead to more accurate results.

Availability and implementation

https://github.com/elkebir-group/doubletD.

Supplementary information

Supplementary data are available at Bioinformatics online.

Distinguishing linear and branched evolution given single-cell DNA sequencing data of tumors

Background

Cancer arises from an evolutionary process where somatic mutations give rise to clonal expansions. Reconstructing this evolutionary process is useful for treatment decision-making as well as understanding evolutionary patterns across patients and cancer types. In particular, classifying a tumor’s evolutionary process as either linear or branched and understanding what cancer types and which patients have each of these trajectories could provide useful insights for both clinicians and researchers. While comprehensive cancer phylogeny inference from single-cell DNA sequencing data is challenging due to limitations with current sequencing technology and the complexity of the resulting problem, current data might provide sufficient signal to accurately classify a tumor’s evolutionary history as either linear or branched.

Results

We introduce the Linear Perfect Phylogeny Flipping (LPPF) problem as a means of testing two alternative hypotheses for the pattern of evolution, which we prove to be NP-hard. We develop Phyolin, which uses constraint programming to solve the LPPF problem. Through both in silico experiments and real data application, we demonstrate the performance of our method, outperforming a competing machine learning approach.

Conclusion

Phyolin is an accurate, easy to use and fast method for classifying an evolutionary trajectory as linear or branched given a tumor’s single-cell DNA sequencing data.

Single-cell DNA amplicon sequencing reveals clonal heterogeneity and evolution in T-cell acute lymphoblastic leukemia

T-cell acute lymphoblastic leukemia (T-ALL) is an aggressive leukemia that is most frequent in children and is characterized by the presence of few chromosomal rearrangements and 10 to 20 somatic mutations in protein-coding regions at diagnosis. The majority of T-ALL cases harbor activating mutations in NOTCH1 together with mutations in genes implicated in kinase signaling, transcriptional regulation, or protein translation. To obtain more insight in the level of clonal heterogeneity at diagnosis and during treatment, we used single-cell targeted DNA sequencing with the Tapestri platform. We designed a custom ALL panel and obtained accurate single-nucleotide variant and small insertion-deletion mutation calling for 305 amplicons covering 110 genes in about 4400 cells per sample and time point. A total of 108 188 cells were analyzed for 25 samples of 8 T-ALL patients. We typically observed a major clone at diagnosis (>35% of the cells) accompanied by several minor clones of which some were less than 1% of the total number of cells. Four patients had >2 NOTCH1 mutations, some of which present in minor clones, indicating a strong pressure to acquire NOTCH1 mutations in developing T-ALL cells. By analyzing longitudinal samples, we detected the presence and clonal nature of residual leukemic cells and clones with a minor presence at diagnosis that evolved to clinically relevant major clones at later disease stages. Therefore, single-cell DNA amplicon sequencing is a sensitive assay to detect clonal architecture and evolution in T-ALL.

The Bourque distances for mutation trees of cancers

Background

Mutation trees are rooted trees in which nodes are of arbitrary degree and labeled with a mutation set. These trees, also referred to as clonal trees, are used in computational oncology to represent the mutational history of tumours. Classical tree metrics such as the popular Robinson–Foulds distance are of limited use for the comparison of mutation trees. One reason is that mutation trees inferred with different methods or for different patients often contain different sets of mutation labels.

Results

We generalize the Robinson–Foulds distance into a set of distance metrics called Bourque distances for comparing mutation trees. We show the basic version of the Bourque distance for mutation trees can be computed in linear time. We also make a connection between the Robinson–Foulds distance and the nearest neighbor interchange distance.

Supplementary Information

The online version contains supplementary material available at 10.1186/s13015-021-00188-3.

GRMT: Generative Reconstruction of Mutation Tree From Scratch Using Single-Cell Sequencing Data

Single-cell sequencing (SCS) now promises the landscape of genetic diversity at single cell level, and is particularly useful to reconstruct the evolutionary history of tumor. There are multiple types of noise that make the SCS data notoriously error-prone, and significantly complicate tumor tree reconstruction. Existing methods for tumor phylogeny estimation suffer from either high computational intensity or low-resolution indication of clonal architecture, giving a necessity of developing new methods for efficient and accurate reconstruction of tumor trees. We introduce GRMT (Generative Reconstruction of Mutation Tree from scratch), a method for inferring tumor mutation tree from SCS data. GRMT exploits the k-Dollo parsimony model to allow each mutation to be gained once and lost at most k times. Under this constraint on mutation evolution, GRMT searches for mutation tree structures from a perspective of tree generation from scratch, and implements it to an iterative process that gradually increases the tree size by introducing a new mutation per time until a complete tree structure that contains all mutations is obtained. This enables GRMT to efficiently recover the chronological order of mutations and scale well to large datasets. Extensive evaluations on simulated and real datasets suggest GRMT outperforms the state-of-the-arts in multiple performance metrics. The GRMT software is freely available at https://github.com/qasimyu/grmt.

Effective Clustering for Single Cell Sequencing Cancer Data

Single cell sequencing (SCS) technologies provide a level of resolution that makes it indispensable for inferring from a sequenced tumor, evolutionary trees or phylogenies representing an accumulation of cancerous mutations. A drawback of SCS is elevated false negative and missing value rates, resulting in a large space of possible solutions, which in turn makes it difficult, sometimes infeasible using current approaches and tools. One possible solution is to reduce the size of an SCS instance --- usually represented as a matrix of presence, absence, and uncertainty of the mutations found in the different sequenced cells --- and to infer the tree from this reduced-size instance. In this work, we present a new clustering procedure aimed at clustering such categorical vector, or matrix data --- here representing SCS instances, called celluloid. We show that celluloid clusters mutations with high precision: never pairing too many mutations that are unrelated in the ground truth, but also obtains accurate results in terms of the phylogeny inferred downstream from the reduced instance produced by this method. We demonstrate the usefulness of a clustering step by applying the entire pipeline (clustering + inference method) to a real dataset, showing a significant reduction in the runtime, raising considerably the upper bound on the size of SCS instances which can be solved in practice. Our approach, celluloid: clustering single cell sequencing data around centroids is available at https://github.com/AlgoLab/celluloid/ under an MIT license, as well as on the Python Package Index (PyPI) at https://pypi.org/project/celluloid-clust/.

Triplet-based similarity score for fully multilabeled trees with poly-occurring labels

MOTIVATION

The latest advances in cancer sequencing, and the availability of a wide range of methods to infer the evolutionary history of tumors, have made it important to evaluate, reconcile and cluster different tumor phylogenies. Recently, several notions of distance or similarities have been proposed in the literature, but none of them has emerged as the golden standard. Moreover, none of the known similarity measures is able to manage mutations occurring multiple times in the tree, a circumstance often occurring in real cases.

RESULTS

To overcome these limitations, in this article, we propose MP3, the first similarity measure for tumor phylogenies able to effectively manage cases where multiple mutations can occur at the same time and mutations can occur multiple times. Moreover, a comparison of MP3 with other measures shows that it is able to classify correctly similar and dissimilar trees, both on simulated and on real data.

AVAILABILITY AND IMPLEMENTATION

An open source implementation of MP3 is publicly available at https://github.com/AlgoLab/mp3treesim.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Inferring cancer progression from Single-Cell Sequencing while allowing mutation losses

Motivation

In recent years, the well-known Infinite Sites Assumption has been a fundamental feature of computational methods devised for reconstructing tumor phylogenies and inferring cancer progressions. However, recent studies leveraging single-cell sequencing (SCS) techniques have shown evidence of the widespread recurrence and, especially, loss of mutations in several tumor samples. While there exist established computational methods that infer phylogenies with mutation losses, there remain some advancements to be made.

Results

We present Simulated Annealing Single-Cell inference (SASC): a new and robust approach based on simulated annealing for the inference of cancer progression from SCS datasets. In particular, we introduce an extension of the model of evolution where mutations are only accumulated, by allowing also a limited amount of mutation loss in the evolutionary history of the tumor: the Dollo-k model. We demonstrate that SASC achieves high levels of accuracy when tested on both simulated and real datasets and in comparison with some other available methods.

Availability and implementation

The SASC tool is open source and available at https://github.com/sciccolella/sasc.

Supplementary information

Supplementary data are available at Bioinformatics online.

Single-cell sequencing technology in tumor research

Tumor heterogeneity is a key characteristic of malignant tumors and a significant obstacle in cancer treatment and research. Although bulk tissue sequencing has wide coverage and high accuracy, it can only represent the dominant cell signal information of each sample, while masking the unique gene expression of rare cells; therefore it cannot represent genes that are unstable within a subgroup, but unchanged in a majority of cells. With the progress of genomic technology, the emergence of single-cell sequencing (SCS) has effectively solved the above problem. Genetic, transcriptomic and epigenetic sequencing at the single-cell level provides an important basis for us to correctly classify the cell subsets of heterogeneous tumor populations and to reveal the process of complex changes in tumor cells at the molecular level. Single-cell sequencing technology has been applied to the field of cancer, revealing exciting discoveries in the potential mechanisms of tumor driver gene mutation, clonal evolution, invasion and metastasis. It also provides favorable conditions for developing new tumor biomarkers and providing more accurate and individualized targeted tumor therapy. Herein, we review the steps and methods of single-cell sequencing and highlight the application of SCS in tumor diagnosis and clinical treatment.

Evolution of late-stage metastatic melanoma is dominated by aneuploidy and whole genome doubling

Although melanoma is initiated by acquisition of point mutations and limited focal copy number alterations in melanocytes-of-origin, the nature of genetic changes that characterise lethal metastatic disease is poorly understood. Here, we analyze the evolution of human melanoma progressing from early to late disease in 13 patients by sampling their tumours at multiple sites and times. Whole exome and genome sequencing data from 88 tumour samples reveals only limited gain of point mutations generally, with net mutational loss in some metastases. In contrast, melanoma evolution is dominated by whole genome doubling and large-scale aneuploidy, in which widespread loss of heterozygosity sculpts the burden of point mutations, neoantigens and structural variants even in treatment-naïve and primary cutaneous melanomas in some patients. These results imply that dysregulation of genomic integrity is a key driver of selective clonal advantage during melanoma progression.

MEDALT: single-cell copy number lineage tracing enabling gene discovery

We present a Minimal Event Distance Aneuploidy Lineage Tree (MEDALT) algorithm that infers the evolution history of a cell population based on single-cell copy number (SCCN) profiles, and a statistical routine named lineage speciation analysis (LSA), whichty facilitates discovery of fitness-associated alterations and genes from SCCN lineage trees. MEDALT appears more accurate than phylogenetics approaches in reconstructing copy number lineage. From data from 20 triple-negative breast cancer patients, our approaches effectively prioritize genes that are essential for breast cancer cell fitness and predict patient survival, including those implicating convergent evolution.The source code of our study is available at https://github.com/KChen-lab/MEDALT .

A practical guide to cancer subclonal reconstruction from DNA sequencing

Subclonal reconstruction from bulk tumor DNA sequencing has become a pillar of cancer evolution studies, providing insight into the clonality and relative ordering of mutations and mutational processes. We provide an outline of the complex computational approaches used for subclonal reconstruction from single and multiple tumor samples. We identify the underlying assumptions and uncertainties in each step and suggest best practices for analysis and quality assessment. This guide provides a pragmatic resource for the growing user community of subclonal reconstruction methods.

Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine

Tumors contain multiple subpopulations of genetically distinct cancer cells. Reconstructing their evolutionary history can improve our understanding of how cancers develop and respond to treatment. Subclonal reconstruction methods cluster mutations into groups that co-occur within the same subpopulations, estimate the frequency of cells belonging to each subpopulation, and infer the ancestral relationships among the subpopulations by constructing a clone tree. However, often multiple clone trees are consistent with the data and current methods do not efficiently capture this uncertainty; nor can these methods scale to clone trees with a large number of subclonal populations.

Here, we formalize the notion of a partially-defined clone tree (partial clone tree for short) that defines a subset of the pairwise ancestral relationships in a clone tree, thereby implicitly representing the set of all clone trees that have these defined pairwise relationships. Also, we introduce a special partial clone tree, the Maximally-Constrained Ancestral Reconstruction (MAR), which summarizes all clone trees fitting the input data equally well. Finally, we extend commonly used clone tree validity conditions to apply to partial clone trees and describe SubMARine, a polynomial-time algorithm producing the subMAR, which approximates the MAR and guarantees that its defined relationships are a subset of those present in the MAR. We also extend SubMARine to work with subclonal copy number aberrations and define equivalence constraints for this purpose. Further, we extend SubMARine to permit noise in the estimates of the subclonal frequencies while retaining its validity conditions and guarantees. In contrast to other clone tree reconstruction methods, SubMARine runs in time and space that scale polynomially in the number of subclones.

We show through extensive noise-free simulation, a large lung cancer dataset and a prostate cancer dataset that the subMAR equals the MAR in all cases where only a single clone tree exists and that it is a perfect match to the MAR in most of the other cases. Notably, SubMARine runs in less than 70 seconds on a single thread with less than one Gb of memory on all datasets presented in this paper, including ones with 50 nodes in a clone tree. On the real-world data, SubMARine almost perfectly recovers the previously reported trees and identifies minor errors made in the expert-driven reconstructions of those trees.

The freely-available open-source code implementing SubMARine can be downloaded at https://github.com/morrislab/submarine.

Cancer cells accumulate mutations over time and consist of genetically distinct subpopulations. Their evolutionary history (as represented by tumor phylogenies) can be inferred from bulk cancer genome sequencing data. Current tumor phylogeny reconstruction methods have two main issues: they are slow, and they do not efficiently represent uncertainty in the reconstruction.

To address these issues, we developed SubMARine, a fast algorithm that summarizes all valid phylogenies in an intuitive format. SubMARine solved all reconstruction problems in this manuscript in less than 70 seconds, orders of magnitude faster than other methods. These reconstruction problems included those with up to 50 subclones; problems that are too large for other algorithms to even attempt. SubMARine achieves these result because, unlike other algorithms, it performs its reconstruction by identifying an upper-bound on the solution set of trees and the amount of noise in the estimates of the subclonal frequencies. In the vast majority of cases we checked, i. e. an extensive noise-free simulation, a lung cancer and a prostate cancer dataset, this upper bound is tight: when only a single solution exists, SubMARine converges to it every time. When multiple solutions exist, our algorithm correctly recovers the uncertain relationships in 71% of cases.

In addition to solving these two major challenges, we introduce some useful new concepts for and open research problems in the field of tumor phylogeny reconstruction. Specifically, we formalize the concept of a partial clone tree which provides a set of constraints on the solution set of clone trees; and provide a complete set of conditions under which a partial clone tree is valid. These conditions guarantee that all trees in the solution set satisfy the constraints implied by the partial clone tree.

An Overview of Advances in Cell-Based Cancer Immunotherapies Based on the Multiple Immune-Cancer Cell Interactions

Tumors have a complex ecosystem in which behavior and fate are determined by the interaction of diverse cancerous and noncancerous cells at local and systemic levels. A number of studies indicate that various immune cells participate in tumor development (Fig. 1). In this review, we will discuss interactions among T lymphocytes (T cells), B cells, natural killer (NK) cells, dendritic cells (DCs), tumor-associated macrophages (TAMs), neutrophils, and myeloid-derived suppressor cells (MDSCs). In addition, we will touch upon attempts to either use or block subsets of immune cells to target cancer.

gpps: an ILP-based approach for inferring cancer progression with mutation losses from single cell data

BACKGROUND

Cancer progression reconstruction is an important development stemming from the phylogenetics field. In this context, the reconstruction of the phylogeny representing the evolutionary history presents some peculiar aspects that depend on the technology used to obtain the data to analyze: Single Cell DNA Sequencing data have great specificity, but are affected by moderate false negative and missing value rates. Moreover, there has been some recent evidence of back mutations in cancer: this phenomenon is currently widely ignored.

RESULTS

We present a new tool, gpps, that reconstructs a tumor phylogeny from Single Cell Sequencing data, allowing each mutation to be lost at most a fixed number of times. The General Parsimony Phylogeny from Single cell (gpps) tool is open source and available at https://github.com/AlgoLab/gpps .

CONCLUSIONS

gpps provides new insights to the analysis of intra-tumor heterogeneity by proposing a new progression model to the field of cancer phylogeny reconstruction on Single Cell data.

Tumor Phylogeny Topology Inference via Deep Learning

Principled computational approaches for tumor phylogeny reconstruction via single-cell sequencing typically aim to build the most likely perfect phylogeny tree from the noisy genotype matrix - which represents genotype calls of single cells. This problem is NP-hard, and as a result, existing approaches aim to solve relatively small instances of it through combinatorial optimization techniques or Bayesian inference. As expected, even when the goal is to infer basic topological features of the tumor phylogeny, rather than reconstructing the topology entirely, these approaches could be prohibitively slow. In this paper, we introduce fast deep learning solutions to the problems of inferring whether the most likely tree has a linear (chain) or branching topology and whether a perfect phylogeny is feasible from a given genotype matrix. We also present a reinforcement learning approach for reconstructing the most likely tumor phylogeny. This preliminary work demonstrates that data-driven approaches can reconstruct key features of tumor evolution.

Inference of mutability landscapes of tumors from single cell sequencing data

One of the hallmarks of cancer is the extremely high mutability and genetic instability of tumor cells. Inherent heterogeneity of intra-tumor populations manifests itself in high variability of clone instability rates. Analogously to fitness landscapes, the instability rates of clonal populations form their mutability landscapes. Here, we present MULAN (MUtability LANdscape inference), a maximum-likelihood computational framework for inference of mutation rates of individual cancer subclones using single-cell sequencing data. It utilizes the partial information about the orders of mutation events provided by cancer mutation trees and extends it by inferring full evolutionary history and mutability landscape of a tumor. Evaluation of mutation rates on the level of subclones rather than individual genes allows to capture the effects of genomic interactions and epistasis. We estimate the accuracy of our approach and demonstrate that it can be used to study the evolution of genetic instability and infer tumor evolutionary history from experimental data. MULAN is available at https://github.com/compbel/MULAN.