  RNA-Seq technology offers new high-throughput ways for transcript
identification and quantification based on short reads, and has recently
attracted great interest. The problem is usually modeled by a weighted splicing
graph whose nodes stand for exons and whose edges stand for split alignments to
the exons. The task consists of finding a number of paths, together with their
expression levels, which optimally explain the coverages of the graph under
various fitness functions, such least sum of squares. In (Tomescu et al.
RECOMB-seq 2013) we showed that under general fitness functions, if we allow a
polynomially bounded number of paths in an optimal solution, this problem can
be solved in polynomial time by a reduction to a min-cost flow program. In this
paper we further refine this problem by asking for a bounded number k of paths
that optimally explain the splicing graph. This problem becomes NP-hard in the
strong sense, but we give a fast combinatorial algorithm based on dynamic
programming for it. In order to obtain a practical tool, we implement three
optimizations and heuristics, which achieve better performance on real data,
and similar or better performance on simulated data, than state-of-the-art
tools Cufflinks, IsoLasso and SLIDE. Our tool, called Traph, is available at
http://www.cs.helsinki.fi/gsa/traph/
