High Performance Algorithms for Molecular Shape Recognition

Algorithmes Haute-Performance pour la Reconnaissance de Formes Moléculaires

David Ritchie (1)

1 ORPAILLEUR - Knowledge representation, reasonning

This memoir summarises my contribution to the problems of representing and comparing the shapes and chemical properties of molecules using novel fast Fourier transform (FFT) techniques. The three main application areas considered are clustering and classifying the shapes of large protein molecules, calculating how pairs of protein molecules fit together, or "dock", to form a macromolecular complex, and comparing rapidly the shapes of many small molecules in so-called virtual drug screening. From a computational point of view, the main theme of my work is that comparing the complex three-dimensional (3D) shapes of molecules is largely a rotational problem, and therefore that molecules should be represented using polar coordinate systems in order to be able to compare them efficiently using rotational FFT correlations. Although FFT-based techniques are widely used in many areas of science, conventional Cartesian grid-based FFT approaches can accelerate shape-matching calculations in only three of the six rigid body degrees of freedom. Here, I show that by representing molecules using orthogonal expansions of spherical harmonic and Gauss-Laguerre polynomials, and by using only standard techniques of calculus, their shapes may be both rotated and translated analytically, and pairs of shapes may be compared or docked very efficiently using a series of 1D, 3D, or even 5D rotational FFTs. Although much of the underlying mathemetical theory is "well known" in the domains of theoretical chemistry and nuclear physics, the overall approach is novel in the context of molecular shape matching and protein docking, and in 3D object recognition in general. The final part of the memoir considers some future perspectives for extending the approaches developed and using them to tackle current challenges in structural systems biology such as high-throughput virtual drug screening, modelling protein flexibility during docking, and assembling very large macromolecular structures.

Ce mémoire résume ma contribution aux problèmes de la représentation et de la comparaison des formes et propriétés chimiques de molécules au moyen de nouvelles techniques de transformées de Fourier rapides (FFT). Les trois principaux domaines abordés ici sont le clustering et la classification des formes de macromolécules protéiques, le docking ou amarrage protéine-protéine visant à modéliser la conformation structurale de deux partenaires susceptible d'exister in vivo, et enfin la comparaison rapide de nombreuses petites molécules pour le criblage virtuel de potentiels inhibiteurs thérapeutiques. Les techniques basées sur la FFT sont largement utilisées dans de nombreux domaines de la science. Par ailleurs, les approches conventionnelles basées sur les grilles cartésiennes de FFT peuvent accélérer les calculs d'appariement moléculaire dans seulement trois des six degrés de liberté (ceux de translation) du corps rigide. Le thème principal de mon travail repose sur l'idée que la comparaison des formes complexes en trois dimensions (3D) de molécules est en grande partie un problème de rotation, dès lors les molécules peuvent efficacement être représentées par des systèmes de coordonnées polaires afin de pouvoir les comparer à l'aide de FFT rotationelles. Dans ce mémoire, je montre qu'en représentant les molécules par des développements orthogonaux en harmoniques sphériques et des polynômes de Gauss-Laguerre et en n'utilisant que des techniques classiques de calcul, leurs formes peuvent être mises en rotation et translatées analytiquement. Les paires de formes peuvent alors être comparées ou amarrées de façon très efficace en utilisant une série de 1D, 3D, ou même 5D FFT de rotation. Même si une grande partie des fondamentaux théoriques sont bien connue dans les domaines de la chimie ou de la physique, l'approche globale est originale dans le contexte de l'appariement de formes moléculaires, du docking de protéines et plus généralement de la reconnaissance d'objets 3D. La dernière partie de ce mémoire ouvre sur les perspectives futures visant à étendre ces différentes approches aux défis actuels posés par la biologie systémique et structurale tels que le criblage virtuel à haut-débit, l'intégration de la flexibilité des protéines lors de leur complexation mais aussi l'assemblage de structures macromoléculaires multi-composants.

Mots clés: bioinformatics; chemoinformatics

Mots clés: bioinformatique; infochimie

Domaines: Informatique [cs]

David Ritchie. Algorithmes Haute-Performance pour la Reconnaissance de Formes Moléculaires. Informatique [cs]. Université Henri Poincaré - Nancy I, 2011. ⟨tel-00587962⟩