Detecting transcriptomic structural variants in heterogeneous contexts via the Multiple Compatible Arrangements Problem

Yutong Qiu, Cong Ma, Han Xie, Carl Kingsford

TL;DR

This paper introduces a new computational framework, the Multiple Compatible Arrangements Problem (MCAP), to accurately detect transcriptomic structural variants (TSVs) in cancer samples, which are often genetically heterogeneous. They developed both an exact integer linear programming (ILP) solution and approximation algorithms that significantly outperform existing methods by accounting for multiple genomic arrangements within a single sample.

What Problem Does This Paper Address?

Detecting transcriptomic structural variants (TSVs) is crucial for understanding cancer development, as these large-scale genomic alterations can lead to the formation of fusion genes. However, a major challenge in TSV detection from RNA-seq data is sample heterogeneity. Real-world samples, especially tumors, often contain multiple distinct genetic alleles. Existing TSV detection tools typically assume a single, homogeneous genome, leading them to misinterpret variations present on different alleles as errors and thus miss true TSVs. This paper aims to bridge this gap by developing methods that can model and account for this genetic heterogeneity.

Methods

The core of the paper is the introduction of the Multiple Compatible Arrangements Problem (MCAP). MCAP models a sample with k distinct genomic arrangements (alleles) and seeks to find k arrangements that maximize the number of RNA-seq reads that align concordantly to at least one of these arrangements.

  • MCAP Formulation: They define MCAP as finding k genome arrangements that maximize concordant reads, effectively allowing conflicting read alignments to be explained by different alleles.
  • NP-Completeness: They prove that MCAP is NP-complete, meaning finding an exact solution is computationally intractable for large instances.
  • Approximation Algorithms:
    • For k=1 (homogeneous case, termed SCAP), they provide a 1/4-approximation algorithm.
  • For k=2 (diploid case), they develop a 3/4-approximation algorithm using an oracle for k=1.
  • Combining these, they achieve a 3/16-approximation for MCAP when k=2 without an oracle.
  • Integer Linear Programming (ILP): They formulate an ILP for general k, which can find optimal solutions but is computationally expensive.
  • Conflict Structure Characterization: They analyze graph structures that inherently require multiple arrangements (k > 1) to explain observed read data, demonstrating that such structures are common.

Datasets

  • TCGA Cancer Samples: The algorithms were evaluated on 381 samples from four cancer types (BLCA, BRCA, LUAD, PRAD) from The Cancer Genome Atlas (TCGA).
  • Cancer Cell Lines: Previously studied breast cancer cell lines (HCC1395 and HCC1954) with experimentally verified SVs were used for validation.

Key Insights and Ideas

  • Heterogeneity is the Norm, Not the Exception: The study strongly suggests that most TCGA samples exhibit significant heterogeneity, with a high fraction of discordant reads falling into "conflict structures" that cannot be explained by a single genome arrangement.
  • MCAP as a Solution: The MCAP framework directly addresses this by allowing multiple genomic arrangements, effectively "resolving" discordant reads by assigning them to different alleles.
  • Conflict Structures are Prevalent: The paper provides a theoretical basis for why heterogeneity is a problem, by characterizing specific graph structures that necessitate multiple arrangements.
  • Approximation Algorithms are Practical: While MCAP is NP-complete, the developed approximation algorithms offer a good balance between accuracy and computational efficiency, performing well in practice.

Key Results

  • Improved TSV Detection: Their method, termed D-SQUID (when using the ILP formulation), identified significantly more TSVs in TCGA samples compared to the existing tool SQUID, which assumes homogeneity.
  • Higher True Positive Rate: In cancer cell lines with known TSVs, D-SQUID also detected more true positive events, including novel ones.
  • Resolution of Discordant Edges: D-SQUID was able to resolve a much higher fraction of discordant edges (over 90% in TCGA samples) compared to SQUID (less than 50%).
  • Approximation Performance: The approximation algorithms (A1 and A2) were substantially faster than the ILP approach, with A2 showing better accuracy in resolving high-weight discordant edges, albeit at a higher computational cost.
  • TCGA vs. Cell Lines: TCGA samples showed a higher fraction of discordant edges in conflict structures than cancer cell lines, aligning with the expectation that bulk tumor samples are more heterogeneous.

Limitations and Future Work

  • Determining Optimal k: MCAP relies on knowing the number of arrangements (k). Determining the optimal k for a given sample is not trivial and remains an open problem.
  • Handling Equivalent Phasings: While MCAP separates TSVs onto different alleles, there can be multiple equivalent "phasings" (orderings) of these alleles, which the current framework doesn't fully address.
  • Incorporating Distance Information: The current formulation doesn't explicitly consider the physical distance between breakpoints and read pairs. Incorporating this could help reduce false positives (due to long distances in rearranged genomes) and false negatives (due to long distances in deletion events).
  • Biological Impact of TSVs: Further research is needed to analyze the functional and disease impact of identified TSVs, especially non-fusion-gene events.

Summary updated

Abstract

Background Transcriptomic structural variants (TSVs)—large-scale transcriptome sequence change due to structural variation - are common in cancer. TSV detection from high-throughput sequencing data is a computationally challenging problem. Among all the confounding factors, sample heterogeneity, where each sample contains multiple distinct alleles, poses a critical obstacle to accurate TSV prediction. Results To improve TSV detection in heterogeneous RNA-seq samples, we introduce the Multiple Compatible Arrangements Problem (MCAP), which seeks k genome arrangements that maximize the number of reads that are concordant with at least one arrangement. This models a heterogeneous or diploid sample. We prove that MCAP is NP-complete and provide a $$\frac{1}{4}$$ 14-approximation algorithm for $$k=1$$ k=1 and a $$\frac{3}{4}$$ 34-approximation algorithm for the diploid case ($$k=2$$ k=2) assuming an oracle for $$k=1$$ k=1. Combining these, we obtain a $$\frac{3}{16}$$ 316-approximation algorithm for MCAP when $$k=2$$ k=2 (without an oracle). We also present an integer linear programming formulation for general k. We characterize the conflict structures in the graph that require $$k>1$$ k>1 alleles to satisfy read concordancy and show that such structures are prevalent. Conclusions We show that the solution to MCAP accurately addresses sample heterogeneity during TSV detection. Our algorithms have improved performance on TCGA cancer samples and cancer cell line samples compared to a TSV calling tool, SQUID. The software is available at https://github.com/Kingsford-Group/diploidsquid.
BibTeX
@inproceedings{qiu2020detecting,
  author = {Yutong Qiu and Cong Ma and Han Xie and Carl Kingsford},
  title = {{Detecting transcriptomic structural variants in heterogeneous contexts via the Multiple Compatible Arrangements Problem}},
  booktitle = {Algorithms Mol. Biol},
  year = {2020},
  url = {https://openreview.net/forum?id=vcFP8ix5vqE},
}
Figure