Nonparametric generalized belief propagation based on pseudo-junction tree for cooperative localization in wireless networks

Non-parametric belief propagation (NBP) is a well-known message passing method for cooperative localization in wireless networks. However, due to the over-counting problem in the networks with loops, NBP’s convergence is not guaranteed, and its estimates are typically less accurate. One solution for this problem is non-parametric generalized belief propagation based on junction tree. However, this method is intractable in large-scale networks due to the high-complexity of the junction tree formation, and the high-dimensionality of the particles. Therefore, in this article, we propose the non-parametric generalized belief propagation based on pseudo-junction tree (NGBP-PJT). The main difference comparing with the standard method is the formation of pseudo-junction tree, which represents the approximated junction tree based on thin graph. In addition, in order to decrease the number of high-dimensional particles, we use more informative importance density function, and reduce the dimensionality of the messages. As by-product, we also propose NBP based on thin graph (NBP-TG), a cheaper variant of NBP, which runs on the same graph as NGBP-PJT. According to our simulation and experimental results, NGBP-PJT method outperforms NBP and NBP-TG in terms of accuracy, computational, and communication cost in reasonably sized networks.

Supporting pruning in tabled LP

This paper analyzes issues which appear when supporting pruning operators in tabled LP. A version of the once/1 control predicate tailored for tabled predicates is presented, and an implementation analyzed and evaluated. Using once/1 with answer-on-demand strategies makes it possible to avoid computing unneeded solutions for problems which can benefit from tabled LP but in which only a single solution is needed, such as model checking and planning. The proposed version of once/1 is also directly applicable to the efficient implementation of other optimizations, such as early completion, cut-fail loops (to, e.g., prune at the top level), if-then-else, and constraint-based branch-and-bound optimization. Although once/1 still presents open issues such as dependencies of tabled solutions on program history, our experimental evaluation confirms that it provides an arbitrarily large efficiency improvement in several application areas.

Diseño acústico y electroacústico de Waipahu Transit Center en Honolulú, Hawái

