Rxivist logo

Rxivist combines preprints from bioRxiv with data from Twitter to help you find the papers being discussed in your field. Currently indexing 64,772 bioRxiv papers from 287,133 authors.

Detecting Transcriptomic Structural Variants in Heterogeneous Contexts via the Multiple Compatible Arrangements Problem

By Yutong Qiu, Cong Ma, Han Xie, Carl Kingsford

Posted 09 Jul 2019
bioRxiv DOI: 10.1101/697367

Transcriptomic structural variants (TSVs) -- structural variants that affect expressed regions -- are common, especially in cancer. Detecting TSVs is a challenging computational problem. Sample heterogeneity (including differences between alleles in diploid organisms) is a critical confounding factor when identifying TSVs. To improve TSV detection in heterogeneous RNA-seq samples, we introduce the Multiple Compatible Arrangement Problem (MCAP), which seeks k genome rearrangements to maximize the number of reads that are concordant with at least one rearrangement.This directly models the situation of a heterogeneous or diploid sample. We prove that MCAP is NP-hard and provide an 1/4-approximation algorithm for k=1 and a 3/4-approximation algorithm for the diploid case (k=2) assuming an oracle for k=1. Combining these, we obtain a 3/16-approximation algorithm for MCAP when k=2 (without an oracle). We also present an integer linear programming formulation for general k. We completely characterize the graph structures that require k>1 to satisfy all edges and show such structures are prevalent in cancer samples. We evaluate our algorithms on 381 TCGA samples and 2 cancer cell lines and show improved performance compared to the state-of-the-art TSV-calling tool, SQUID.

Download data

  • Downloaded 161 times
  • Download rankings, all-time:
    • Site-wide: 51,359 out of 64,772
    • In bioinformatics: 5,575 out of 6,408
  • Year to date:
    • Site-wide: 28,828 out of 64,772
  • Since beginning of last month:
    • Site-wide: 31,172 out of 64,772

Altmetric data


Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)


News