  Genome annotation is an important issue in biology which has long been
addressed with gene prediction methods and manual experiments requiring
biological expertise. The expanding Next Generation Sequencing technologies and
their enhanced precision allow a new approach to the domain: the segmentation
of RNA-Seq data to determine gene boundaries. Because of its almost linear
complexity, we propose to use the Pruned Dynamic Programming Algorithm, which
performances had been acknowledged for CGH arrays, for Seq-experiment outputs.
This requires the adaptation of the algorithm to the negative binomial
distribution with which we model the data. We show that if the dispersion in
the signal is known, the PDP algorithm can be used and we provide an estimator
for this dispersion. We then propose to estimate the number of segments, which
can be associated to coding or non-coding regions of the genome, using an
oracle penalty. We illustrate the results of our approach on a real data-set
and show its good performance. Our algorithm is available as an R package on
the CRAN repository.
