No description available.

Throughout biological, chemical, and pharmaceutical research,conformational searches are used to explore the possiblethree-dimensional configurations of molecules. This thesis describesa new systematic method for conformational search, including anapplication of the method to determining the structure of a peptidevia solid-state NMR spectroscopy. A separate portion of the thesis isabout protein-DNA binding, with a three-dimensional macromolecularstructure determined by x-ray crystallography.The search method in this thesis enumerates all conformations of amolecule (at a given level of torsion angle resolution) that satisfy aset of local geometric constraints, such as constraints derived fromNMR experiments. Systematic searches, historically used for smallmolecules, generally now use some form of divide-and-conquer forapplication to larger molecules. Our method can achieve a significantimprovement in runtime by making some major and counter-intuitivemodifications to traditional divide-and-conquer:(1) OmniMerge divides a polymer into many alternative pairs ofsubchains and searches all the pairs, instead of simply cutting inhalf and searching two subchains. Although the extra searches mayappear wasteful, the bottleneck stage of the overall search, which isto re-connect the conformations of the largest subchains, can be greatlyaccelerated by the availability of alternative pairs of sidechains.(2) Propagation of disqualified conformations acrossoverlapping subchains can disqualify infeasible conformations veryrapidly, which further offsets the cost of searching the extrasubchains of OmniMerge.(3) The search may be run in two stages, once at low-resolutionusing a side-effect of OmniMerge to determine an optimalpartitioning of the molecule into efficient subchains; then again athigh-resolution while making use of the precomputed subchains.(4) An A* function prioritizes each subchain based onestimated future search costs. Subchains with sufficiently lowpriority can be omitted from the search, which improves efficiency.A common theme of these four ideas is to make good choices about howto break the large search problem into lower-dimensional subproblems.In addition, the search method uses heuristic local searches withinthe overall systematic framework, to maintain the systematic guaranteewhile providing the empirical efficiency of stochastic search.These novel algorithms were implemented and the effectiveness of eachinnovation is demonstrated on a highly constrained peptide with 40degrees of freedom.

No description available.

Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-09-24T19:32:19Z (GMT). No. of bitstreams: 1 Alves_RafaelSantosdeOliveira_D.pdf: 2213205 bytes, checksum: 67a1681eb02b103974e57e3047edc755 (MD5) Previous issue date: 2013 / Resumo: O Problema de Geometria de Distâncias Moleculares (PGDM) consiste em encontrar uma imersão tridimensional de um grafo simples, não orientado, de forma que o peso nas arestas corresponda às distâncias inter-atômicas de uma molécula. Este é um problema de busca em um espaço contínuo, mas que pode ser discretizado sob algumas exigências, dando origem ao PGDM discretizado (PGDMD), que é solucionado usando informações sobre distâncias entre alguns átomos da molécula através de um algoritmo Branch and Prune (BP). Caso as distâncias sejam dadas por um conjunto de limites inferiores e superiores, temos um novo problema: o PGDMD intervalar (iPGDMD). A partir da interpretação geométrica deste último, propomos uma nova abordagem utilizando a Álgebra de Clifford a fim de tornar o algoritmo BP mais eficiente e de poder tratar algebricamente os problemas relacionados ao tratamento das distâncias intervalares / Abstract: The Molecular Distance Geometry Problem (MDGP) consists in finding a three dimensional embedding of simple, weighted, undirected graph such that the weight in the edges correspond to the inter-atomic distances of a molecule. This is a continuous search problem which can be discretized under some assumptions, yielding the Discretized MDGP (DMDGP), which is solved by a Branch and Prune (BP) algorithm using information about the distances among some atoms of the molecule. If the distances are given by a set of lower and upper bounds, a new problem arises: the interval DMDGP (iDMDGP). From a geometric interpretation of this problem, we propose a new approach, using Clifford Algebras, in order to improve the BP efficiency and treat algebraically the issues related to interval distances / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

