Segmentor3IsBack: an R package for the fast and exact segmentation of Seq-data

Alice Cleynen, Pierre Neuvial, Émilie Lebarbier, Mark Hoebeke, Stéphane RobinarXiv 2012 · DOI · arXiv

Abstract

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.

Introduction

In genomics, segmentation is the process of partitioning a sequence of data into regions with similar statistical properties, such as identifying gene boundaries from RNA-Seq "reads." Historically, methods designed for microarrays assumed continuous Gaussian distributions. However, Next-Generation Sequencing (NGS) produces discrete count data characterized by "overdispersion," where variance exceeds the mean. As sequencing resolution increases, datasets now reach millions of points, rendering traditional $O(n^2)$ dynamic programming algorithms computationally infeasible.

Methods

The Segmentor3IsBack R package implements a C++ backend utilizing three core components to address these challenges:

  1. Pruned Dynamic Programming Algorithm (PDPA): PDPA reduces computational complexity from quadratic to nearly linear ($O(n \log n)$) by "pruning" the search space—discarding candidate change-points that cannot be part of an optimal solution.
  2. Negative Binomial (NB) Modeling: The authors demonstrate that the negative binomial loss function satisfies the convexity and point-additivity requirements for exact PDPA pruning, allowing the model to handle biological overdispersion.
  3. Oracle Penalty for Model Selection: To determine the optimal number of segments ($K$), the package uses a non-asymptotic "oracle penalty." This approach avoids the overfitting or underfitting common with standard criteria like AIC or BIC.
Cost of optimal segmentation for 4 and 3 segments.

The algorithm requires an overdispersion parameter ($\phi$), which can be estimated using a sliding-window median of moment estimators. The pruning mechanism remains valid as long as the loss function is convex, making the approach robust across different data types.

Key Results

The empirical performance of Segmentor3IsBack confirms its suitability for large-scale genomic analysis.

  • Efficiency and Scalability: The algorithm's complexity is $O(K_{max} n \log n)$, enabling it to process millions of data points in minutes. For instance, a yeast dataset with over 230,000 points was segmented in approximately 25 minutes.
  • Accuracy: On simulated negative binomial data, the method achieved a Rand Index between 0.94 and 1.0, indicating near-perfect recovery of ground-truth change-points.
  • Biological Validity: In S. Cerevisiae (yeast) chromosome 1, the identified segments closely matched known gene boundaries, with high correspondence to the Saccharomyces Genome Database (SGD).
Computational time as a function of signal size.

The algorithm remains robust even under high overdispersion, a condition where many alternative methods become unstable or computationally prohibitive.

Conclusion and Future Work

Segmentor3IsBack provides a fast, exact solution for segmenting high-throughput sequencing data. While highly effective, current limitations include the assumption of a constant overdispersion parameter across the sequence and the need for semi-automated tuning of the oracle penalty constant. Future developments may focus on multi-track sequencing data for joint segmentation of multiple samples and accommodating varying dispersion levels across genomic regions.

Summary updated

Abstract

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.
BibTeX
@misc{cleynen2012segmentor,
  author = {Alice Cleynen and Pierre Neuvial and Émilie Lebarbier and Mark Hoebeke and Stéphane Robin},
  title = {{Segmentor3IsBack: an R package for the fast and exact segmentation of Seq-data}},
  year = {2012},
  eprint = {1204.5564},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.5564},
}
Figure