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.
Traph is a novel radically different tool based on minimum-cost network flows. Our method 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. (version 0.5)
NEW: We have a new exact engine for finding a limited number of transcripts based on dynamic programming (included version 0.6), see README.
Download the latest version at: https://sourceforge.net/projects/traph/files/.
The scripts used for validating the predictions are available here.
The simulated data used in our experiments is available here.
If you use the min-cost flow engine of Traph, please cite:
A. I. Tomescu, A. Kuosmanen, R. Rizzi, and V. Mäkinen. A Novel Min-Cost Flow Method for Estimating Transcript Expression with RNA-Seq. BMC Bioinformatics, 14(Suppl 5):S15 (10 April 2013). Presented at RECOMB-Seq 2013, April 11-12, 2013, Beijing, China.
[Slides]
If you use the dynamic prorgamming engine of Traph, please cite:
A. I. Tomescu, A. Kuosmanen, R. Rizzi, and V. Mäkinen. A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths. WABI - Workshop of Algorithms for Bioinformatics, Lecture Notes in Computer Science 8126, 85-98, 2013.
[Slides]
For any questions, please contact us: alexandru.tomescu[at]helsinki.fi, anna.kuosmanen[at]cs.helsinki.fi