El objetivo de este Proyecto Fin de Grado es el diseño de megafonía y PAGA (Public Address /General Alarm) de la estación de tren Waipahu Transit Center en la ciudad de Honolulú, Hawái. Esta estación forma parte de una nueva línea de tren que está en proceso de construcción actualmente llamada Honolulu Rail Transit. Inicialmente la línea de tren constará de 21 estaciones, en las que prácticamente todas están diseñadas como pasos elevados usando como referencia las autopistas que cruzan la isla. Se tiene prevista su fecha de finalización en el año 2019, aunque las primeras estaciones se inaugurarán en 2017. Se trata en primer lugar un estudio acústico del recinto a sonorizar, eligiendo los equipos necesarios: conmutadores, altavoces, amplificadores, procesador, equipo de control y micrófonos. Este primer estudio sirve para obtener una aproximación de equipos necesarios, así como la posible situación de estos dentro de la estación. Tras esto, se procede a la simulación de la estación mediante el programa de simulación acústica y electroacústica EASE 4.4. Para ello, se diseña la estación en un modelo 3D, en el que cada superficie se asocia a su material correspondiente. Para facilitar el diseño y el cómputo de las simulaciones se divide la estación en 3 partes por separado. Cada una corresponde a un nivel de la estación: Ground level, el nivel inferior que contiene la entrada; Concourse Level, pasillo que comunica los dos andenes; y Platform Level, en el que realizarán las paradas los trenes. Una vez realizado el diseño se procede al posicionamiento de altavoces en los diferentes niveles de la estación. Debido al clima existente en la isla, el cual ronda los 20°C a lo largo de todo el año, no es necesaria la instalación de sistemas de aire acondicionado o calefacción, por lo que la estación no está totalmente cerrada. Esto supone un problema al realizar las simulaciones en EASE, ya que al tratarse de un recinto abierto se deberán hallar parámetros como el tiempo de reverberación o el volumen equivalente por otros medios. Para ello, se utilizará el método Ray Tracing, mediante el cual se halla el tiempo de reverberación por la respuesta al impulso de la sala; y a continuación se calcula un volumen equivalente del recinto mediante la fórmula de Eyring. Con estos datos, se puede proceder a calcular los parámetros necesarios: nivel de presión sonora directo, nivel de presión sonora total y STI (Speech Transmission Index). Para obtener este último será necesario ecualizar antes en cada uno de los niveles de la estación. Una vez hechas las simulaciones, se comprueba que el nivel de presión sonora y los valores de inteligibilidad son acordes con los requisitos dados por el cliente. Tras esto, se procede a realizar los bucles de altavoces y el cálculo de amplificadores necesarios. Se estudia la situación de los micrófonos, que servirán para poder variar la potencia emitida por los altavoces dependiendo del nivel de ruido en la estación. Una vez obtenidos todos los equipos necesarios en la estación, se hace el conexionado entre éstos, tanto de una forma simplificada en la que se pueden ver los bucles de altavoces en cada nivel de la estación, como de una forma más detallada en la que se muestran las conexiones entre cada equipo del rack. Finalmente, se realiza el etiquetado de los equipos y un presupuesto estimado con los costes del diseño del sistema PAGA. ABSTRACT. The aim of this Final Degree Project is the design of the PAGA (Public Address / General Alarm) system in the train station Waipahu Transit Center in the city of Honolulu, Hawaii. This station is part of a new rail line that is currently under construction, called Honolulu Rail Transit. Initially, the rail line will have 21 stations, in which almost all are designed elevated using the highways that cross the island as reference. At first, it is treated an acoustic study in the areas to cover, choosing the equipment needed: switches, loudspeakers, amplifiers, DPS, control station and microphones. This first study helps to obtain an approximation of the equipments needed, as well as their placement inside the station. Thereafter, it is proceeded to do the simulation of the station through the acoustics and electroacoustics simulation software EASE 4.4. In order to do that, it is made the 3D design of the station, in which each surface is associated with its material. In order to ease the design and calculation of the simulations, the station has been divided in 3 zones. Each one corresponds with one level of the station: Ground Level, the lower level that has the entrance; Concourse Level, a corridor that links the two platforms; and Platform Level, where the trains will stop. Once the design is made, it is proceeded to place the speakers in the different levels of the station. Due to the weather in the island, which is about 20°C throughout the year, it is not necessary the installation of air conditioning or heating systems, so the station is not totally closed. This cause a problem when making the simulations in EASE, as the project is open, and it will be necessary to calculate parameters like the reverberation time or the equivalent volume by other methods. In order to do that, it will be used the Ray Tracing method, by which the reverberation time is calculated by the impulse response; and then it is calculated the equivalent volume of the area with the Eyring equation. With this information, it can be proceeded to calculate the parameters needed: direct sound pressure level, total sound pressure level and STI (Speech Transmission Index). In order to obtain the STI, it will be needed to equalize before in each of the station’s levels. Once the simulations are done, it is checked that the sound pressure level and the intelligibility values agree with the requirements given by the client. After that, it is proceeded to perform the speaker’s loops and the calculation of the amplifiers needed. It is studied the placement of the microphones, which will help to vary the power emitted by the speakers depending on the background noise level in the station. Once obtained all the necessary equipment in the station, it is done the connection diagram, both a simplified diagram in which there can be seen the speaker’s loops in each level of the station, or a more detailed diagram in which it is shown the wiring between each equipment of the rack. At last, it is done the labeling of the equipments and an estimated budget with the expenses for the PAGA design.

A sharing-based approach to supporting adaptation in service compositions

Data-related properties of the activities involved in a service composition can be used to facilitate several design-time and run-time adaptation tasks, such as service evolution, distributed enactment, and instance-level adaptation. A number of these properties can be expressed using a notion of sharing. We present an approach for automated inference of data properties based on sharing analysis, which is able to handle service compositions with complex control structures, involving loops and sub-workflows. The properties inferred can include data dependencies, information content, domain-defined attributes, privacy or confidentiality levels, among others. The analysis produces characterizations of the data and the activities in the composition in terms of minimal and maximal sharing, which can then be used to verify compliance of potential adaptation actions, or as supporting information in their generation. This sharing analysis approach can be used both at design time and at run time. In the latter case, the results of analysis can be refined using the composition traces (execution logs) at the point of execution, in order to support run-time adaptation.

Instalación de un sistema funcional sobre un computador convencional

En esta tesis se tratan dos aspectos fundamentales de los sistemas funcionales, de cuyo tratamiento depende, en gran medida, la eficiencia de tales sistemas. En primer lugar, se presentan y evalúan una serie de soluciones al problema de representación interna en los sistemas funcionales, soluciones basadas en la utilización de estructuras lineales para obtener una mejora en el tiempo de ejecución y en la ocupación de la memoria del sistema. En segundo lugar, se presenta un sistema de evaluación multitarea para reducir programas funcionales, basado en la especificación de varios ficheros de salida. En él, las tareas del sistema evalúan, de forma concurrente, las diversas partes del resultado de un programa y se .comunican entre sí en base a mensajes que permiten detectar y resolver, sin necesidad de abortar la ejecución, bucles de dependencias entre tareas. El sistema reacciona ante estas situaciones de error de forma comedida, de modo que este error no afecta al resto de las tareas del sistema. Se plantea también un mecanismo de gestión de memoria, mecanismo que introduce una tarea especial en el sistema, encargada de la gestión de una memoria común a todo él, y satisface las necesidades de memoria de las tareas de forma, transparente al mecanismo de evaluación.---ABSTRACT---Two fundamental aspects of functional systems, of which their efficiency to a large extent depends, are dealt with in this thesis. Firstly, several solutions to the internal representation problem of functional systems are proposed and evaluated. These solutions are based on the use of linear data structures in order to achieve a shorter execution time and smaller memory requirement. Secondly, a new multitask evaluation system for the reduction of functional programs is described; it is based on the specifücation of several output files. In this evaluation system, the task evaluates in the different parts of the program result concurrently. Tasks communicate one another through messages, which make it possible to detect and solve the dependency loops within tasks. The program does not need to be aborted, the sistem reacts to such error situations in a smooth way, no other tasks are affected. A memory management system is also introduced. This management system inserts a special task, that carries-out the management of a common memory and serves all tasks memory requirements in a transparent mode to the evaluation mechanism.

VHDL-based system design of a cognitive sensorimotor loop (CSL) for haptic Human-Machine Interaction (HMI)