OmniMerge performs a systematic search to enumerate all conformations of a molecule (at a given level of torsion-angle resolution) that satisfy a set of local geometric constraints. Constraints would typically come from NMR experiments, but applications such as docking or homology modeling could also give rise to similar constraints. The molecule to be searched is partitioned into small subchains so that the set of possible conformations for the whole molecule may be constructed by merging the feasible conformations for the subchain parts. However, instead of using a binary tree for straightforward divide-and-conquer, OmniMerge defines a sub-problem for every possible subchain of the molecule. Searching every subchain provides a counter-intuitive advantage: with every possible subdivision available for merging, one may choose the most favorable merge for each subchain, particularly for the bottleneck chain(s). Improving the bottleneck step may therefore cause the whole search to be completed more quickly. Finally, to discard infeasible conformations more rapidly, OmniMerge filters the solution set of each subchain based on compatibility with the solutions sets of all overlapping subchains. These two innovations—choosing the most favorable merges and enforcing consistency between overlapping subchains—yield significant improvements in run time. By determining the extent of structural variability permitted by a set of constraints, OmniMerge offers the potential to aid error analysis and improve confidence for NMR results on peptides and moderate-sized molecules. / Singapore-MIT Alliance (SMA)

Orientadores: Carlile Campos Lavor, Tibérius de Oliveira e Bonates / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T15:11:50Z (GMT). No. of bitstreams: 1 Lima_JorgeFerreiraAlencar_D.pdf: 1109545 bytes, checksum: 086223c23c920a9abe0d3661769a6a7d (MD5) Previous issue date: 2015 / Resumo: Geometria de Distâncias Euclidianas (GDE) é o estudo da geometria euclidiana baseado no conceito de distância. É uma teoria útil em diversas aplicações, onde os dados consistem em um conjunto de distâncias e as possíveis soluções são pontos em algum espaço euclidiano que realizam as distâncias dadas. O problema chave em GDE é conhecido como Problema de Geometria de Distâncias (PGD), em que é dado um inteiro K>0 e um grafo simples, não direcionado, ponderado G=(V,E,d), cujas arestas são ponderadas por uma função não negativa d, e queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Consideramos tanto problemas teóricos quanto aplicações da GDE. Em termos teóricos, demonstramos a quantidade exata de soluções de uma classe de PGDs muito importante para problemas de conformação molecular e, além disso, conseguimos condições necessárias e suficientes para determinar quando um grafo completo associado a um PGD é realizável e qual o espaço euclidiano com dimensão mínima para tal realização. Em termos práticos, desenvolvemos um algoritmo que calcula tal realização em dimensão mínima com resultados superiores a um algoritmo clássico da literatura. Finalmente, mostramos uma aplicação direta do PGD em problemas de escalonamento multidimensional / Abstract: Euclidean distance geometry (EDG) is the study of Euclidean geometry based on the concept of distance. This is useful in several applications, where the input data consists of an incomplete set of distances and the output is a set of points in some Euclidean space realizing the given distances. The key problem in EDG is known as the Distance Geometry Problem (DGP), where an integer K>0 is given, as well as a simple undirected weighted graph G=(V,E,d), whose edges are weighted by a non-negative function d. The problem consists in determining whether or not there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space, in such a way that those coordinates satisfy all distances given by d. We considered both theoretical issues and applications of EDG. In theoretical terms, we proved the exact number of solutions of a subclass of DGP that is very important in the molecular conformation problems. Moreover, we described necessary and sufficient conditions for determining whether a complete graph associated to a DGP is realizable and the minimum dimension of such realization. In practical terms, we developed an algorithm that computes such realization, which outperforms a classical algorithm from the literature. Finally, we showed a direct application of DGP to multidimensional scaling / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

In this paper we will study the 1p spaces. We will begin with definitions and different examples of 1p spaces. In particular, we will prove Holder's and Minkowski's inequalities for 1p sequence.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第23220号 / 工博第4864号 / 新制||工||1759(附属図書館) / 京都大学大学院工学研究科分子工学専攻 / (主査)教授 佐藤 啓文, 教授 佐藤 徹, 教授 田中 勝久 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

