Accurate inference of isoforms from multiple sample RNA-Seq data

BMC Genomics

Proceedings

Wei Li¹  Masruba Tasnim²  Ei-Wen Yang²  Tao Jiang³  Shining Ma⁴ 

[1] Department of Biostatistics and Computational Biology, Dana-Farber Cancer Institute and Harvard School of Public Health, 02215, Boston, MA, USA;Department of Computer Science and Engineering, University of California, Riverside, 92507, Riverside, CA, USA;Department of Computer Science and Engineering, University of California, Riverside, 92507, Riverside, CA, USA;Department of Computer Science and Engineering, University of California, Riverside, 92507, Riverside, CA, USA;MOE Key Lab of Bioinformatics and Bioinformatics Division, TNLIST / Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China;MOE Key Lab of Bioinformatics and Bioinformatics Division, TNLIST / Department of Automation, Tsinghua University, 100084, Beijing, China;Department of Computer Science and Engineering, University of California, Riverside, 92507, Riverside, CA, USA;

关键词: Integer Linear Programming;    Transcriptome Assembly;    Differential Analysis;    Assembly Result;    Integer Linear Programming Problem;   

DOI  :  10.1186/1471-2164-16-S2-S15

来源: Springer

【 摘 要 】

BackgroundRNA-Seq based transcriptome assembly has become a fundamental technique for studying expressed mRNAs (i.e., transcripts or isoforms) in a cell using high-throughput sequencing technologies, and is serving as a basis to analyze the structural and quantitative differences of expressed isoforms between samples. However, the current transcriptome assembly algorithms are not specifically designed to handle large amounts of errors that are inherent in real RNA-Seq datasets, especially those involving multiple samples, making downstream differential analysis applications difficult. On the other hand, multiple sample RNA-Seq datasets may provide more information than single sample datasets that can be utilized to improve the performance of transcriptome assembly and abundance estimation, but such information remains overlooked by the existing assembly tools.ResultsWe formulate a computational framework of transcriptome assembly that is capable of handling noisy RNA-Seq reads and multiple sample RNA-Seq datasets efficiently. We show that finding an optimal solution under this framework is an NP-hard problem. Instead, we develop an efficient heuristic algorithm, called Iterative Shortest Path (ISP), based on linear programming (LP) and integer linear programming (ILP). Our preliminary experimental results on both simulated and real datasets and comparison with the existing assembly tools demonstrate that (i) the ISP algorithm is able to assemble transcriptomes with a greatly increased precision while keeping the same level of sensitivity, especially when many samples are involved, and (ii) its assembly results help improve downstream differential analysis. The source code of ISP is freely available at http://alumni.cs.ucr.edu/~liw/isp.html.

【 授权许可】

Unknown   
© Tasnim et al.; licensee BioMed Central Ltd. 2015. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.