The indexing ambiguity in serial femtosecond crystallography (SFX) resolved using an expectation maximization algorithm

Haiguang Liu, John C. H. SpenceIUCrJ 2014 · DOI

TL;DR

This paper introduces a novel expectation maximization (EM) algorithm to solve the "indexing ambiguity" problem in serial femtosecond crystallography (SFX). By iteratively building a model of full diffraction intensities from partial data, the algorithm can reliably distinguish between correct and incorrect crystal indexing, a crucial step for merging data and determining protein structures.

What Problem Does This Paper Address?

Serial femtosecond crystallography (SFX) uses X-ray free-electron lasers (XFELs) to determine the structures of proteins by analyzing diffraction patterns from thousands of tiny crystals. A major challenge in SFX is "indexing ambiguity." This occurs when a crystal's symmetry (Bravais symmetry) is higher than its space group symmetry, leading to multiple geometrically equivalent ways to assign Miller indices (which describe the orientation of diffraction spots) to the observed Bragg peaks. This ambiguity makes it difficult to merge diffraction data from different crystals accurately, as incorrect indexing can lead to merging data from "twinned" orientations, effectively creating a false twin. To resolve this, one needs full diffraction intensities, but SFX only captures partial reflections from each shot. This creates a "chicken-and-egg" problem: you need correct indexing to get full intensities, but you need full intensities to resolve the indexing ambiguity.

Methods

The authors propose an Expectation Maximization (EM) algorithm to tackle this indexing ambiguity. The core idea is to iteratively build a 3D model of the full diffraction intensities. In each iteration:

  1. Expectation Step: Each experimental diffraction pattern (containing partial reflections) is compared against the current 3D model of full reflection intensities. The algorithm calculates a Pearson correlation coefficient to quantify how well each pattern's indexing matches the model.
  2. Maximization Step: Based on these correlations, the algorithm assigns the most likely indexing mode to each pattern. The patterns are then merged according to their assigned indexing modes to create a new, improved 3D model for the next iteration.

This iterative process refines the model, gradually resolving the indexing ambiguity. The algorithm uses Pearson's correlation coefficient to measure the similarity between partial reflections in a pattern and the full reflection model.

Datasets

The authors evaluated their EM algorithm using two types of data:

  • Simulated Data: Theoretical intensities were computed for Photosystem I (PSI) in space group P6₃, using its known atomic structure (PDB code 1jb0). Simulated diffraction patterns were generated based on this model, with indexing assigned randomly to mimic the ambiguity.
  • Experimental Data: Actual SFX data from Photosystem I (PSI) crystals collected at the Linac Coherent Light Source (LCLS) was used. The PDB model of PSI was again used as a reference for evaluating the detwinning accuracy.

Key Insights and Ideas

  • Iterative Refinement is Key: The EM algorithm's power lies in its iterative nature. By using the partially resolved model from one iteration to guide the next, it progressively refines the indexing and builds a more accurate representation of the full diffraction volume.
  • Pearson Correlation as a Discriminator: The Pearson correlation coefficient proves effective in distinguishing between correct and incorrect indexing modes, even when dealing with severely partial reflections.
  • Bridging the Gap: The algorithm effectively bridges the "chicken-and-egg" problem by using partial data to build a model that, in turn, helps resolve the ambiguity in indexing.
  • Robustness to Partiality: The method demonstrates resilience to the inherent partiality of SFX data, where only a fraction of a reflection is captured.

Key Results

  • High Accuracy: For experimental PSI data, the EM algorithm successfully recovered the correct indexing for 94.6% of the diffraction patterns.
  • Effective Detwinning: Visualizations of the diffraction data before and after detwinning clearly show the removal of artificial symmetry caused by incorrect indexing.
  • Fast Convergence: The algorithm converges to a stable solution within a few iterations (around 6-10 for experimental data, and as few as 2 for simulated data with specific partiality modeling).
  • Linear Scaling: The computation time for each iteration scales linearly with the number of patterns, making it efficient for large datasets.
  • Robustness: Running the algorithm multiple times with different starting models yielded consistent results, indicating its robustness.
  • Minimum Data Requirement: For reliable convergence, a minimum of 5000 diffraction patterns was found to be necessary for the PSI experimental data.

Limitations and Future Work

  • Minimum Data Size: The algorithm's success is dependent on having a sufficient number of diffraction patterns. With fewer than 5000 patterns, the success rate can be significantly reduced, and more runs might be needed.
  • Future Work: The authors mention that the effect of sub-micrometer crystal sizes and their shape transform on diffraction patterns will be investigated in a subsequent paper. They also note that the current implementation uses a single computing core, and parallelization could further speed up processing for very large datasets. The method is implemented within the CrystFEL framework, and the source code is available.

Summary updated

Abstract

Crystallographic auto-indexing algorithms provide crystal orientations and unit-cell parameters and assign Miller indices based on the geometric relations between the Bragg peaks observed in diffraction patterns. However, if the Bravais symmetry is higher than the space-group symmetry, there will be multiple indexing options that are geometrically equivalent, and hence many ways to merge diffraction intensities from protein nanocrystals. Structure factor magnitudes from full reflections are required to resolve this ambiguity but only partial reflections are available from each XFEL shot, which must be merged to obtain full reflections from these 'stills'. To resolve this chicken-and-egg problem, an expectation maximization algorithm is described that iteratively constructs a model from the intensities recorded in the diffraction patterns as the indexing ambiguity is being resolved. The reconstructed model is then used to guide the resolution of the indexing ambiguity as feedback for the next iteration. Using both simulated and experimental data collected at an X-ray laser for photosystem I in the P63 space group (which supports a merohedral twinning indexing ambiguity), the method is validated.
BibTeX
@inproceedings{liu2014indexing,
  author = {Haiguang Liu and John C. H. Spence},
  title = {{The indexing ambiguity in serial femtosecond crystallography (SFX) resolved using an expectation maximization algorithm}},
  booktitle = {IUCrJ},
  year = {2014},
  doi = {10.1107/s2052252514020314},
}
Figure