This thesis addresses the kinematic analysis of mechanisms, in particular, the position analysis of kinematic chains, or linkages, that is, mechanisms with rigid bodies (links) interconnected by kinematic pairs (joints). This problem, of completely geometrical nature, consists in finding the feasible assembly modes that a kinematic chain can adopt. An assembly mode is a possible relative transformation between the links of a kinematic chain. When an assignment of positions and orientations is made for all links with respect to a given reference frame, an assembly mode is called a configuration. The methods reported in the literature for solving the position analysis of kinematic chains can be classified as graphical, analytical, or numerical. The graphical approaches are mostly geometrical and designed to solve particular problems. The analytical and numerical methods deal, in general, with kinematic chains of any topology and translate the original geometric problem into a system of kinematic analysis of all the Assur kinematic chains resulting from replacing some of its revolute joints by slider joints. Thus, it is concluded that the polynomials of all fully-parallel planar robots can be derived directly from that of the widely known 3-RPR robot. In addition to these results, this thesis also presents an efficient procedure, based on distance and oriented area constraints, and geometrical arguments, to trace coupler curves of pin-jointed Gr¨ubler kinematic chains. All these techniques and results together are contributions to theoretical kinematics of mechanisms, robot kinematics, and distance plane geometry. equations that defines the location of each link based, mainly, on independent loop equations. In the analytical approaches, the system of kinematic equations is reduced to a polynomial, known as the characteristic polynomial of the linkage, using different elimination methods —e.g., Gr¨obner bases or resultant techniques. In the numerical approaches, the system of kinematic equations is solved using, for instance, polynomial continuation or interval-based procedures. In any case, the use of independent loop equations to solve the position analysis of kinematic chains, almost a standard in kinematics of mechanisms, has seldom been questioned despite the resulting system of kinematic equations becomes quite involved even for simple linkages. Moreover, stating the position analysis of kinematic chains directly in terms of poses, with or without using independent loop equations, introduces two major disadvantages: arbitrary reference frames has to be included, and all formulas involve translations and rotations simultaneously. This thesis departs from this standard approach by, instead of directly computing Cartesian locations, expressing the original position problem as a system of distance-based constraints that are then solved using analytical and numerical procedures adapted to their particularities. In favor of developing the basics and theory of the proposed approach, this thesis focuses on the study of the most fundamental planar kinematic chains, namely, Baranov trusses, Assur kinematic chains, and pin-jointed Gr¨ubler kinematic chains. The results obtained have shown that the novel developed techniques are promising tools for the position analysis of kinematic chains and related problems. For example, using these techniques, the characteristic polynomials of most of the cataloged Baranov trusses can be obtained without relying on variable eliminations or trigonometric substitutions and using no other tools than elementary algebra. An outcome in clear contrast with the complex variable eliminations require when independent loop equations are used to tackle the problem. The impact of the above result is actually greater because it is shown that the characteristic polynomial of a Baranov truss, derived using the proposed distance-based techniques, contains all the necessary and sufficient information for solving the position / Esta tesis aborda el problema de análisis de posición de cadenas cinemáticas, mecanismos con cuerpos rígidos (enlaces) interconectados por pares cinemáticos (articulaciones). Este problema, de naturaleza geométrica, consiste en encontrar los modos de ensamblaje factibles que una cadena cinemática puede adoptar. Un modo de ensamblaje es una transformación relativa posible entre los enlaces de una cadena cinemática. Los métodos reportados en la literatura para la solución del análisis de posición de cadenas cinemáticas se pueden clasificar como gráficos, analíticos o numéricos. Los enfoques gráficos son geométricos y se diseñan para resolver problemas particulares. Los métodos analíticos y numéricos tratan con cadenas cinemáticas de cualquier topología y traducen el problema geométrico original en un sistema de ecuaciones cinemáticas que define la ubicación de cada enlace, basado generalmente en ecuaciones de bucle independientes. En los enfoques analíticos, el sistema de ecuaciones cinemáticas se reduce a un polinomio, conocido como el polinomio característico de la cadena cinemática, utilizando diferentes métodos de eliminación. En los métodos numéricos, el sistema se resuelve utilizando, por ejemplo, la continuación polinomial o procedimientos basados en intervalos. En cualquier caso, el uso de ecuaciones de bucle independientes, un estándar en cinemática de mecanismos, rara vez ha sido cuestionado a pesar de que el sistema resultante de ecuaciones es bastante complicado, incluso para cadenas simples. Por otra parte, establecer el análisis de la posición de cadenas cinemáticas directamente en términos de poses, con o sin el uso de ecuaciones de bucle independientes, presenta dos inconvenientes: sistemas de referencia arbitrarios deben ser introducidos, y todas las fórmulas implican traslaciones y rotaciones de forma simultánea. Esta tesis se aparta de este enfoque estándar expresando el problema de posición original como un sistema de restricciones basadas en distancias, en lugar de directamente calcular posiciones cartesianas. Estas restricciones son posteriormente resueltas con procedimientos analíticos y numéricos adaptados a sus particularidades. Con el propósito de desarrollar los conceptos básicos y la teoría del enfoque propuesto, esta tesis se centra en el estudio de las cadenas cinemáticas planas más fundamentales, a saber, estructuras de Baranov, cadenas cinemáticas de Assur, y cadenas cinemáticas de Grübler. Los resultados obtenidos han demostrado que las técnicas desarrolladas son herramientas prometedoras para el análisis de posición de cadenas cinemáticas y problemas relacionados. Por ejemplo, usando dichas técnicas, los polinomios característicos de la mayoría de las estructuras de Baranov catalogadas se puede obtener sin realizar eliminaciones de variables o sustituciones trigonométricas, y utilizando solo álgebra elemental. Un resultado en claro contraste con las complejas eliminaciones de variables que se requieren cuando se utilizan ecuaciones de bucle independientes. El impacto del resultado anterior es mayor porque se demuestra que el polinomio característico de una estructura de Baranov, derivado con las técnicas propuestas, contiene toda la información necesaria y suficiente para resolver el análisis de posición de las cadenas cinemáticas de Assur que resultan de la sustitución de algunas de sus articulaciones de revolución por articulaciones prismáticas. De esta forma, se concluye que los polinomios de todos los robots planares totalmente paralelos se pueden derivar directamente del polinomio característico del conocido robot 3-RPR. Adicionalmente, se presenta un procedimiento eficaz, basado en restricciones de distancias y áreas orientadas, y argumentos geométricos, para trazar curvas de acoplador de cadenas cinemáticas de Grübler. En conjunto, todas estas técnicas y resultados constituyen contribuciones a la cinemática teórica de mecanismos, la cinemática de robots, y la geometría plana de distancias. Barcelona 13-

Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T18:42:28Z (GMT). No. of bitstreams: 1 Rezende_GermanoAbudde_D.pdf: 1418033 bytes, checksum: 61d29b02274278ede5ffca797e26371a (MD5) Previous issue date: 2014 / Resumo: A geometria de distâncias é o estudo da geometria baseado no conceito de distância. Ela é útil em várias aplicações, onde os dados de entrada consistem de um conjunto incompleto de distâncias, e a saída é um conjunto de pontos no espaço euclidiano, que realiza as distâncias dadas. No Problema de Geometria de Distâncias (DGP), é dado um inteiro K > 0 e um grafo simples, não direcionado, G = (V,E,d), cujas arestas são ponderadas por uma função não negativa d. Queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Um DGPk (com K fixado) está fortemente relacionado a um outro tipo de problema, que trata dos possíveis completamentos de uma certa matriz de distâncias euclidianas. Este último pode ser visto, em um certo sentido, como o "dual do primeiro problema". Neste trabalho, exploramos essa dualidade com a finalidade de propor melhorias no método Branch-and-Prune aplicado a uma versão discreta do DGPk / Abstract: Distance Geometry is the study of geometry based on the concept of distance. It is useful in many applications where the input data consists of an incomplete set of distances, and the output is a set of points in some Euclidean space which realizes the given distances. In the Distance Geometry Problem (DGP), it is given an integer K > 0 and a simple undirected weighted graph G = (V,E,d), whose edges are weighted by a non-negative function d. We want to determine if there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space satisfying all distance constraints given by d. A DGPk (with K fixed) is closely related to another type of problem, which treats the possible completions of a certain Euclidean distance matrix. In some sense, this is the "dual" of the first problem. We explore this duality in order to improve the Branch-and-Prune method applied to a discrete version of the DGPk / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada