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