PuFFIN - a parameter-free method to build nucleosome maps from paired-end reads

Anton Polishko, Evelien M. Bunnik, Karine G. Le Roch, Stefano LonardiBMC Bioinformatics 2014 · DOI

TL;DR

This paper introduces PuFFIN, a novel, parameter-free method for constructing genome-wide nucleosome maps using paired-end sequencing reads. PuFFIN's multi-resolution approach allows it to accurately identify nucleosome positions, even in complex genomic regions, outperforming existing tools in accuracy and robustness.

What Problem Does This Paper Address?

Understanding how DNA is packaged into chromatin, with nucleosomes as its basic unit, is crucial for deciphering gene regulation. Accurately mapping nucleosome positions across the genome is essential for this. While various experimental techniques exist, computational methods for analyzing the resulting sequencing data often struggle with challenges like varying fragment sizes, overlapping nucleosomes, and the need for manual parameter tuning. Existing tools often rely on single-end reads, which provide less precise information, or require users to painstakingly optimize parameters like nucleosome overlap and fragment size ranges. This manual tuning can lead to suboptimal results and makes the process cumbersome. PuFFIN aims to overcome these limitations by providing an automated, parameter-free solution for nucleosome mapping using paired-end reads.

Methods

PuFFIN employs a novel multi-resolution approach that avoids the need for user-defined parameters. The core of the method involves three steps:

  1. Building Nucleosome Profiles and Landscapes: Instead of directly analyzing read counts, PuFFIN represents each mapped paired-end read as a Gaussian distribution. This probabilistic representation accounts for uncertainty in read mapping. These individual Gaussian functions are then summed to create a nucleosome profile. Crucially, PuFFIN generates a family of these profiles by varying a smoothing parameter ($\alpha$) across a range of resolutions. This multi-resolution strategy allows the algorithm to adapt to local data properties. These profiles are then normalized to create "nucleosome landscapes," which highlight candidate nucleosome locations at different scales.
  2. Detecting Candidate Nucleosomes: Peaks in these nucleosome landscapes are identified as candidate nucleosome locations. The algorithm defines a peak by its center and width, and further refines candidate locations by calculating the centroid of the corresponding read midpoints to ensure they accurately represent the input reads.
  3. Building the Final Solution: The method then constructs a final set of non-overlapping nucleosomes by processing the candidate peaks from the different resolution levels. It starts with the lowest resolution (largest $\alpha$) and iteratively adds peaks that do not overlap with previously identified nucleosomes. This ensures that well-positioned nucleosomes are identified early, while "fuzzy" or less defined nucleosomes are captured at higher resolutions.

Datasets

The paper evaluates PuFFIN using:

  • Synthetic Datasets: Generated using the syntheticNucMap tool from the nucleR package. These datasets were designed to simulate various scenarios, including low coverage, fuzzy nucleosomes, and varying degrees of overlap, allowing for controlled benchmarking.
  • Real Datasets:
    • S. cerevisiae (yeast) dataset (NCBI SRA SRR094649).
  • P. falciparum (malaria parasite) dataset (NCBI SRA SRS453761).

The authors note that a lack of "ground-truth" for real data makes benchmarking challenging, hence the extensive use of synthetic data.

Key Insights and Ideas

  • Parameter-Free Approach: The most significant innovation is the elimination of user-defined parameters. This drastically simplifies the process and prevents users from making suboptimal choices that could lead to inaccurate nucleosome maps.
  • Multi-Resolution Analysis: By examining nucleosome landscapes at various resolutions, PuFFIN can effectively identify both sharply defined and "fuzzy" nucleosomes, which are common in biological systems but difficult for single-resolution methods to capture.
  • Probabilistic Read Representation: Modeling each read as a Gaussian distribution elegantly handles the inherent uncertainty in paired-end read mapping.
  • Iterative Consensus Building: The strategy of building a consensus set by processing resolutions from coarse to fine ensures that robust nucleosome calls are prioritized, while still capturing less defined ones.

Key Results

  • Accuracy: PuFFIN consistently produced more accurate nucleosome maps compared to existing tools (NucPosSimulator, TEMPLATE FILTERING, and NORMAL) on both synthetic and real datasets. This accuracy was particularly evident in scenarios with fuzzy or overlapping nucleosomes.
  • Robustness: The parameter-free nature of PuFFIN makes it more robust to variations in data quality and complexity.
  • Over-reporting Mitigation: PuFFIN demonstrated a reduced tendency to over-report nucleosomes compared to NucPosSimulator, especially in datasets with a high proportion of fuzzy nucleosomes.
  • Execution Time: While PuFFIN's execution time was higher than some tools (NORMAL, TEMPLATE FILTERING) on yeast data, it was competitive or faster on P. falciparum data. The authors note that implementation in C/C++ could further improve speed.

Limitations and Future Work

  • Execution Time: The current Python implementation of PuFFIN is slower than tools written in Java or C/C++. The authors are actively working on improving this by re-implementing the tool in C/C++.
  • Data Quantity Sensitivity: The paper suggests that PuFFIN's performance degrades monotonically with decreasing input data quantity (coverage). A minimum of 30-fold coverage is recommended for analysis using PuFFIN.
  • Future Work: The authors suggest that the multi-resolution strategy employed by PuFFIN could be applicable to other genome analysis domains. Further optimization of the computational efficiency is also a clear future direction.

Summary updated

BibTeX
@article{polishko2014puffin,
  author = {Anton Polishko and Evelien M. Bunnik and Karine G. Le Roch and Stefano Lonardi},
  title = {{PuFFIN - a parameter-free method to build nucleosome maps from paired-end reads}},
  journal = {BMC Bioinformatics},
  year = {2014},
  doi = {10.1186/1471-2105-15-s9-s11},
}
Figure