2026-08-17T03:50:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11048 2024-03-06T10:47:28Z ddc:004 open_access

Detecting Transcriptomic Structural Variants in Heterogeneous Contexts via the Multiple Compatible Arrangements Problem Qiu, Yutong Ma, Cong Xie, Han Kingsford, Carl transcriptomic structural variation integer linear programming heterogeneity Transcriptomic structural variants (TSVs) - large-scale transcriptome sequence change due to structural variation - 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 a 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yutong Qiu and Cong Ma and Han Xie and Carl Kingsford 2019 Is Part Of LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2019.18 urn:nbn:de:0030-drops-110483 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode