No description available.

Un médicament, ou tout autre petite molécule biologique, agit sur l’organisme via des interactions chimiques qui se produisent avec d’autres macromolécules telles que les protéines qui régissent le fonctionnement des cellules. La détermination de l’ensemble des cibles, c’est à dire de l’ensemble des macromolécules susceptibles de lier une même molécule, est essentielle pour mieux comprendre les mécanismes moléculaires à l’origine des effets d’un médicament. Cette connaissance permettrait en effet de guider la conception d’un composé pour éviter au mieux les effets secondaires indésirables, ou au contraire découvrir de nouvelles applications à des molécules connues. Les avancées de la biologie structurale nous permettent maintenant d’avoir accès à un très grand nombre de structures tridimensionnelles de protéines impliquées dans ces interactions, ce qui motive l’utilisation d’outils in silico (informatique) pour complémenter ou guider les expériences in vitro ou in vivo plus longues et plus chères.La thèse s’inscrit dans le cadre d’une collaboration entre le laboratoire DAVID de l’Université de Versailles-Saint-Quentin, et l’entreprise Bionext SA qui propose une suite logicielle permettant de visualiser et d’étudier les interactions chimiques. Les travaux de recherches ont pour objectif de développer un algorithme permettant, à partir des données structurales des protéines, de déterminer des cibles potentielles pour un composé donné. L’approche choisie consiste à utiliser la connaissance d’une première interaction entre un composé et une protéine afin de rechercher par similarité d’autres protéines pour lesquelles on peut inférer la capacité à se lier avec le même composé. Il s’agit plus précisément de rechercher une similarité locale entre un motif donné, qui est la région permettant à la cible connue de lier le composé, et un ensemble de protéines candidates.Un algorithme a été développé, BioBind, qui utilise un modèle des surfaces des macromolécules issu de la théorie des formes alpha afin de modéliser la surface accessible ainsi qu’une topologie sur cette surface permettant la définition de régions en surface. Afin de traiter le problème de la recherche d’un motif en surface, une heuristique est utilisée consistant à définir des motifs réguliers qui sont une approximation de disques géodésiques et permettant un échantillonnage exhaustif à la surface des macromolécules. Ces régions circulaires sont alors étendues à l’ensemble du motif recherché afin de déterminer une mesure de similarité.Le problème de la prédiction de cibles est ramené à un problème de classification binaire, où il s’agit pour un ensemble de protéines données de déterminer lesquelles sont susceptibles d’interagir avec le composé considéré, par similarité avec la première cible connue. Cette formalisation permet d’étudier les performances de notre approche, ainsi que de la comparer avec d’autres approches sur différents jeux de données. Nous utilisons pour cela deux jeux de données issus de la littérature ainsi qu’un troisième développé spécifiquement pour cette problématique afin d’être plus représentatif des molécules pertinentes du point de vue pharmacologique, c’est-à-dire ayant des propriétés proches des médicaments. Notre approche se compare favorablement sur ces trois jeux de données par rapport à une autre approche de prédiction par similarité, et plus généralement notre analyse confirme que les approches par docking (amarrage) sont moins performantes que les approches par similarité pour le problème de la prédiction de cibles. / The action of a drug, or another small biomolecule, is induced by chemical interactions with other macromolecules such as proteins regulating the cell functions. The determination of the set of targets, the macromolecules that could bind the same small molecule, is essential in order to understand molecular mechanisms responsible for the effects of a drug. Indeed, this knowledge could help the drug design process so as to avoid side effects or to find new applications for known drugs. The advances of structural biology provides us with three-dimensional representations of many proteins involved in these interactions, motivating the use of in silico tools to complement or guide further in vitro or in vivo experiments which are both more expansive and time consuming.This research is conducted as part of a collaboration between the DAVID laboratory of the Versailles-Saint-Quentin University, and Bionext SA which offers a software suite to visualize and analyze chemical interactions between biological molecules. The objective is to design an algorithm to predict these interactions for a given compound, using the structures of potential targets. More precisely, starting from a known interaction between a drug and a protein, a new interaction can be inferred with another sufficiently similar protein. This approach consists in the search of a given pattern, the known binding site, across a collection of macromolecules.An algorithm was implemented, BioBind, which rely on a topological representation of the surface of the macromolecules based on the alpha shapes theory. Our surface representation allows to define a concept of region of any shape on the surface. In order to tackle the search of a given pattern region, a heuristic has been developed, consisting in the definition of regular region which is an approximation of a geodesic disk. This circular shape allows for an exhaustive sampling and fast comparison, and any circular region can then be extended to the actual pattern to provide a similarity evaluation with the query binding site.The target prediction problem is formalized as a binary classification problem, where a set of macromolecules is being separated between those predicted to interact and the others, based on their local similarity with the known target. With this point of view, classic metrics can be used to assess performance, and compare our approach with others. Three datasets were used, two of which were extracted from the literature and the other one was designed specifically for our problem emphasizing the pharmacological relevance of the chosen molecules. Our algorithm proves to be more efficient than another state-of-the-art similarity based approach, and our analysis confirms that docking software are not relevant for our target prediction problem when a first target is known, according to our metric.

[pt] O objetivo deste trabalho é apresentar uma nova estratégia para o problema de empacotamento de discos sem sobreposição para gerar arranjos aleatórios densos. O algoritmo geométrico adota uma abordagem frente de avanço que, com o apoio de uma malha poligonal, utiliza novas heurísticas para determinar as próximas posições para as próximas partículas. Além disso, propomos esquemas de realocação para melhorar o empacotamento no interior do arranjo e perto das bordas dos objetos arbitrários que contêm as partículas. Os resultados provam que nosso algoritmo pode superar trabalhos anteriores, não apenas com a função de distribuição de raios de partículas desejada, mas também aumentando a densidade de empacotamento e o número médio de contatos. / [en] This work aims to present a new strategy for the non-overlapping disk packing problem to generate dense random assemblies. The geometric algorithm adopts an advancing front approach that uses new heuristics to determine the next positions for the incoming particles with the support of a polygonal mesh. Furthermore, we propose relocation schemes to improve the packing at the pack s interior and near the container borders. Experiments prove that our algorithm outperforms previous results, w.r.t the desired particle radii distribution function and increases the packing density and mean number of particle contacts.

Diese Arbeit beinhaltet {\it geometrische Algorithmen} zur L\"osung reeller polynomialer Gleichungssysteme mit rationalen Koeffizienten, wobei die Polynome eine reduzierte regul\"are Folge bilden (vgl. Abschnitt \ref{abschgeo}). Unter reellem L\"osen verstehen wir hier die Bestimmung eines Punktes in jeder Zusammenhangskomponente einer kompakten glatten reellen Variet\"at $V:=W \cap \R^n$.\\ Im Mittelpunkt steht die Anwendung des f\"ur den algebraisch abgeschlossenen Fall ver\"offentlichten symbolischen geometrischen Algorithmus nach \cite{gh2} und \cite{gh3}. Die Berechenungsmodelle sind {\em Straight--Line Programme} und {arithmetische Netzwerke} mit Parametern in $\; \Q$. Die Input--Polynome sind durch ein Straight--Line Programm der Gr\"o{\ss}e $L$ gegeben. Eine geometrische L\"osung des Input--Glei\-chungs\-sys\-tems besteht aus einem primitiven Element der Ringerweiterung, welche durch die Nullstellen des Systems beschrieben ist, aus einem mininalen Polynom dieses primitiven Elements, und aus den Parametrisierungen der Koordinaten. Diese Darstellung der L\"osung hat eine lange Geschichte und geht mindestens auf Leopold Kronecker \cite{kron} zur\"uck. Die Komplexit\"at des in dieser Arbeit begr\"undeten Algorithmus erweist sich als linear in $L$ und polynomial bez\"uglich $n, d, \delta$ bzw. $\delta \;'$, wobei $n$ die Anzahl der Variablen und $d$ eine Gradschranke der Polynome im System ist. Die Gr\"o{\ss}en $\delta$ und $\delta \; '$ sind geometrische Invarianten, die das Maximum der {\em Grade des Inputsystems} und geeigneter {\em polarer Variet\"aten} repr\"asentieren (bzgl. des ({\em geometrischen}) Grades vgl. \cite{he}). Die Anwendung eines Algorithmus \"uber den komplexen Zahlen auf das L\"osen von polynomialen Gleichungen im Reellen wird durch die Einf\"urung polarer Variet\"aten m\"oglich (vgl. \cite{bank}). Die polaren Variet\"aten sind das Kernst\"uck und das vorbereitende Werzeug zur effizienten Nutzung des oben erw\"ahnten geometrischen Algorithmus. Es wird ein inkrementelles Verfahren zur Auffindung reeller Punkte in jeder Zusammenhangskomponente der Nullstellenmenge des Inputsystems abgeleitet, welches einen beschr\"ankten glatten (lokalen) vollst\"andigen Durchschnitt in $\R^n$ beschreibt. Das Inkrement des Algorithmus ist die Kodimension der polaren Variet\"aten. Die Haupts\"atze sind Satz $\ref{theorem12}$ auf Seite $\pageref{theorem12}$ f\"ur den Hyperfl\"achenfall, und Satz $\ref{theoresult}$ auf Seite $\pageref{theoresult}$, sowie die Aussage in der Einf\"uhrung dieser Arbeit, Seite $\pageref{vollres}$ f\"ur den vollst\"andigen Durchschnitt. / This dissertation deals with {\em geometric algorithms} for solving real multivariate polynomial equation systems, that define a reduced regular sequence (cf. subsection $\ref{abschgeo}$). Real solving means that one has to find at least one real point in each connected component of a real compact and smooth variety $V := W \cap \R^n$. \\ The main point of this thesis is the use of a complex symbolic geometric algorithm, which is designed for an algebraically closed field and was published in the papers \cite{gh2} and \cite{gh3}. The models of computation are {\em straight--line programms} and {\em arithmetic Networks} with parameters in $\; \Q$. Let the polynomials be given by a division--free straight--line programm of size $L$. A geometric solution for the system of equations given by the regular sequence consists in a {\em primitiv element} of the ring extension associated with the system, a minimal polynomial of this primitive element and a parametrization of the coordinates. This representation has a long history going back to {\em Leopold Kronecker} \cite{kron}. The time--complexity of our algorithms turns out to be linear in $L$ and polynomial with respect to $n, d, \delta$ or $\delta '$, respectively. Here $n$ denotes the number of variables, $d$ is an upper bound of the degrees of the polynomials involved in the system, $\delta$ and $\delta '$ are geometric invariants representing the maximum of the {\em affine (geometric) degree} of the system under consideration and the affine (geometric) degree of suitable {\em polar varieties} (cf. \cite{he} for the ({\em geometric}) degree). The application of an algorithm running in the complex numbers to solve polynomial equations in the real case becomes possible by the introduction of polar varieties (cf. \cite{bank}). The polar varieties introduced for this purpose prove to be the corner--stone and the preliminary tool for the efficient use of the geometric algorithm mentioned above. An incremental algorithm is designed to find at least one real point on each connected component of the zero set defined by the input under the assumption that the given semialgebraic set $V = W \cap \R^n$ is a bounded, smooth (local) complete intersection manifold in $\R^n$. The increment of the new algorithm is the codimension of the polar varieties under consideration. The main theorems are Theorem $\ref{theorem12}$ on page $\pageref{theorem12}$ for the hypersurface case, and Theorem $\ref{theoresult}$ on page $\pageref{theoresult}$ for the complete intersection as well as the statement in the introduction of this thesis on page $\pageref{vollres}$.