L’imagerie optique par colorant potentiométrique est une méthode d’enregistrement de l’activité corticale prometteuse, mais dont le potentiel réel est limité par la présence d’artefacts et d’interférences dans les acquisitions. À partir de modèles existant dans la littérature, nous proposons un modèle génératif du signal basé sur un mélange additif de composantes, chacune contrainte dans une union d’espaces linéaires déterminés par son origine biophysique. Motivés par le problème de séparation de composantes qui en découle, qui est un problème inverse linéaire sous-déterminé, nous développons : (1) des régularisations convexes structurées spatialement, favorisant en particulier des solutions parcimonieuses ; (2) un nouvel algorithme proximal de premier ordre pour minimiser efficacement la fonctionnelle qui en résulte ; (3) des méthodes statistiques de sélection de paramètre basées sur l’estimateur non biaisé du risque de Stein. Nous étudions ces outils dans un cadre général, et discutons leur utilité pour de nombreux domaines des mathématiques appliqués, en particulier pour les problèmes inverses ou de régression en grande dimension. Nous développons par la suite un logiciel de séparation de composantes en présence de bruit, dans un environnement intégré adapté à l’imagerie optique par colorant potentiométrique. Finalement, nous évaluons ce logiciel sur différentes données, synthétiques et réelles, montrant des résultats encourageants quant à la possibilité d’observer des dynamiques corticales complexes. / Voltage-sensitive dye optical imaging is a promising recording modality for the cortical activity, but its practical potential is limited by many artefacts and interferences in the acquisitions. Inspired by existing models in the literature, we propose a generative model of the signal, based on an additive mixtures of components, each one being constrained within an union of linear spaces, determined by its biophysical origin. Motivated by the resulting component separation problem, which is an underdetermined linear inverse problem, we develop: (1) convex, spatially structured regularizations, enforcing in particular sparsity on the solutions; (2) a new rst-order proximal algorithm for minimizing e›ciently the resulting functional; (3) statistical methods for automatic parameters selection, based on Stein’s unbiased risk estimate.We study thosemethods in a general framework, and discuss their potential applications in variouselds of applied mathematics, in particular for large scale inverse problems or regressions. We develop subsequently a soŸware for noisy component separation, in an integrated environment adapted to voltage-sensitive dye optical imaging. Finally, we evaluate this soŸware on dišerent data set, including synthetic and real data, showing encouraging perspectives for the observation of complex cortical dynamics.

Le nombre de gènes codant pour des protéines chez l’'homme, le vers rond et la mouche des fruits est du même ordre de grandeur. Cette absence de correspondance entre le nombre de gènes d’un eucaryote et sa complexité phénotypique s’explique en partie par le caractère alternatif de l’épissage.L'épissage alternatif augmente considérablement le répertoire fonctionnel de protéines codées par un nombre limité de gènes. Ce mécanisme, très actif lors du développement embryonnaire, participe au devenir cellulaire. De nombreux troubles génétiques, hérités ou acquis (en particulier certains cancers), se caractérisent par une altération de son fonctionnement.Les technologies de séquençage à haut débit de l'ARN donnent accès a une information plus riche sur le mécanisme de l’épissage. Cependant, si la lecture à haut débit des séquences d’ARN est plus rapide et moins coûteuse, les données qui en sont issues sont complexes et nécessitent le développement d’outils algorithmiques pour leur interprétation. En particulier, la reconstruction des transcrits alternatifs requiert une étape de déconvolution non triviale.Dans ce contexte, cette thèse participe à l'étude des événements d'épissage et des transcrits alternatifs sur des données de séquençage à haut débit de l'ARN.Nous proposons de nouvelles méthodes pour reconstruire et quantifier les transcrits alternatifs de façon plus efficace et précise. Nos contributions méthodologiques impliquent des techniques de régression parcimonieuse, basées sur l'optimisation convexe et sur des algorithmes de flots. Nous étudions également une procédure pour détecter des anomalies d'épissage dans un contexte de diagnostic clinique. Nous suggérons un protocole expérimental facilement opérant et développons de nouveaux modèles statistiques et algorithmes pour quantifier des événements d’épissage et mesurer leur degré d'anormalité chez le patient. / The number of protein-coding genes in a human, a nematodeand a fruit fly are roughly equal.The paradoxical miscorrelation between the number of genesin an organism's genome and its phenotypic complexityfinds an explanation in the alternative natureof splicing in higher organisms.Alternative splicing largely increases the functionaldiversity of proteins encoded by a limitednumber of genes.It is known to be involved incell fate decisionand embryonic development,but also appears to be dysregulatedin inherited and acquired human genetic disorders,in particular in cancers.High-throughput RNA sequencing technologiesallow us to measure and question splicingat an unprecedented resolution.However, while the cost of sequencing RNA decreasesand throughput increases,many computational challenges arise from the discrete and local nature of the data.In particular, the task of inferring alternative transcripts requires a non-trivial deconvolution procedure.In this thesis, we contribute to deciphering alternative transcript expressions andalternative splicing events fromhigh-throughput RNA sequencing data.We propose new methods to accurately and efficientlydetect and quantify alternative transcripts.Our methodological contributionslargely rely on sparse regression techniquesand takes advantage ofnetwork flow optimization techniques.Besides, we investigate means to query splicing abnormalitiesfor clinical diagnosis purposes.We suggest an experimental protocolthat can be easily implemented in routine clinical practice,and present new statistical models and algorithmsto quantify splicing events and measure how abnormal these eventsmight be in patient data compared to wild-type situations.

