A novel min-cost flow method for estimating transcript expression with RNA-Seq
Open Access
- 10 April 2013
- journal article
- Published by Springer Nature in BMC Bioinformatics
- Vol. 14 (S5) , S15
Abstract
Through transcription and alternative splicing, a gene can be transcribed into different RNA sequences (isoforms), depending on the individual, on the tissue the cell is in, or in response to some stimuli. Recent RNA-Seq technology allows for new high-throughput ways for isoform identification and quantification based on short reads, and various methods have been put forward for this non-trivial problem. In this paper we propose a novel radically different method based on minimum-cost network flows. This has a two-fold advantage: on the one hand, it translates the problem as an established one in the field of network flows, which can be solved in polynomial time, with different existing solvers; on the other hand, it is general enough to encompass many of the previous proposals under the least sum of squares model. Our method works as follows: in order to find the transcripts which best explain, under a given fitness model, a splicing graph resulting from an RNA-Seq experiment, we find a min-cost flow in an offset flow network, under an equivalent cost model. Under very weak assumptions on the fitness model, the optimal flow can be computed in polynomial time. Parsimoniously splitting the flow back into few path transcripts can be done with any of the heuristics and approximations available from the theory of network flows. In the present implementation, we choose the simple strategy of repeatedly removing the heaviest path. We proposed a new very general method based on network flows for a multiassembly problem arising from isoform identification and quantification with RNA-Seq. Experimental results on prediction accuracy show that our method is very competitive with popular tools such as Cufflinks and IsoLasso. Our tool, called Traph (Transcrips in gRAPHs), is available at: http://www.cs.helsinki.fi/gsa/traph/.Keywords
This publication has 18 references indexed in Scilit:
- MetaVelvet: an extension of Velvet assembler to de novo metagenome assembly from short sequence readsNucleic Acids Research, 2012
- The clonal and mutational evolution spectrum of primary triple-negative breast cancersNature, 2012
- Sparse linear modeling of next-generation mRNA sequencing (RNA-Seq) data for isoform discovery and abundance estimationProceedings of the National Academy of Sciences, 2011
- IsoLasso: A LASSO Regression Approach to RNA-Seq Based Transcriptome AssemblyJournal of Computational Biology, 2011
- Ab initio reconstruction of cell type–specific transcriptomes in mouse reveals the conserved multi-exonic structure of lincRNAsNature Biotechnology, 2010
- Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiationNature Biotechnology, 2010
- Computation for ChIP-seq and RNA-seq studiesNature Methods, 2009
- Mapping and quantifying mammalian transcriptomes by RNA-SeqNature Methods, 2008
- The Multiassembly Problem: Reconstructing Multiple Transcript Isoforms From EST Fragment MixturesGenome Research, 2004
- Splicing graphs and EST assembly problemBioinformatics, 2002