ParticleCall: A particle filter for base calling in next-generation sequencing systems

Xiaohu Shen, Haris VikaloBMC Bioinformatics 2012 · DOI · OpenReview

Abstract

Base calling is a critical step in next-generation sequencing (NGS) that converts raw fluorescent intensity signals into nucleotide sequences. While Bayesian methods offer high accuracy by modeling noise like phasing and pre-phasing, their computational intensity often limits practical application. We present ParticleCall, a novel algorithm that utilizes Hidden Markov Models (HMMs) and particle filtering to achieve Bayesian-level accuracy with significantly reduced computational overhead. By introducing a fast Particle Filter Expectation-Maximization (PFEM) approach for parameter estimation, ParticleCall provides a scalable solution for high-throughput sequencing environments.

Introduction

In Illumina sequencing, fluorescent intensities are measured as nucleotides are synthesized. This process is inherently noisy due to phasing (failure to incorporate a base) and pre-phasing (incorporating multiple bases). These errors accumulate over sequencing cycles, leading to signal "blurring" and increased error rates in longer reads.

Current base-calling solutions generally fall into two categories: computationally efficient but less accurate heuristics (e.g., Illumina’s default Bustard algorithm) and highly accurate but computationally prohibitive Bayesian models (e.g., BayesCall). BayesCall relies on Markov Chain Monte Carlo (MCMC) sampling, which can take days to process a single run. ParticleCall addresses this gap by leveraging Sequential Monte Carlo methods to provide a fast, accurate alternative.

Methodology

ParticleCall reformulates the sequencing process as a Hidden Markov Model (HMM). In this framework, the "hidden" state represents the actual DNA sequence, while the "observed" state corresponds to the noisy fluorescent intensities recorded by the sequencer.

HMM representation of the sequencing process, where S represents the hidden DNA states and y represents the observed intensities.

To efficiently solve this HMM, the algorithm employs two primary techniques:

  1. Particle Filtering: Instead of the global optimization required by MCMC, particle filters track multiple hypotheses (particles) of the sequence state cycle-by-cycle. This sequential approach is naturally suited to the "one-way" nature of sequencing.
  2. Particle Filter EM (PFEM): A major bottleneck in Bayesian base calling is parameter estimation (e.g., crosstalk, decay, and phasing rates). ParticleCall utilizes a window-by-window PFEM scheme. By assuming parameters are stable within short windows (typically 5 cycles), the algorithm can estimate parameters rapidly using samples from the particle filter, replacing the heavy MCMC-based estimation.

Results and Discussion

The performance of ParticleCall was evaluated using a phiX174 bacteriophage control dataset on an Illumina Genome Analyzer II (76 cycles).

Accuracy and Computational Efficiency

ParticleCall achieved a base-calling error rate of 1.24%, matching the accuracy of BayesCall and significantly outperforming Bustard (~1.52%) and Rolexa (~1.70%). As shown in the error rate analysis across cycles, ParticleCall maintains a low error profile even as signal noise increases in later cycles.

Comparison of error rates across sequencing cycles for various base-calling algorithms. ParticleCall (via PFEM/MCEM) tracks closely with the most accurate Bayesian methods.

The computational gains are substantial. ParticleCall is approximately 3x faster than BayesCall during the base-calling phase. More importantly, the PFEM parameter estimation scheme required only 39 minutes, compared to nearly 19 hours (1139 minutes) for BayesCall’s MCMC approach—a 29x speedup.

Impact on Downstream Assembly

The utility of improved base calling was further validated through de novo assembly using the Velvet assembler. Reads processed by ParticleCall resulted in longer contigs and higher N50 scores than those from competing methods. This suggests that higher base-calling accuracy can reduce the "coverage" required for successful genomic reconstruction, potentially lowering overall sequencing costs.

Conclusion

ParticleCall demonstrates that Sequential Monte Carlo methods can bring sophisticated Bayesian modeling to high-throughput sequencing without the prohibitive time costs of MCMC. While the current model assumes parameter stability within small windows, future work may explore tile-specific or cluster-specific parameter modeling to further enhance accuracy. The efficiency of the PFEM approach makes ParticleCall a viable candidate for near real-time base calling in modern genomic laboratories.

Summary updated

Abstract

Background Next-generation sequencing systems are capable of rapid and cost-effective DNA sequencing, thus enabling routine sequencing tasks and taking us one step closer to personalized medicine. Accuracy and lengths of their reads, however, are yet to surpass those provided by the conventional Sanger sequencing method. This motivates the search for computationally efficient algorithms capable of reliable and accurate detection of the order of nucleotides in short DNA fragments from the acquired data. Results In this paper, we consider Illumina’s sequencing-by-synthesis platform which relies on reversible terminator chemistry and describe the acquired signal by reformulating its mathematical model as a Hidden Markov Model. Relying on this model and sequential Monte Carlo methods, we develop a parameter estimation and base calling scheme called ParticleCall. ParticleCall is tested on a data set obtained by sequencing phiX174 bacteriophage using Illumina’s Genome Analyzer II. The results show that the developed base calling scheme is significantly more computationally efficient than the best performing unsupervised method currently available, while achieving the same accuracy. Conclusions The proposed ParticleCall provides more accurate calls than the Illumina’s base calling algorithm, Bustard. At the same time, ParticleCall is significantly more computationally efficient than other recent schemes with similar performance, rendering it more feasible for high-throughput sequencing data analysis. Improvement of base calling accuracy will have immediate beneficial effects on the performance of downstream applications such as SNP and genotype calling. ParticleCall is freely available at https://sourceforge.net/projects/particlecall .
BibTeX
@article{shen2012particlecall,
  author = {Xiaohu Shen and Haris Vikalo},
  title = {{ParticleCall: A particle filter for base calling in next-generation sequencing systems}},
  journal = {BMC Bioinformatics},
  year = {2012},
  doi = {10.1186/1471-2105-13-160},
}
Figure