Les algorithmes convexes de résolution pour les régressions linéaires parcimonieuses possèdent de bonnes performances pratiques et théoriques. Cependant, ils souffrent tous des dimensions du problème qui dictent la complexité de chacune de leur itération. Nous proposons une approche pour réduire ce coût calculatoire au niveau de l'itération. Des stratégies récentes s'appuyant sur des tests d'élimination de variables ont été proposées pour accélérer la résolution des problèmes de régressions parcimonieuse pénalisées tels que le LASSO. Ces approches reposent sur l'idée qu'il est profitable de dédier un petit effort de calcul pour localiser des atomes inactifs afin de les retirer du dictionnaire dans une étape de prétraitement. L'algorithme de résolution utilisant le dictionnaire ainsi réduit convergera alors plus rapidement vers la solution du problème initial. Nous pensons qu'il existe un moyen plus efficace pour réduire le dictionnaire et donc obtenir une meilleure accélération : à l'intérieur de chaque itération de l'algorithme, il est possible de valoriser les calculs originalement dédiés à l'algorithme pour obtenir à moindre coût un nouveau test d'élimination dont l'effet d'élimination augmente progressivement le long des itérations. Le dictionnaire est alors réduit de façon dynamique au lieu d'être réduit de façon statique, une fois pour toutes, avant la première itération. Nous formalisons ce principe d'élimination dynamique à travers une formulation algorithmique générique, et l'appliquons en intégrant des tests d'élimination existants, à l'intérieur de plusieurs algorithmes du premier ordre pour résoudre les problèmes du LASSO et Group-LASSO. / Applications in signal processing and machine learning make frequent use of sparse regressions. Resulting convex problems, such as the LASSO, can be efficiently solved thanks to first-order algorithms, which are general, and have good convergence properties. However those algorithms suffer from the dimension of the problem, which impose the complexity of their iterations. In this thesis we study approaches, based on screening tests, aimed at reducing the computational cost at the iteration level. Such approaches build upon the idea that it is worth dedicating some small computational effort to locate inactive atoms and remove them from the dictionary in a preprocessing stage so that the regression algorithm working with a smaller dictionary will then converge faster to the solution of the initial problem. We believe that there is an even more efficient way to screen the dictionary and obtain a greater acceleration: inside each iteration of the regression algorithm, one may take advantage of the algorithm computations to obtain a new screening test for free with increasing screening effects along the iterations. The dictionary is henceforth dynamically screened instead of being screened statically, once and for all, before the first iteration. Our first contribution is the formalisation of this principle and its application to first-order algorithms, for the resolution of the LASSO and Group-LASSO. In a second contribution, this general principle is combined to active-set methods, whose goal is also to accelerate the resolution of sparse regressions. Applying the two complementary methods on first-order algorithms, leads to great acceleration performances.

De nombreux domaines issus de l'industrie et des sciences appliquées ont été, au cours des dernières années, les témoins d'une révolution numérique. Cette tendance s'est accompagnée d'une croissance continue du volume des données--vidéos, musiques et images, dont le traitement est devenu un véritable défi technique. Par exemple, il est aujourd'hui fréquent de prendre des centaines de photographies de plusieurs millions de pixels, la moindre application de méthodes du traitement de l'image devenant alors une opération difficile. Dans ce contexte, la parcimonie est apparue comme un concept central en apprentissage statistique et traitement du signal. Il est en effet naturel de représenter, analyser et exploiter les données disponibles à travers un nombre réduit de paramètres. Par exemple, on peut imaginer effectuer de la reconnaissance d'objets sur des images de hautes résolutions en n'utilisant qu'un petit sous-ensemble pertinent de pixels. Alors que les approches générales favorisant la parcimonie ont déjà été l'objet de nombreux travaux--débouchant sur d'élégantes fondations théoriques, des outils algorithmiques efficaces et plusieurs succès pratiques--cette thèse se concentre sur une forme particulière et plus récente de parcimonie, nommée parcimonie structurée. Comme son nom l'indique, nous considérerons des situations où nous ne serons pas simplement intéréssés par la parcimonie, mais où nous aurons également à disposition des connaissances a priori nous renseignant sur certaines propriétés structurelles. En continuant d'exploiter l'exemple de la reconnaissance d'objets mentioné ci-dessus, nous savons que des pixels voisins sur une image ont tendance à partager des propriétés similaires, telles que la classe de l'objet à laquelle ils appartiennent. Ainsi, une approche encourageant la parcimonie devrait tirer partie de cette information spatiale. L'objectif de cette thèse est de comprendre et analyser le concept de parcimonie structurée, en se basant sur des considérations statistiques, algorithmiques et appliquées. Nous commencerons par introduire une famille de normes structurées parcimonieuses dont les propriétés sont étudiées en détail. En particulier, nous montrerons à quel type d'information structurelle ces normes correspondent, et nous présenterons sous quelles conditions statistiques elles sont capables de produire une séléction consistente de variables. Nous étudierons ensuite l'apprentissage de dictionnaires parcimonieux et structurés, où nous exploiterons les normes introduites précédemment dans un cadre de factorisation de matrices. L'approche qui en résulte est fléxible et versatile, et nous montrerons que les éléments de dictionnaire appris exhibent une structure parcimonieuse adaptée à la classe de signaux considérée. Concernant l'optimisation, nous proposerons différents outils algorithmiques efficaces et capables de passer à l'échelle, tels que des stratégies à ensemble de variables actives ou encore des méthodes proximales. Grâce à ces outils algorithmiques, nous illustrerons sur de nombreuses applications issues de domaines variés, quand et pourquoi la parcimonie structurée peut être bénéfique. Ces illustrations contiennent par exemple, des tâches de restauration en traitement de l'image, la modélisation de documents textuels sous la forme d'une hiérarchie de thèmes, la prédiction de la taille d'objets à partir de signaux d'imagerie par résonance magnétique fonctionnelle, ou encore des problèmes de segmentation d'images en vision par ordinateur.

L'interprétation abstraite est une méthode générale qui permet de déterminer de manière automatique des invariants de programmes. Cette méthode conduit à résoudre un problème de point fixe non linéaire de grande taille mais qui possède des propriétés de monotonie. Ainsi, déterminer des bornes sur les valeurs prises par une variable au cours de l'exécution d'un programme, est un problème de point fixe équivalent à un problème de jeu à deux joueurs, à somme nulle et avec options d'arrêt. Cette dernière observation explique la mise en oeuvre d'algorithmes d'itérations sur les politiques. Dans un premier temps, nous avons généralisé les domaines numériques polyédriques par un domaine numérique abstrait permettant de représenter des invariants non-linéaires. Nous avons défini une fonction sémantique abstraite sur ce domaine à partir d'une correspondance de Galois. Cependant, l'évaluation de celle-ci est aussi difficile qu'un problème d'optimisation globale non-convexe. Cela nous a amené à définir une fonction sémantique relâchée, construite à partir de la théorie de la dualité, qui sur-approxime de la fonction sémantique abstraite. La théorie de la dualité a également motivé une construction d'une itération sur les politiques dynamique pour calculer des invariants numériques. En pratique pour des programmes écrits en arithmétique affine, nous avons combiné la relaxation de Shor et l'information des fonctions de Lyapunov quadratique pour évaluer la fonction sémantique relâchée et ainsi générer des invariants numériques sous forme d'ellipsoïdes tronquées. Le deuxième travail concerne l'itération sur les politiques et le calcul du plus petit point fixe qui fournit l'invariant le plus précis. Nous avons raffiné l'itération sur les politiques afin de produire le plus petit point fixe dans le cas des jeux stochastiques. Ce raffinement repose sur des techniques de théorie de Perron-Frobenius non-linéaire. En effet, la fonction sémantique abstraite sur les intervalles peut être vue comme un opérateur de Shapley en information parfaite: elle est semidifférentiable. L'approche conjointe de la semidifférentielle et des rayons spectraux non linéaires nous a permis, dans le cas des contractions au sens large de caractériser le plus petit point fixe. Cette approche mène à un critère d'arrêt pour l'itération sur politique dans le cas des fonctions affines par morceaux contractantes au sens large. Quand le point fixe est non minimal, le problème consiste à exhiber un point fixe négatif non nul de la semidifférentielle. Ce vecteur conduit à une nouvelle politique qui fournit un point fixe strictement plus petit que le point fixe courant. Cette approche a été appliquée à quelques exemples de jeux stochastiques à paiements positifs et de vérification de programmes.