This document is a summary of the Bachelor thesis titled “VHDL-Based System Design of a Cognitive Sensorimotor Loop (CSL) for Haptic Human-Machine Interaction (HMI)” written by Pablo de Miguel Morales, Electronics Engineering student at the Universidad Politécnica de Madrid (UPM Madrid, Spain) during an Erasmus+ Exchange Program at the Beuth Hochschule für Technik (BHT Berlin, Germany). The tutor of this project is Dr. Prof. Hild. This project has been developed inside the Neurobotics Research Laboratory (NRL) in close collaboration with Benjamin Panreck, a member of the NRL, and another exchange student from the UPM Pablo Gabriel Lezcano. For a deeper comprehension of the content of the thesis, a deeper look in the document is needed as well as the viewing of the videos and the VHDL design. In the growing field of automation, a large amount of workforce is dedicated to improve, adapt and design motor controllers for a wide variety of applications. In the specific field of robotics or other machinery designed to interact with humans or their environment, new needs and technological solutions are often being discovered due to the existing, relatively unexplored new scenario it is. The project consisted of three main parts: Two VHDL-based systems and one short experiment on the haptic perception. Both VHDL systems are based on a Cognitive Sensorimotor Loop (CSL) which is a control loop designed by the NRL and mainly developed by Dr. Prof. Hild. The CSL is a control loop whose main characteristic is the fact that it does not use any external sensor to measure the speed or position of the motor but the motor itself. The motor always generates a voltage that is proportional to its angular speed so it does not need calibration. This method is energy efficient and simplifies control loops in complex systems. The first system, named CSL Stay In Touch (SIT), consists in a one DC motor system controller by a FPGA Board (Zynq ZYBO 7000) whose aim is to keep contact with any external object that touches its Sensing Platform in both directions. Apart from the main behavior, three features (Search Mode, Inertia Mode and Return Mode) have been designed to enhance the haptic interaction experience. Additionally, a VGA-Screen is also controlled by the FPGA Board for the monitoring of the whole system. This system has been completely developed, tested and improved; analyzing its timing and consumption properties. The second system, named CSL Fingerlike Mechanism (FM), consists in a fingerlike mechanical system controlled by two DC motors (Each controlling one part of the finger). The behavior is similar to the first system but in a more complex structure. This system was optional and not part of the original objectives of the thesis and it could not be properly finished and tested due to the lack of time. The haptic perception experiment was an experiment conducted to have an insight into the complexity of human haptic perception in order to implement this knowledge into technological applications. The experiment consisted in testing the capability of the subjects to recognize different objects and shapes while being blindfolded and with their ears covered. Two groups were done, one had full haptic perception while the other had to explore the environment with a plastic piece attached to their finger to create a haptic handicap. The conclusion of the thesis was that a haptic system based only on a CSL-based system is not enough to retrieve valuable information from the environment and that other sensors are needed (temperature, pressure, etc.) but that a CSL-based system is very useful to control the force applied by the system to interact with haptic sensible surfaces such as skin or tactile screens. RESUMEN. Este documento es un resumen del proyecto fin de grado titulado “VHDL-Based System Design of a Cognitive Sensorimotor Loop (CSL) for Haptic Human-Machine Interaction (HMI)” escrito por Pablo de Miguel, estudiante de Ingeniería Electrónica de Comunicaciones en la Universidad Politécnica de Madrid (UPM Madrid, España) durante un programa de intercambio Erasmus+ en la Beuth Hochschule für Technik (BHT Berlin, Alemania). El tutor de este proyecto ha sido Dr. Prof. Hild. Este proyecto se ha desarrollado dentro del Neurorobotics Research Laboratory (NRL) en estrecha colaboración con Benjamin Panreck (un miembro del NRL) y con Pablo Lezcano (Otro estudiante de intercambio de la UPM). Para una comprensión completa del trabajo es necesaria una lectura detenida de todo el documento y el visionado de los videos y análisis del diseño VHDL incluidos en el CD adjunto. En el creciente sector de la automatización, una gran cantidad de esfuerzo está dedicada a mejorar, adaptar y diseñar controladores de motor para un gran rango de aplicaciones. En el campo específico de la robótica u otra maquinaria diseñada para interactuar con los humanos o con su entorno, nuevas necesidades y soluciones tecnológicas se siguen desarrollado debido al relativamente inexplorado y nuevo escenario que supone. El proyecto consta de tres partes principales: Dos sistemas basados en VHDL y un pequeño experimento sobre la percepción háptica. Ambos sistemas VHDL están basados en el Cognitive Sesnorimotor Loop (CSL) que es un lazo de control creado por el NRL y cuyo desarrollador principal ha sido Dr. Prof. Hild. El CSL es un lazo de control cuya principal característica es la ausencia de sensores externos para medir la velocidad o la posición del motor, usando el propio motor como sensor. El motor siempre genera un voltaje proporcional a su velocidad angular de modo que no es necesaria calibración. Este método es eficiente en términos energéticos y simplifica los lazos de control en sistemas complejos. El primer sistema, llamado CSL Stay In Touch (SIT), consiste en un sistema formado por un motor DC controlado por una FPGA Board (Zynq ZYBO 7000) cuyo objetivo es mantener contacto con cualquier objeto externo que toque su plataforma sensible en ambas direcciones. Aparte del funcionamiento básico, tres modos (Search Mode, Inertia Mode y Return Mode) han sido diseñados para mejorar la interacción. Adicionalmente, se ha diseñado el control a través de la FPGA Board de una pantalla VGA para la monitorización de todo el sistema. El sistema ha sido totalmente desarrollado, testeado y mejorado; analizando su propiedades de timing y consumo energético. El segundo sistema, llamado CSL Fingerlike Mechanism (FM), consiste en un mecanismo similar a un dedo controlado por dos motores DC (Cada uno controlando una falange). Su comportamiento es similar al del primer sistema pero con una estructura más compleja. Este sistema no formaba parte de los objetivos iniciales del proyecto y por lo tanto era opcional. No pudo ser plenamente desarrollado debido a la falta de tiempo. El experimento de percepción háptica fue diseñado para profundizar en la percepción háptica humana con el objetivo de aplicar este conocimiento en aplicaciones tecnológicas. El experimento consistía en testear la capacidad de los sujetos para reconocer diferentes objetos, formas y texturas en condiciones de privación del sentido del oído y la vista. Se crearon dos grupos, en uno los sujetos tenían plena percepción háptica mientras que en el otro debían interactuar con los objetos a través de una pieza de plástico para generar un hándicap háptico. La conclusión del proyecto fue que un sistema háptico basado solo en sistemas CSL no es suficiente para recopilar información valiosa del entorno y que debe hacer uso de otros sensores (temperatura, presión, etc.). En cambio, un sistema basado en CSL es idóneo para el control de la fuerza aplicada por el sistema durante la interacción con superficies hápticas sensibles tales como la piel o pantallas táctiles.

Crystal structure of a thermostable type B DNA polymerase from Thermococcus gorgonarius

Most known archaeal DNA polymerases belong to the type B family, which also includes the DNA replication polymerases of eukaryotes, but maintain high fidelity at extreme conditions. We describe here the 2.5 Å resolution crystal structure of a DNA polymerase from the Archaea Thermococcus gorgonarius and identify structural features of the fold and the active site that are likely responsible for its thermostable function. Comparison with the mesophilic B type DNA polymerase gp43 of the bacteriophage RB69 highlights thermophilic adaptations, which include the presence of two disulfide bonds and an enhanced electrostatic complementarity at the DNA–protein interface. In contrast to gp43, several loops in the exonuclease and thumb domains are more closely packed; this apparently blocks primer binding to the exonuclease active site. A physiological role of this “closed” conformation is unknown but may represent a polymerase mode, in contrast to an editing mode with an open exonuclease site. This archaeal B DNA polymerase structure provides a starting point for structure-based design of polymerases or ligands with applications in biotechnology and the development of antiviral or anticancer agents.

Crystal structure of the HLA-Cw3 allotype-specific killer cell inhibitory receptor KIR2DL2

Killer cell inhibitory receptors (KIR) protect class I HLAs expressing target cells from natural killer (NK) cell-mediated lysis. To understand the molecular basis of this receptor-ligand recognition, we have crystallized the extracellular ligand-binding domains of KIR2DL2, a member of the Ig superfamily receptors that recognize HLA-Cw1, 3, 7, and 8 allotypes. The structure was determined in two different crystal forms, an orthorhombic P212121 and a trigonal P3221 space group, to resolutions of 3.0 and 2.9 Å, respectively. The overall fold of this structure, like KIR2DL1, exhibits K-type Ig topology with cis-proline residues in both domains that define β-strand switching, which sets KIR apart from the C2-type hematopoietic growth hormone receptor fold. The hinge angle of KIR2DL2 is approximately 80°, 14° larger than that observed in KIR2DL1 despite the existence of conserved hydrophobic residues near the hinge region. There is also a 5° difference in the observed hinge angles in two crystal forms of 2DL2, suggesting that the interdomain hinge angle is not fixed. The putative ligand-binding site is formed by residues from several variable loops with charge distribution apparently complementary to that of HLA-C. The packing of the receptors in the orthorhombic crystal form offers an intriguing model for receptor aggregation on the cell surface.

A dimeric crystal structure for the N-terminal two domains of intercellular adhesion molecule-1

The 3.0-Å structure of a 190-residue fragment of intercellular adhesion molecule-1 (ICAM-1, CD54) reveals two tandem Ig-superfamily (IgSF) domains. Each of two independent molecules dimerizes identically with a symmetry-related molecule over a hydrophobic interface on the BED sheet of domain 1, in agreement with dimerization of ICAM-1 on the cell surface. The residues that bind to the integrin LFA-1 are well oriented for bivalent binding in the dimer, with the critical Glu-34 residues pointing away from each other on the periphery. Residues that bind to rhinovirus are in the flexible BC and FG loops at the tip of domain 1, and these and the upper half of domain 1 are well exposed in the dimer for docking to virus. By contrast, a residue important for binding to Plasmodium falciparum-infected erythrocytes is in the dimer interface. The presence of A′ strands in both domains 1 and 2, conserved hydrogen bonds at domain junctions, and elaborate hydrogen bond networks around the key integrin binding residues in domain 1 make these domains suited to resist tensile forces during adhesive interactions. A subdivision of the intermediate (I) set of IgSF domains is proposed in which domain 1 of ICAM-1 and previously described I set domains belong to the I1 set and domain 2 of ICAM-1, ICAM-2, and vascular cell adhesion molecule-1 belong to the I2 set.

