Similarity Searching in Macromolecular Electron Density Maps

Abstract

From the very beginning of biology, the interpretation of images has been a major driving force of discovery. Especially the method of comparing images and identifying similarities and differences is widely used in various fields for the study of macroscopic objects. This work applies the generic approach of similarity searching to images of sub-nanometer scale objects, namely macromolecular electron density maps. Among others, these maps can be acquired by X-ray crystallography and single particle cryo-electron microscopy, and up to now more than 67000 three-dimensional atomic structures of biomolecules have been elucidated using these methods. The comparison of atomic structures gives insight into various questions such as evolutionary relations between organisms and it can help in the process of drug development. Comparing biomolecules by registering the experimental electron density maps is a complex task since high resolution maps are exceedingly intricate. Furthermore, manual inspection of all available maps is impossible due to the sheer amount of maps. Therefore, methods for an automated, efficient, and accurate comparison of electron density maps are required. This work addresses the mentioned problem and introduces a method that is implemented in a software system coined siseek, which is geared to solving the problem of similarity searching in macromolecular electron density maps. siseek is based on the scale-invariant feature transform and locates keypoints -- image features -- in salient, spherical regions of a given map. Each keypoint is assigned discrete orientations, which are determined based on the gradient in the keypoint’s neighborhood. Orientations, in turn, are used for the computation of local neighborhood descriptors, which enable the identification of similar local neighborhoods in maps. Based on this information, map registration -- the superposition of similar parts of two maps -- is facilitated. Furthermore, an approach for molecule recognition based on feature vector similarity is described. siseek is parameterized in several large scale studies using a set of synthetically generated maps. The performance of siseek is first assessed by docking molecular subunits to distorted, synthetic maps of their corresponding assemblies. These experiments show that siseek is able to successfully locate atomic structures in intermediate and high resolution electron density maps requiring less time than other approaches. This finding is confirmed by exemplifying that siseek correctly registers atomic structures to various experimental maps acquired by single particle cryo-electron microscopy and X-ray crystallography. Additionally, pairs of X-ray crystallography maps are successfully registered by siseek. Furthermore, siseek is used in a proof of concept to identify molecules depicted in electron density maps. The experiments demonstrate that siseek facilitates similarity searching in macromolecular electron density maps and show that the method can be used to aid the process of interpreting these maps.

Seit den Anfängen der Biologie liefert die Interpretation von Bilddaten wertvolle Erkenntnisse. Insbesondere der Vergleich von Bildern wird häufig für die Analyse makroskopischer Strukturen eingesetzt und ermöglicht es Ähnlichkeiten und Gemeinsamkeiten der dargestellten Objekte festzustellen. In dieser Arbeit wird die generische Methode der Ähnlichkeitssuche auf Objekte aus dem sub-nanometer Bereich angewendet, die in makromolekularen Elektronendichtekarten abgebildet sind. Diese Karten können z. B. aus Röntgenstrukturanalyse- und Kryo-Elektronenmikroskopie-Experimenten gewonnen werden und haben bislang die Bestimmung der dreidimensionalen, atomaren Struktur von mehr als 67000 Biomolekülen ermöglicht. Aufgrund des hohen Detailgrades hochaufgelöster Elektronendichtekarten ist der Vergleich der Karten nicht trivial. Des weiteren liegt bei der großen Anzahl der Karten eine manuelle Analyse ohnehin nicht im Bereich des Praktikablen. Aus diesen Gründen sind Methoden zur automatisierten, effizienten und genauen Analyse von Elektronendichtekarten notwendig. In der vorliegenden Arbeit wird diese Fragestellung behandelt und eine Methode vorgestellt, die in einem Softwaresystem mit dem Namen siseek implementiert wurde und der automatisierten Ähnlichkeitssuche in makromolekularen Elektronendichtekarten dient. siseek basiert auf der "scale-invariant feature transform" und identifiziert Schlüsselpunkte ("keypoints") in hervorstehenden, kugelförmigen Bereichen einer Karte. Jedem Schlüsselpunkt werden Orientierungen auf Basis des umliegenden Gradientenfeldes zugewiesen, die wiederum dazu verwendet werden lokale Nachbarschaftsdeskriptoren zu berechnen. Jeder Deskriptor wird als Merkmalsvektor betrachtet und zur Berechnung der Ähnlichkeit zwischen den zugrundeliegenden Nachbarschaften genutzt. Basierend auf dieser Ähnlichkeit wird die Registrierung, also die Überlagerung ähnlicher Teile, von zwei Karten ermöglicht. Zusätzlich wird auf Basis von siseek ein Verfahren zur automatisierten Erkennung eines in einer Elektronendichtekarte dargestellten Moleküls vorgestellt. siseek wurde in mehreren groß angelegten Studien mit Hilfe von synthetischen Karten parametrisiert und in Docking-Experimenten mit synthetischen und experimentellen Karten analysiert. Diese Experimente zeigen, dass siseek zur Ähnlichkeitssuche in Karten mit mittlerer und hoher Auflösung eingesetzt werden kann und dabei weniger Zeit als andere Ansätze benötigt. Dieser Befund wird durch Registrierungsexperimente mit experimentell gewonnenen Karten aus Röntgenstrukturanalyse und Kryo-Elektronenmikroskopie untermauert. Außerdem wird eine Machbarkeitsstudie zur automatisierten Molekülerkennung in Elektronendichtekarten vorgestellt. Die Experimente zeigen, dass siseek zur Registrierung von Elektronendichtekarten eingesetzt werden und somit deren Interpretation unterstützen kann.