Discovering significant evolutionary trajectories in cancer phylogenies

MOTIVATION

Tumors are the result of a somatic evolutionary process leading to substantial intra-tumor heterogeneity. Single-cell and multi-region sequencing enable the detailed characterization of the clonal architecture of tumors and have highlighted its extensive diversity across tumors. While several computational methods have been developed to characterize the clonal composition and the evolutionary history of tumors, the identification of significantly conserved evolutionary trajectories across tumors is still a major challenge.

RESULTS

We present a new algorithm, MAximal tumor treeS TRajectOries (MASTRO), to discover significantly conserved evolutionary trajectories in cancer. MASTRO discovers all conserved trajectories in a collection of phylogenetic trees describing the evolution of a cohort of tumors, allowing the discovery of conserved complex relations between alterations. MASTRO assesses the significance of the trajectories using a conditional statistical test that captures the coherence in the order in which alterations are observed in different tumors. We apply MASTRO to data from nonsmall-cell lung cancer bulk sequencing and to acute myeloid leukemia data from single-cell panel sequencing, and find significant evolutionary trajectories recapitulating and extending the results reported in the original studies.

AVAILABILITY AND IMPLEMENTATION

MASTRO is available at https://github.com/VandinLab/MASTRO.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

SPRISS: Approximating Frequent K-mers by Sampling Reads, and Applications

Motivation

The extraction of k-mers is a fundamental component in many complex analyses of large next-generation sequencing datasets, including reads classification in genomics and the characterization of RNA-seq datasets. The extraction of all k-mers and their frequencies is extremely demanding in terms of running time and memory, owing to the size of the data and to the exponential number of k-mers to be considered. However, in several applications, only frequent k-mers, which are k-mers appearing in a relatively high proportion of the data, are required by the analysis.

Results

In this work, we present SPRISS, a new efficient algorithm to approximate frequent k-mers and their frequencies in next-generation sequencing data. SPRISS uses a simple yet powerful reads sampling scheme, which allows to extract a representative subset of the dataset that can be used, in combination with any k-mer counting algorithm, to perform downstream analyses in a fraction of the time required by the analysis of the whole data, while obtaining comparable answers. Our extensive experimental evaluation demonstrates the efficiency and accuracy of SPRISS in approximating frequent k-mers, and shows that it can be used in various scenarios, such as the comparison of metagenomic datasets, the identification of discriminative k-mers, and SNP (single nucleotide polymorphism) genotyping, to extract insights in a fraction of the time required by the analysis of the whole dataset.

Availability and implementation

SPRISS [a preliminary version (Santoro et al., 2021) of this work was presented at RECOMB 2021] is available at https://github.com/VandinLab/SPRISS.

Supplementary information

Supplementary data are available at Bioinformatics online.

Fast Approximation of Frequent k-Mers and Applications to Metagenomics

Estimating the abundances of all k-mers in a set of biological sequences is a fundamental and challenging problem with many applications in biological analysis. Although several methods have been designed for the exact or approximate solution of this problem, they all require to process the entire data set, which can be extremely expensive for high-throughput sequencing data sets. Although in some applications it is crucial to estimate all k-mers and their abundances, in other situations it may be sufficient to report only frequent k-mers, which appear with relatively high frequency in a data set. This is the case, for example, in the computation of k-mers' abundance-based distances among data sets of reads, commonly used in metagenomic analyses. In this study, we develop, analyze, and test a sampling-based approach, called Sampling Algorithm for K-mErs approxIMAtion (SAKEIMA), to approximate the frequent k-mers and their frequencies in a high-throughput sequencing data set while providing rigorous guarantees on the quality of the approximation. SAKEIMA employs an advanced sampling scheme and we show how the characterization of the Vapnik-Chervonenkis dimension, a core concept from statistical learning theory, of a properly defined set of functions leads to practical bounds on the sample size required for a rigorous approximation. Our experimental evaluation shows that SAKEIMA allows to rigorously approximate frequent k-mers by processing only a fraction of a data set and that the frequencies estimated by SAKEIMA lead to accurate estimates of k-mer-based distances between high-throughput sequencing data sets. Overall, SAKEIMA is an efficient and rigorous tool to estimate k-mers' abundances providing significant speedups in the analysis of large sequencing data sets.

Biological and genetic factors influencing plasma factor VIII levels in a healthy family population: results from the Stanislas cohort

The mechanisms underlying the variability of factor VIII (FVIII) levels are still poorly understood. The only receptor of FVIII identified so far is the lipoprotein receptor-related protein (LRP), which is thought to be involved in FVIII degradation. We aimed to characterize biological and genetic factors related to FVIII variability, focusing on coding polymorphisms of the LRP gene and polymorphisms potentially detected by molecular screening of the LRP-binding domains of the FVIII gene. Plasma FVIII coagulant activity (FVIII:C) and von Willebrand factor (VWF:Ag) antigen levels were measured in a sample of 100 healthy nuclear families (200 parents and 224 offspring). The ABO blood group and the three coding polymorphisms of the LRP gene (A217V, D2080N and C766T) were genotyped. Lipids and anthropometric factors poorly contributed to the variability of FVIII:C (<5%). A strong effect of ABO blood groups on FVIII:C levels was observed that remained significant after adjustment for VWF:Ag levels (P = 0.02). These two factors explained more than 50% of FVIII:C variability. After adjustment for VWF:Ag and ABO blood groups, a residual resemblance for FVIII:C persisted between biological relatives (rho = 0.13 +/- 0.06 between parents and offspring, rho = 0.24 +/- 0.09 between siblings) compatible with an additional genetic influence. The N allele of the LRP/D2080N polymorphism was associated with decreased levels of FVIII:C (90.4 +/- 8.7 vs. 102.2 +/- 3.5 IU/dl, P = 0.03) and VWF:Ag levels (109.1 +/- 11.2 vs. 125.4 +/- 4.4 IU/dl, P = 0.02). No polymorphism was detected in the LRP-binding domains of the FVIII gene. This study reinforces the hypothesis of a genetic influence of FVIII levels beyond the influence of VWF:Ag and ABO blood groups. The D2080N polymorphism of the LRP gene weakly contributed to the variability of FVIII:C levels in this healthy population.