The structure of the two amino-terminal domains of human ICAM-1 suggests how it functions as a rhinovirus receptor and as an LFA-1 integrin ligand

The normal function of human intercellular adhesion molecule-1 (ICAM-1) is to provide adhesion between endothelial cells and leukocytes after injury or stress. ICAM-1 binds to leukocyte function-associated antigen (LFA-1) or macrophage-1 antigen (Mac-1). However, ICAM-1 is also used as a receptor by the major group of human rhinoviruses and is a catalyst for the subsequent viral uncoating during cell entry. The three-dimensional atomic structure of the two amino-terminal domains (D1 and D2) of ICAM-1 has been determined to 2.2-Å resolution and fitted into a cryoelectron microscopy reconstruction of a rhinovirus–ICAM-1 complex. Rhinovirus attachment is confined to the BC, CD, DE, and FG loops of the amino-terminal Ig-like domain (D1) at the end distal to the cellular membrane. The loops are considerably different in structure to those of human ICAM-2 or murine ICAM-1, which do not bind rhinoviruses. There are extensive charge interactions between ICAM-1 and human rhinoviruses, which are mostly conserved in both major and minor receptor groups of rhinoviruses. The interaction of ICAMs with LFA-1 is known to be mediated by a divalent cation bound to the insertion (I)-domain on the α chain of LFA-1 and the carboxyl group of a conserved glutamic acid residue on ICAMs. Domain D1 has been docked with the known structure of the I-domain. The resultant model is consistent with mutational data and provides a structural framework for the adhesion between these molecules.

Crystal structure of chemically synthesized [N33A] stromal cell-derived factor 1α, a potent ligand for the HIV-1 “fusin” coreceptor

Stromal cell-derived factor-1α (SDF-1α ) is a member of the chemokine superfamily and functions as a growth factor and chemoattractant through activation of CXCR4/LESTR/Fusin, a G protein-coupled receptor. This receptor also functions as a coreceptor for T-tropic syncytium-inducing strains of HIV-1. SDF-1α antagonizes infectivity of these strains by competing with gp120 for binding to the receptor. The crystal structure of a variant SDF-1α ([N33A]SDF-1α ) prepared by total chemical synthesis has been refined to 2.2-Å resolution. Although SDF-1α adopts a typical chemokine β-β-β-α topology, the packing of the α-helix against the β-sheet is strikingly different. Comparison of SDF-1α with other chemokine structures confirms the hypothesis that SDF-1α may be either an ancestral protein from which all other chemokines evolved or the chemokine that is the least divergent from a primordial chemokine. The structure of SDF-1α reveals a positively charged surface ideal for binding to the negatively charged extracellular loops of the CXCR4 HIV-1 coreceptor. This ionic complementarity is likely to promote the interaction of the mobile N-terminal segment of SDF-1α with interhelical sites of the receptor, resulting in a biological response.

DsrA RNA regulates translation of RpoS message by an anti-antisense mechanism, independent of its action as an antisilencer of transcription

DsrA RNA regulates both transcription, by overcoming transcriptional silencing by the nucleoid-associated H-NS protein, and translation, by promoting efficient translation of the stress σ factor, RpoS. These two activities of DsrA can be separated by mutation: the first of three stem-loops of the 85 nucleotide RNA is necessary for RpoS translation but not for anti-H-NS action, while the second stem-loop is essential for antisilencing and less critical for RpoS translation. The third stem-loop, which behaves as a transcription terminator, can be substituted by the trp transcription terminator without loss of either DsrA function. The sequence of the first stem-loop of DsrA is complementary with the upstream leader portion of rpoS messenger RNA, suggesting that pairing of DsrA with the rpoS message might be important for translational regulation. Mutations in the Rpos leader and compensating mutations in DsrA confirm that this predicted pairing is necessary for DsrA stimulation of RpoS translation. We propose that DsrA pairing stimulates RpoS translation by acting as an anti-antisense RNA, freeing the translation initiation region from the cis-acting antisense RNA and allowing increased translation.