Optimization is a scientific discipline that lies at the boundary between pure and applied mathematics. Indeed, while on the one hand some of its developments involve rather theoretical concepts, its most successful algorithms are on the other hand heavily used by numerous companies to solve scheduling and design problems on a daily basis. Our research started with the study of the conic formulation for convex optimization problems. This approach was already studied in the seventies but has recently gained a lot of interest due to development of a new class of algorithms called interior-point methods. This setting is able to exploit the two most important characteristics of convexity: - a very rich duality theory (existence of a dual problem that is strongly related to the primal problem, with a very symmetric formulation), - the ability to solve these problems efficiently, both from the theoretical (polynomial algorithmic complexity) and practical (implementations allowing the resolution of large-scale problems) point of views. Most of the research in this area involved so-called self-dual cones, where the dual problem has exactly the same structure as the primal: the most famous classes of convex optimization problems (linear optimization, convex quadratic optimization and semidefinite optimization) belong to this category. We brought some contributions in this field: - a survey of interior-point methods for linear optimization, with an emphasis on the fundamental principles that lie behind the design of these algorithms, - a computational study of a method of linear approximation of convex quadratic optimization (more precisely, the second-order cone that can be used in the formulation of quadratic problems is replaced by a polyhedral approximation whose accuracy that can be guaranteed a priori), - an application of semidefinite optimization to classification, whose principle consists in separating different classes of patterns using ellipsoids defined in the feature space (this approach was successfully applied to the prediction of student grades). However, our research focussed on a much less studied category of convex problems which does not rely on self-dual cones, i.e. structured problems whose dual is formulated very differently from the primal. We studied in particular - geometric optimization, developed in the late sixties, which possesses numerous application in the field of engineering (entropy optimization, used in information theory, also belongs to this class of problems) - l_p-norm optimization, a generalization of linear and convex quadratic optimization, which allows the formulation of constraints built around expressions of the form |ax+b|^p (where p is a fixed exponent strictly greater than 1). For each of these classes of problems, we introduced a new type of convex cone that made their formulation as standard conic problems possible. This allowed us to derive very simplified proofs of the classical duality results pertaining to these problems, notably weak duality (a mere consequence of convexity) and the absence of a duality gap (strong duality property without any constraint qualification, which does not hold in the general convex case). We also uncovered a very surprising result that stipulates that geometric optimization can be viewed as a limit case of l_p-norm optimization. Encouraged by the similarities we observed, we developed a general framework that encompasses these two classes of problems and unifies all the previously obtained conic formulations. We also brought our attention to the design of interior-point methods to solve these problems. The theory of polynomial algorithms for convex optimization developed by Nesterov and Nemirovsky asserts that the main ingredient for these methods is a computable self-concordant barrier function for the corresponding cones. We were able to define such a barrier function in the case of l_p-norm optimization (whose parameter, which is the main determining factor in the algorithmic complexity of the method, is proportional to the number of variables in the formulation and independent from p) as well as in the case of the general framework mentioned above. Finally, we contributed a survey of the self-concordancy property, improving some useful results about the value of the complexity parameter for certain categories of barrier functions and providing some insight on the reason why the most commonly adopted definition for self-concordant functions is the best possible.

Le problème de l'optimisation des systèmes utilisant l'arithmétique virgule fixe est un problème d'optimisation combinatoire de complexité NP-difficile. Savoir analyser et optimiser des applications complexes et de taille réelle est le thème central de cette thèse. Une technique de type diviser-pour-régner, où un système donné est décomposé en plusieurs petits sous-systèmes organisés selon une hiérarchie est au cœur de cette approche. Cette décomposition ouvre la voie à l'évaluation rapide de la précision et au problème d'optimisation hiérarchique de la largeur des données et des opérations du système. En raison de la réduction du nombre de variables, la convergence du problème d'optimisation hiérarchique vers une solution est beaucoup plus rapide que dans le cas classique. Le modèle "Single Noise Source" (SNS) est proposé pour étudier les statistiques des erreurs de quantification. Au lieu de simplement se concentrer sur la moyenne et la variance du bruit des erreurs dues à la quantification, il fournit également des formules analytiques pour dériver les paramètres statistiques des processus aléatoires produisant les erreurs de quantification équivalentes à une simulation en virgule fixe. En présence des opérations " non-lisses " (un- smooth) telles que la décision dans les modulations QAM, les fonctions Min() ou Max(), etc., il est pour l'instant inévitable d'utiliser la simulation en virgule fixe. Une technique pour l'évaluation analytique des statistiques des erreurs de quantification en présence d'opérateurs non-lisses dans les graphes ne contenant pas de rebouclage est également proposée. Afin de tenir compte également des systèmes ayant des rebouclages, une technique hybride qui utilise le modèle SNS pour accélérer les simulations en virgule fixe est de plus proposée. Un cadre d'utilisation de l'optimisation convexe est proposé comme heuristique pour résoudre le problème d'optimisation des largeurs. Cette nouvelle technique améliore non seulement la qualité de la solution, mais permet de résoudre le problème plus rapidement que les approches itératives classiques. L'application des techniques proposées permet non seulement de réduire les coûts du système mais aussi une réduction de plusieurs ordres de grandeur dans le temps nécessaire pour optimiser les systèmes utilisant l'arithmétique virgule fixe.