A structural view of evolutionary divergence

Two directed evolution experiments on p-nitrobenzyl esterase yielded one enzyme with a 100-fold increased activity in aqueous-organic solvents and another with a 17°C increase in thermostability. Structures of the wild type and its organophilic and thermophilic counterparts are presented at resolutions of 1.5 Å, 1.6 Å, and 2.0 Å, respectively. These structures identify groups of interacting mutations and demonstrate how directed evolution can traverse complex fitness landscapes. Early-generation mutations stabilize flexible loops not visible in the wild-type structure and set the stage for further beneficial mutations in later generations. The mutations exert their influence on the esterase structure over large distances, in a manner that would be difficult to predict. The loops with the largest structural changes generally are not the sites of mutations. Similarly, none of the seven amino acid substitutions in the organophile are in the active site, even though the enzyme experiences significant changes in the organization of this site. In addition to reduction of surface loop flexibility, thermostability in the evolved esterase results from altered core packing, helix stabilization, and the acquisition of surface salt bridges, in agreement with other comparative studies of mesophilic and thermophilic enzymes. Crystallographic analysis of the wild type and its evolved counterparts reveals networks of mutations that collectively reorganize the active site. Interestingly, the changes that led to diversity within the α/β hydrolase enzyme family and the reorganization seen in this study result from main-chain movements.

The structure of the acto-myosin subfragment 1 complex: Results of searches using data from electron microscopy and x-ray crystallography

Surmises of how myosin subfragment 1 (S1) interacts with actin filaments in muscle contraction rest upon knowing the relative arrangement of the two proteins. Although there exist crystallographic structures for both S1 and actin, as well as electron microscopy data for the acto–S1 complex (AS1), modeling of this arrangement has so far only been done “by eye.” Here we report fitted AS1 structures obtained using a quantitative method that is both more objective and makes more complete use of the data. Using undistorted crystallographic results, the best-fit AS1 structure shows significant differences from that obtained by visual fitting. The best fit is produced using the F-actin model of Holmes et al. [Holmes, K. C., Popp, D., Gebhard, W. & Kabsch, W. (1990) Nature (London) 347, 44–49]. S1 residues at the AS1 interface are now found at a higher radius as well as being translated axially and rotated azimuthally. Fits using S1 plus loops missing from the crystal structure were achieved using a homology search method to predict loop structures. These improved fits favor an arrangement in which the loop at the 50- to 20-kDa domain junction of S1 is located near the N terminus of actin. Rigid-body movements of the lower 50-kDa domain, which further improve the fit, produce closure of the large 50-kDa domain cleft and bring conserved residues in the lower 50-kDa domain into an apparently appropriate orientation for close interaction with actin. This finding supports the idea that binding of ATP to AS1 at the end of the ATPase cycle disrupts the actin binding site by changing the conformation of the 50-kDa cleft of S1.

Role of Saccharomyces cerevisiae Msh2 and Msh3 repair proteins in double-strand break-induced recombination

When gene conversion is initiated by a double-strand break (DSB), any nonhomologous DNA that may be present at the ends must be removed before new DNA synthesis can be initiated. In Saccharomyces cerevisiae, removal of nonhomologous ends depends not only on the nucleotide excision repair endonuclease Rad1/Rad10 but also on Msh2 and Msh3, two proteins that are required to correct mismatched bp. These proteins have no effect when DSB ends are homologous to the donor, either in the kinetics of recombination or in the proportion of gene conversions associated with crossing-over. A second DSB repair pathway, single-strand annealing also requires Rad1/Rad10 and Msh2/Msh3, but reveals a difference in their roles. When the flanking homologous regions that anneal are 205 bp, the requirement for Msh2/Msh3 is as great as for Rad1/Rad10; but when the annealing partners are 1,170 bp, Msh2/Msh3 have little effect, while Rad1/Rad10 are still required. Mismatch repair proteins Msh6, Pms1, and Mlh1 are not required. We suggest Msh2 and Msh3 recognize not only heteroduplex loops and mismatched bp, but also branched DNA structures with a free 3′ tail.