Le docking moléculaire est une méthode permettant de prédire l'orientation d'une molécule donnée relativement à une autre lorsque celles-ci forment un complexe. Le premier algorithme de docking moléculaire a vu jour en 1990 afin de trouver de nouveaux candidats face à la protéase du VIH-1. Depuis, l'utilisation de protocoles de docking est devenue une pratique standard dans le domaine de la conception de nouveaux médicaments. Typiquement, un protocole de docking comporte plusieurs phases. Il requiert l'échantillonnage exhaustif du site d'interaction où les éléments impliqués sont considérées rigides. Des algorithmes de clustering sont utilisés afin de regrouper les candidats à l'appariement similaires. Des méthodes d'affinage sont appliquées pour prendre en compte la flexibilité au sein complexe moléculaire et afin d'éliminer de possibles artefacts de docking. Enfin, des algorithmes d'évaluation sont utilisés pour sélectionner les meilleurs candidats pour le docking. Cette thèse présente de nouveaux algorithmes de protocoles de docking qui facilitent la prédiction des structures de complexes protéinaires, une des cibles les plus importantes parmi les cibles visées par les méthodes de conception de médicaments. Une première contribution concerne l‘algorithme Docktrina qui permet de prédire les conformations de trimères protéinaires triangulaires. Celui-ci prend en entrée des prédictions de contacts paire-à-paire à partir d'hypothèse de corps rigides. Ensuite toutes les combinaisons possibles de paires de monomères sont évalués à l'aide d'un test de distance RMSD efficace. Cette méthode à la fois rapide et efficace améliore l'état de l'art sur les protéines trimères. Deuxièmement, nous présentons RigidRMSD une librairie C++ qui évalue en temps constant les distances RMSD entre conformations moléculaires correspondant à des transformations rigides. Cette librairie est en pratique utile lors du clustering de positions de docking, conduisant à des temps de calcul améliorés d'un facteur dix, comparé aux temps de calcul des algorithmes standards. Une troisième contribution concerne KSENIA, une fonction d'évaluation à base de connaissance pour l'étude des interactions protéine-protéine. Le problème de la reconstruction de fonction d'évaluation est alors formulé et résolu comme un problème d'optimisation convexe. Quatrièmement, CARBON, un nouvel algorithme pour l'affinage des candidats au docking basés sur des modèles corps-rigides est proposé. Le problème d'optimisation de corps-rigides est vu comme le calcul de trajectoires quasi-statiques de corps rigides influencés par la fonction énergie. CARBON fonctionne aussi bien avec un champ de force classique qu'avec une fonction d'évaluation à base de connaissance. CARBON est aussi utile pour l'affinage de complexes moléculaires qui comportent des clashes stériques modérés à importants. Finalement, une nouvelle méthode permet d'estimer les capacités de prédiction des fonctions d'évaluation. Celle-ci permet d‘évaluer de façon rigoureuse la performance de la fonction d'évaluation concernée sur des benchmarks de complexes moléculaires. La méthode manipule la distribution des scores attribués et non pas directement les scores de conformations particulières, ce qui la rend avantageuse au regard des critères standard basés sur le score le plus élevé. Les méthodes décrites au sein de la thèse sont testées et validées sur différents benchmarks protéines-protéines. Les algorithmes implémentés ont été utilisés avec succès pour la compétition CAPRI concernant la prédiction de complexes protéine-protéine. La méthodologie développée peut facilement être adaptée pour de la reconnaissance d'autres types d'interactions moléculaires impliquant par exemple des ligands, de l'ARN… Les implémentations en C++ des différents algorithmes présentés seront mises à disposition comme SAMSON Elements de la plateforme logicielle SAMSON sur http://www.samson-connect.net ou sur http://nano-d.inrialpes.fr/software. / Molecular docking is a method that predicts orientation of one molecule with respect to another one when forming a complex. The first computational method of molecular docking was applied to find new candidates against HIV-1 protease in 1990. Since then, using of docking pipelines has become a standard practice in drug discovery. Typically, a docking protocol comprises different phases. The exhaustive sampling of the binding site upon rigid-body approximation of the docking subunits is required. Clustering algorithms are used to group similar binding candidates. Refinement methods are applied to take into account flexibility of the molecular complex and to eliminate possible docking artefacts. Finally, scoring algorithms are employed to select the best binding candidates. The current thesis presents novel algorithms of docking protocols that facilitate structure prediction of protein complexes, which belong to one of the most important target classes in the structure-based drug design. First, DockTrina - a new algorithm to predict conformations of triangular protein trimers (i.e. trimers with pair-wise contacts between all three pairs of proteins) is presented. The method takes as input pair-wise contact predictions from a rigid-body docking program. It then scans and scores all possible combinations of pairs of monomers using a very fast root mean square deviation (RMSD) test. Being fast and efficient, DockTrina outperforms state-of-the-art computational methods dedicated to predict structure of protein oligomers on the collected benchmark of protein trimers. Second, RigidRMSD - a C++ library that in constant time computes RMSDs between molecular poses corresponding to rigid-body transformations is presented. The library is practically useful for clustering docking poses, resulting in ten times speed up compared to standard RMSD-based clustering algorithms. Third, KSENIA - a novel knowledge-based scoring function for protein-protein interactions is developed. The problem of scoring function reconstruction is formulated and solved as a convex optimization problem. As a result, KSENIA is a smooth function and, thus, is suitable for the gradient-base refinement of molecular structures. Remarkably, it is shown that native interfaces of protein complexes provide sufficient information to reconstruct a well-discriminative scoring function. Fourth, CARBON - a new algorithm for the rigid-body refinement of docking candidates is proposed. The rigid-body optimization problem is viewed as the calculation of quasi-static trajectories of rigid bodies influenced by the energy function. To circumvent the typical problem of incorrect stepsizes for rotation and translation movements of molecular complexes, the concept of controlled advancement is introduced. CARBON works well both in combination with a classical force-field and a knowledge-based scoring function. CARBON is also suitable for refinement of molecular complexes with moderate and large steric clashes between its subunits. Finally, a novel method to evaluate prediction capability of scoring functions is introduced. It allows to rigorously assess the performance of the scoring function of interest on benchmarks of molecular complexes. The method manipulates with the score distributions rather than with scores of particular conformations, which makes it advantageous compared to the standard hit-rate criteria. The methods described in the thesis are tested and validated on various protein-protein benchmarks. The implemented algorithms are successfully used in the CAPRI contest for structure prediction of protein-protein complexes. The developed methodology can be easily adapted to the recognition of other types of molecular interactions, involving ligands, polysaccharides, RNAs, etc. The C++ versions of the presented algorithms will be made available as SAMSON Elements for the SAMSON software platform at http://www.samson-connect.net or at http://nano-d.inrialpes.fr/software.

Le docking moléculaire est une méthode permettant de prédire l'orientation d'une molécule donnée relativement à une autre lorsque celles-ci forment un complexe. Le premier algorithme de docking moléculaire a vu jour en 1990 afin de trouver de nouveaux candidats face à la protéase du VIH-1. Depuis, l'utilisation de protocoles de docking est devenue une pratique standard dans le domaine de la conception de nouveaux médicaments. Typiquement, un protocole de docking comporte plusieurs phases. Il requiert l'échantillonnage exhaustif du site d'interaction où les éléments impliqués sont considérées rigides. Des algorithmes de clustering sont utilisés afin de regrouper les candidats à l'appariement similaires. Des méthodes d'affinage sont appliquées pour prendre en compte la flexibilité au sein complexe moléculaire et afin d'éliminer de possibles artefacts de docking. Enfin, des algorithmes d'évaluation sont utilisés pour sélectionner les meilleurs candidats pour le docking. Cette thèse présente de nouveaux algorithmes de protocoles de docking qui facilitent la prédiction des structures de complexes protéinaires, une des cibles les plus importantes parmi les cibles visées par les méthodes de conception de médicaments. Une première contribution concerne l‘algorithme Docktrina qui permet de prédire les conformations de trimères protéinaires triangulaires. Celui-ci prend en entrée des prédictions de contacts paire-à-paire à partir d'hypothèse de corps rigides. Ensuite toutes les combinaisons possibles de paires de monomères sont évalués à l'aide d'un test de distance RMSD efficace. Cette méthode à la fois rapide et efficace améliore l'état de l'art sur les protéines trimères. Deuxièmement, nous présentons RigidRMSD une librairie C++ qui évalue en temps constant les distances RMSD entre conformations moléculaires correspondant à des transformations rigides. Cette librairie est en pratique utile lors du clustering de positions de docking, conduisant à des temps de calcul améliorés d'un facteur dix, comparé aux temps de calcul des algorithmes standards. Une troisième contribution concerne KSENIA, une fonction d'évaluation à base de connaissance pour l'étude des interactions protéine-protéine. Le problème de la reconstruction de fonction d'évaluation est alors formulé et résolu comme un problème d'optimisation convexe. Quatrièmement, CARBON, un nouvel algorithme pour l'affinage des candidats au docking basés sur des modèles corps-rigides est proposé. Le problème d'optimisation de corps-rigides est vu comme le calcul de trajectoires quasi-statiques de corps rigides influencés par la fonction énergie. CARBON fonctionne aussi bien avec un champ de force classique qu'avec une fonction d'évaluation à base de connaissance. CARBON est aussi utile pour l'affinage de complexes moléculaires qui comportent des clashes stériques modérés à importants. Finalement, une nouvelle méthode permet d'estimer les capacités de prédiction des fonctions d'évaluation. Celle-ci permet d‘évaluer de façon rigoureuse la performance de la fonction d'évaluation concernée sur des benchmarks de complexes moléculaires. La méthode manipule la distribution des scores attribués et non pas directement les scores de conformations particulières, ce qui la rend avantageuse au regard des critères standard basés sur le score le plus élevé. Les méthodes décrites au sein de la thèse sont testées et validées sur différents benchmarks protéines-protéines. Les algorithmes implémentés ont été utilisés avec succès pour la compétition CAPRI concernant la prédiction de complexes protéine-protéine. La méthodologie développée peut facilement être adaptée pour de la reconnaissance d'autres types d'interactions moléculaires impliquant par exemple des ligands, de l'ARN… Les implémentations en C++ des différents algorithmes présentés seront mises à disposition comme SAMSON Elements de la plateforme logicielle SAMSON sur http://www.samson-connect.net ou sur http://nano-d.inrialpes.fr/software. / Molecular docking is a method that predicts orientation of one molecule with respect to another one when forming a complex. The first computational method of molecular docking was applied to find new candidates against HIV-1 protease in 1990. Since then, using of docking pipelines has become a standard practice in drug discovery. Typically, a docking protocol comprises different phases. The exhaustive sampling of the binding site upon rigid-body approximation of the docking subunits is required. Clustering algorithms are used to group similar binding candidates. Refinement methods are applied to take into account flexibility of the molecular complex and to eliminate possible docking artefacts. Finally, scoring algorithms are employed to select the best binding candidates. The current thesis presents novel algorithms of docking protocols that facilitate structure prediction of protein complexes, which belong to one of the most important target classes in the structure-based drug design. First, DockTrina - a new algorithm to predict conformations of triangular protein trimers (i.e. trimers with pair-wise contacts between all three pairs of proteins) is presented. The method takes as input pair-wise contact predictions from a rigid-body docking program. It then scans and scores all possible combinations of pairs of monomers using a very fast root mean square deviation (RMSD) test. Being fast and efficient, DockTrina outperforms state-of-the-art computational methods dedicated to predict structure of protein oligomers on the collected benchmark of protein trimers. Second, RigidRMSD - a C++ library that in constant time computes RMSDs between molecular poses corresponding to rigid-body transformations is presented. The library is practically useful for clustering docking poses, resulting in ten times speed up compared to standard RMSD-based clustering algorithms. Third, KSENIA - a novel knowledge-based scoring function for protein-protein interactions is developed. The problem of scoring function reconstruction is formulated and solved as a convex optimization problem. As a result, KSENIA is a smooth function and, thus, is suitable for the gradient-base refinement of molecular structures. Remarkably, it is shown that native interfaces of protein complexes provide sufficient information to reconstruct a well-discriminative scoring function. Fourth, CARBON - a new algorithm for the rigid-body refinement of docking candidates is proposed. The rigid-body optimization problem is viewed as the calculation of quasi-static trajectories of rigid bodies influenced by the energy function. To circumvent the typical problem of incorrect stepsizes for rotation and translation movements of molecular complexes, the concept of controlled advancement is introduced. CARBON works well both in combination with a classical force-field and a knowledge-based scoring function. CARBON is also suitable for refinement of molecular complexes with moderate and large steric clashes between its subunits. Finally, a novel method to evaluate prediction capability of scoring functions is introduced. It allows to rigorously assess the performance of the scoring function of interest on benchmarks of molecular complexes. The method manipulates with the score distributions rather than with scores of particular conformations, which makes it advantageous compared to the standard hit-rate criteria. The methods described in the thesis are tested and validated on various protein-protein benchmarks. The implemented algorithms are successfully used in the CAPRI contest for structure prediction of protein-protein complexes. The developed methodology can be easily adapted to the recognition of other types of molecular interactions, involving ligands, polysaccharides, RNAs, etc. The C++ versions of the presented algorithms will be made available as SAMSON Elements for the SAMSON software platform at http://www.samson-connect.net or at http://nano-d.inrialpes.fr/software.

Les robots flexibles sont de plus en plus utilisés dans les applications pratiques. Ces robots sont caractérisés par une conception mécanique légère, réduisant ainsi leur encombrement, leur consommation d’énergie et améliorant leur sécurité. Cependant, la présence de vibrations transitoires rend difficile un contrôle précis de la trajectoire de ces systèmes. Cette thèse est précisément consacrée à l’asservissement en position des manipulateurs flexibles dans les espaces articulaire et opérationnel. Des méthodes de commande avancées, basées sur des outils de la commande robuste et de l’optimisation convexe, ont été proposées. Ces méthodes font en particulier appel à la théorie des systèmes linéaires à paramètres variants (LPV) et aux inégalités matricielles linéaires (LMI). En comparaison avec des lois de commande non-linéaires disponibles dans la littérature, les lois de commande LPV proposées permettent de considérerdes contraintes de performance et de robustesse de manière simple et systématique. L’accent est porté dans notre travail sur la gestion appropriée de la dépendance paramétrique du modèle LPV, en particulier les dépendances polynomiale et rationnelle. Des simulations numériques effectuées dans des conditions réalistes, ont permis d’observer une meilleure robustesse de la commande LPV par rapport à la commande non-linéaire par inversion de modèle face aux bruits de mesure, aux excitations de haute fréquence et aux incertitudes de modèle. / Flexible robots are becoming more and more common in practical applications. This type of robots is characterized by the use of lightweight materials, which allows reducing their size, their power consumption and improves their safety. However, an accurate trajectory tracking of these systems is difficult to achieve because of the transient vibrations they undergo. This PhD thesis work is particularly devoted to the position control of flexible robotic manipulators at the joint and end-effector levels. Advanced control methods, based on some tools of the robust control theory and convex optimization, have been proposed. These methods are based on the theory of Linear Parameter Varying (LPV) systems and Linear Matrix Inequalities (LMI). Compared to some nonlinear control laws available in the literature that involve model inversion, theproposed LPV control laws make it possible to consider performance and robustness constraints in a simple and systematic manner. Our work particularly emphasizes on the appropriate management of the parametric dependence of the LPV model, especially the polynomial and rational dependences. Numerical simulations carried out in realistic operating conditions have shown a better robustness of the LPV control compared to the inversion-based nonlinear control withrespect to measurement noise, high frequency inputs and model uncertainties.