From eventual to atomic and locally atomic CC programs: A concurrent semantics

We present a concurrent semantics (i.e. a semantics where concurrency is explicitely represented) for CC programs with atomic tells. This allows to derive concurrency, dependency, and nondeterminism information for such languages. The ability to treat failure information puts CLP programs also in the range of applicability of our semantics: although such programs are not concurrent, the concurrency information derived in the semantics may be interpreted as possible parallelism, thus allowing to safely parallelize those computation steps which appear to be concurrent in the net. Dually, the dependency information may also be interpreted as necessary sequentialization, thus possibly exploiting it to schedule CC programs. The fact that the semantical structure contains dependency information suggests a new tell operation, which checks for consistency only the constraints it depends on, achieving a reasonable trade-off between efficiency and atomicity.

Impact of N on the atomic-scale Sb distribution in quaternary GaAsSbN-capped InAs quantum dots

The use of GaAsSbN capping layers on InAs/GaAs quantum dots (QDs) has recently been proposed for micro- and optoelectronic applications for their ability to independently tailor electron and hole confinement potentials. However, there is a lack of knowledge about the structural and compositional changes associated with the process of simultaneous Sb and N incorporation. In the present work, we have characterized using transmission electron microscopy techniques the effects of adding N in the GaAsSb/InAs/GaAs QD system. Firstly, strain maps of the regions away from the InAs QDs had revealed a huge reduction of the strain fields with the N incorporation but a higher inhomogeneity, which points to a composition modulation enhancement with the presence of Sb-rich and Sb-poor regions in the range of a few nanometers. On the other hand, the average strain in the QDs and surroundings is also similar in both cases. It could be explained by the accumulation of Sb above the QDs, compensating the tensile strain induced by the N incorporation together with an In-Ga intermixing inhibition. Indeed, compositional maps of column resolution from aberration-corrected Z-contrast images confirmed that the addition of N enhances the preferential deposition of Sb above the InAs QD, giving rise to an undulation of the growth front. As an outcome, the strong redshift in the photoluminescence spectrum of the GaAsSbN sample cannot be attributed only to the N-related reduction of the conduction band offset but also to an enhancement of the effect of Sb on the QD band structure.

Determination of the magnetostrictive atomic enviroments in FeCoB alloys

The atomic environments of Fe and Co involved in the magnetostriction effect in FeCoB alloys have been identified by differential extended x-ray fine structure (DiffEXAFS) spectroscopy. The study, done in amorphous and polycrystalline FeCoB films, demonstrates that the alloys are heterogeneous and that boron plays a crucial role in the origin of their magnetostrictive properties. The analysis of DiffEXAFS in the polycrystalline and amorphous alloys indicates that boron activates magnetostriction when entering as an impurity into octahedral interstitial sites of the Fe bcc lattice, causing its tetragonal distortion. Magnetostriction would be explained then by the relative change in volume when the tetragonal axis of the site is reoriented under an externally applied magnetic field. The experiment demonstrates the extreme sensitivity of DiffEXAFS to characterize magnetostrictive environments that are undetectable in their related EXAFS spectra.

Electronic structure of copper nitrides as a function of nitrogen content

he nitrogen content dependence of the electronic properties for copper nitride thin films with an atomic percentage of nitrogen ranging from 26 ± 2 to 33 ± 2 have been studied by means of optical (spectroscopic ellipsometry), thermoelectric (Seebeck), and electrical resistivity measurements. The optical spectra are consistent with direct optical transitions corresponding to the stoichiometric semiconductor Cu3N plus a free-carrier contribution, essentially independent of temperature, which can be tuned in accordance with the N-excess. Deviation of the N content from stoichiometry drives to significant decreases from − 5 to − 50 μV/K in the Seebeck coefficient and to large enhancements, from 10− 3 up to 10 Ω cm, in the electrical resistivity. Band structure and density of states calculations have been carried out on the basis of the density functional theory to account for the experimental results.

Strong Connectivity in Directed Hypergraphs and its Application to the Atomic Decomposition of Ontologies

Los hipergrafos dirigidos se han empleado en problemas relacionados con lógica proposicional, bases de datos relacionales, linguística computacional y aprendizaje automático. Los hipergrafos dirigidos han sido también utilizados como alternativa a los grafos (bipartitos) dirigidos para facilitar el estudio de las interacciones entre componentes de sistemas complejos que no pueden ser fácilmente modelados usando exclusivamente relaciones binarias. En este contexto, este tipo de representación es conocida como hiper-redes. Un hipergrafo dirigido es una generalización de un grafo dirigido especialmente adecuado para la representación de relaciones de muchos a muchos. Mientras que una arista en un grafo dirigido define una relación entre dos de sus nodos, una hiperarista en un hipergrafo dirigido define una relación entre dos conjuntos de sus nodos. La conexión fuerte es una relación de equivalencia que divide el conjunto de nodos de un hipergrafo dirigido en particiones y cada partición define una clase de equivalencia conocida como componente fuertemente conexo. El estudio de los componentes fuertemente conexos de un hipergrafo dirigido puede ayudar a conseguir una mejor comprensión de la estructura de este tipo de hipergrafos cuando su tamaño es considerable. En el caso de grafo dirigidos, existen algoritmos muy eficientes para el cálculo de los componentes fuertemente conexos en grafos de gran tamaño. Gracias a estos algoritmos, se ha podido averiguar que la estructura de la WWW tiene forma de “pajarita”, donde más del 70% del los nodos están distribuidos en tres grandes conjuntos y uno de ellos es un componente fuertemente conexo. Este tipo de estructura ha sido también observada en redes complejas en otras áreas como la biología. Estudios de naturaleza similar no han podido ser realizados en hipergrafos dirigidos porque no existe algoritmos capaces de calcular los componentes fuertemente conexos de este tipo de hipergrafos. En esta tesis doctoral, hemos investigado como calcular los componentes fuertemente conexos de un hipergrafo dirigido. En concreto, hemos desarrollado dos algoritmos para este problema y hemos determinado que son correctos y cuál es su complejidad computacional. Ambos algoritmos han sido evaluados empíricamente para comparar sus tiempos de ejecución. Para la evaluación, hemos producido una selección de hipergrafos dirigidos generados de forma aleatoria inspirados en modelos muy conocidos de grafos aleatorios como Erdos-Renyi, Newman-Watts-Strogatz and Barabasi-Albert. Varias optimizaciones para ambos algoritmos han sido implementadas y analizadas en la tesis. En concreto, colapsar los componentes fuertemente conexos del grafo dirigido que se puede construir eliminando ciertas hiperaristas complejas del hipergrafo dirigido original, mejora notablemente los tiempos de ejecucion de los algoritmos para varios de los hipergrafos utilizados en la evaluación. Aparte de los ejemplos de aplicación mencionados anteriormente, los hipergrafos dirigidos han sido también empleados en el área de representación de conocimiento. En concreto, este tipo de hipergrafos se han usado para el cálculo de módulos de ontologías. Una ontología puede ser definida como un conjunto de axiomas que especifican formalmente un conjunto de símbolos y sus relaciones, mientras que un modulo puede ser entendido como un subconjunto de axiomas de la ontología que recoge todo el conocimiento que almacena la ontología sobre un conjunto especifico de símbolos y sus relaciones. En la tesis nos hemos centrado solamente en módulos que han sido calculados usando la técnica de localidad sintáctica. Debido a que las ontologías pueden ser muy grandes, el cálculo de módulos puede facilitar las tareas de re-utilización y mantenimiento de dichas ontologías. Sin embargo, analizar todos los posibles módulos de una ontología es, en general, muy costoso porque el numero de módulos crece de forma exponencial con respecto al número de símbolos y de axiomas de la ontología. Afortunadamente, los axiomas de una ontología pueden ser divididos en particiones conocidas como átomos. Cada átomo representa un conjunto máximo de axiomas que siempre aparecen juntos en un modulo. La decomposición atómica de una ontología es definida como un grafo dirigido de tal forma que cada nodo del grafo corresponde con un átomo y cada arista define una dependencia entre una pareja de átomos. En esta tesis introducimos el concepto de“axiom dependency hypergraph” que generaliza el concepto de descomposición atómica de una ontología. Un modulo en una ontología correspondería con un componente conexo en este tipo de hipergrafos y un átomo de una ontología con un componente fuertemente conexo. Hemos adaptado la implementación de nuestros algoritmos para que funcionen también con axiom dependency hypergraphs y poder de esa forma calcular los átomos de una ontología. Para demostrar la viabilidad de esta idea, hemos incorporado nuestros algoritmos en una aplicación que hemos desarrollado para la extracción de módulos y la descomposición atómica de ontologías. A la aplicación la hemos llamado HyS y hemos estudiado sus tiempos de ejecución usando una selección de ontologías muy conocidas del área biomédica, la mayoría disponibles en el portal de Internet NCBO. Los resultados de la evaluación muestran que los tiempos de ejecución de HyS son mucho mejores que las aplicaciones más rápidas conocidas. ABSTRACT Directed hypergraphs are an intuitive modelling formalism that have been used in problems related to propositional logic, relational databases, computational linguistic and machine learning. Directed hypergraphs are also presented as an alternative to directed (bipartite) graphs to facilitate the study of the interactions between components of complex systems that cannot naturally be modelled as binary relations. In this context, they are known as hyper-networks. A directed hypergraph is a generalization of a directed graph suitable for representing many-to-many relationships. While an edge in a directed graph defines a relation between two nodes of the graph, a hyperedge in a directed hypergraph defines a relation between two sets of nodes. Strong-connectivity is an equivalence relation that induces a partition of the set of nodes of a directed hypergraph into strongly-connected components. These components can be collapsed into single nodes. As result, the size of the original hypergraph can significantly be reduced if the strongly-connected components have many nodes. This approach might contribute to better understand how the nodes of a hypergraph are connected, in particular when the hypergraphs are large. In the case of directed graphs, there are efficient algorithms that can be used to compute the strongly-connected components of large graphs. For instance, it has been shown that the macroscopic structure of the World Wide Web can be represented as a “bow-tie” diagram where more than 70% of the nodes are distributed into three large sets and one of these sets is a large strongly-connected component. This particular structure has been also observed in complex networks in other fields such as, e.g., biology. Similar studies cannot be conducted in a directed hypergraph because there does not exist any algorithm for computing the strongly-connected components of the hypergraph. In this thesis, we investigate ways to compute the strongly-connected components of directed hypergraphs. We present two new algorithms and we show their correctness and computational complexity. One of these algorithms is inspired by Tarjan’s algorithm for directed graphs. The second algorithm follows a simple approach to compute the stronglyconnected components. This approach is based on the fact that two nodes of a graph that are strongly-connected can also reach the same nodes. In other words, the connected component of each node is the same. Both algorithms are empirically evaluated to compare their performances. To this end, we have produced a selection of random directed hypergraphs inspired by existent and well-known random graphs models like Erd˝os-Renyi and Newman-Watts-Strogatz. Besides the application examples that we mentioned earlier, directed hypergraphs have also been employed in the field of knowledge representation. In particular, they have been used to compute the modules of an ontology. An ontology is defined as a collection of axioms that provides a formal specification of a set of terms and their relationships; and a module is a subset of an ontology that completely captures the meaning of certain terms as defined in the ontology. In particular, we focus on the modules computed using the notion of syntactic locality. As ontologies can be very large, the computation of modules facilitates the reuse and maintenance of these ontologies. Analysing all modules of an ontology, however, is in general not feasible as the number of modules grows exponentially in the number of terms and axioms of the ontology. Nevertheless, the modules can succinctly be represented using the Atomic Decomposition of an ontology. Using this representation, an ontology can be partitioned into atoms, which are maximal sets of axioms that co-occur in every module. The Atomic Decomposition is then defined as a directed graph such that each node correspond to an atom and each edge represents a dependency relation between two atoms. In this thesis, we introduce the notion of an axiom dependency hypergraph which is a generalization of the atomic decomposition of an ontology. A module in the ontology corresponds to a connected component in the hypergraph, and the atoms of the ontology to the strongly-connected components. We apply our algorithms for directed hypergraphs to axiom dependency hypergraphs and in this manner, we compute the atoms of an ontology. To demonstrate the viability of this approach, we have implemented the algorithms in the application HyS which computes the modules of ontologies and calculate their atomic decomposition. In the thesis, we provide an experimental evaluation of HyS with a selection of large and prominent biomedical ontologies, most of which are available in the NCBO Bioportal. HyS outperforms state-of-the-art implementations in the tasks of extracting modules and computing the atomic decomposition of these ontologies.

Probing the Saccharomyces cerevisiae centromeric DNA (CEN DNA)–binding factor 3 (CBF3) kinetochore complex by using atomic force microscopy

Yeast centromeric DNA (CEN DNA) binding factor 3 (CBF3) is a multisubunit protein complex that binds to the essential CDEIII element in CEN DNA. The four CBF3 proteins are required for accurate chromosome segregation and are considered to be core components of the yeast kinetochore. We have examined the structure of the CBF3–CEN DNA complex by atomic force microscopy. Assembly of CBF3–CEN DNA complexes was performed by combining purified CBF3 proteins with a DNA fragment that includes the CEN region from yeast chromosome III. Atomic force microscopy images showed DNA molecules with attached globular bodies. The contour length of the DNA containing the complex is ≈9% shorter than the DNA alone, suggesting some winding of DNA within the complex. The measured location of the single binding site indicates that the complex is located asymmetrically to the right of CDEIII extending away from CDEI and CDEII, which is consistent with previous data. The CEN DNA is bent ≈55° at the site of complex formation. A significant fraction of the complexes are linked in pairs, showing three to four DNA arms, with molecular volumes approximately three times the mean volumes of two-armed complexes. These multi-armed complexes indicate that CBF3 can bind two DNA molecules together in vitro and, thus, may be involved in holding together chromatid pairs during mitosis.

The first step of aminoacylation at the atomic level in histidyl-tRNA synthetase

The crystal structure of an enzyme–substrate complex with histidyl-tRNA synthetase from Escherichia coli, ATP, and the amino acid analog histidinol is described and compared with the previously obtained enzyme–product complex with histidyl-adenylate. An active site arginine, Arg-259, unique to all histidyl-tRNA synthetases, plays the role of the catalytic magnesium ion seen in seryl-tRNA synthetase. When Arg-259 is substituted with histidine, the apparent second order rate constant (kcat/Km) for the pyrophosphate exchange reaction and the aminoacylation reaction decreases 1,000-fold and 500-fold, respectively. Crystals soaked with MnCl2 reveal the existence of two metal binding sites between β- and γ-phosphates; these sites appear to stabilize the conformation of the pyrophosphate. The use of both conserved metal ions and arginine in phosphoryl transfer provides evidence of significant early functional divergence of class II aminoacyl-tRNA synthetases.

Monitoring the assembly of Ig light-chain amyloid fibrils by atomic force microscopy

Aggregation of Ig light chains to form amyloid fibrils is a characteristic feature of light-chain amyloidosis, a light-chain deposition disease. A recombinant variable domain of the light chain SMA was used to form amyloid fibrils in vitro. Fibril formation was monitored by atomic force microscopy imaging. Single filaments 2.4 nm in diameter were predominant at early times; protofibrils 4.0 nm in diameter were predominant at intermediate times; type I and type II fibrils 8.0 nm and 6.0 nm in diameter, respectively, were predominant at the endpoints. The increase in number of fibrils correlated with increased binding of the fluorescent dye thioflavin T. The fibrils and protofibrils showed a braided structure, suggesting that their formation involves the winding of protofibrils and filaments, respectively. These observations support a model in which two filaments combine to form a protofibril, two protofibrils intertwine to form a type I fibril, and three filaments form a type II fibril.

Structural activity of a cloned potassium channel (ROMK1) monitored with the atomic force microscope: The “molecular-sandwich” technique

The atomic force microscope (AFM) was used to continuously follow height changes of individual protein molecules exposed to physiological stimuli. A AFM tip was coated with ROMK1 (a cloned renal epithelial potassium channel known to be highly pH sensitive) and lowered onto atomically flat mica surface until the protein was sandwiched between AFM tip and mica. Because the AFM tip was an integral part of a highly flexible cantilever, any structural alterations of the sandwiched molecule were transmitted to the cantilever. This resulted in a distortion of the cantilever that was monitored by means of a laser beam. With this system it was possible to resolve vertical height changes in the ROMK1 protein of ≥0.2 nm (approximately 5% of the molecule’s height) with a time resolution of ≥1 msec. When bathed in electrolyte solution that contained the catalytic subunit of protein kinase A and 0.1 mM ATP (conditions that activate the native ion channel), we found stochastically occurring height fluctuations in the ROMK1 molecule. These changes in height were pH-dependent, being greatest at pH 7.6, and lowering the pH (either by titration or by the application of CO2) reduced their magnitude. The data show that overall changes in shape of proteins occur stochastically and increase in size and frequency when the proteins are active. This AFM “molecular-sandwich” technique, called MOST, measures structural activity of proteins in real time and could prove useful for studies on the relationship between structure and function of proteins at the molecular level.

The RESID Database of protein structure modifications and the NRL-3D Sequence–Structure Database

The RESID Database is a comprehensive collection of annotations and structures for protein post-translational modifications including N-terminal, C-terminal and peptide chain cross-link modifications. The RESID Database includes systematic and frequently observed alternate names, Chemical Abstracts Service registry numbers, atomic formulas and weights, enzyme activities, taxonomic range, keywords, literature citations with database cross-references, structural diagrams and molecular models. The NRL-3D Sequence–Structure Database is derived from the three-dimensional structure of proteins deposited with the Research Collaboratory for Structural Bioinformatics Protein Data Bank. The NRL-3D Database includes standardized and frequently observed alternate names, sources, keywords, literature citations, experimental conditions and searchable sequences from model coordinates. These databases are freely accessible through the National Cancer Institute–Frederick Advanced Biomedical Computing Center at these web sites: http://www.ncifcrf.gov/RESID, http://www.ncifcrf.gov/ NRL-3D; or at these National Biomedical Research Foundation Protein Information Resource web sites: http://pir.georgetown.edu/pirwww/dbinfo/resid.html, http://pir.georgetown.edu/pirwww/dbinfo/nrl3d.html

Protein folding from a highly disordered denatured state: The folding pathway of chymotrypsin inhibitor 2 at atomic resolution

Previous experimental and theoretical studies have produced high-resolution descriptions of the native and folding transition states of chymotrypsin inhibitor 2 (CI2). In similar fashion, here we use a combination of NMR experiments and molecular dynamics simulations to examine the conformations populated by CI2 in the denatured state. The denatured state is highly unfolded, but there is some residual native helical structure along with hydrophobic clustering in the center of the chain. The lack of persistent nonnative structure in the denatured state reduces barriers that must be overcome, leading to fast folding through a nucleation–condensation mechanism. With the characterization of the denatured state, we have now completed our description of the folding/unfolding pathway of CI2 at atomic resolution.

The Three-Dimensional Structure of Aspergillus niger Pectin Lyase B at 1.7-Å Resolution1

The three-dimensional structure of Aspergillus niger pectin lyase B (PLB) has been determined by crystallographic techniques at a resolution of 1.7 Å. The model, with all 359 amino acids and 339 water molecules, refines to a final crystallographic R factor of 16.5%. The polypeptide backbone folds into a large right-handed cylinder, termed a parallel β helix. Loops of various sizes and conformations protrude from the central helix and probably confer function. The largest loop of 53 residues folds into a small domain consisting of three antiparallel β strands, one turn of an α helix, and one turn of a 310 helix. By comparison with the structure of Erwinia chrysanthemi pectate lyase C (PelC), the primary sequence alignment between the pectate and pectin lyase subfamilies has been corrected and the active site region for the pectin lyases deduced. The substrate-binding site in PLB is considerably less hydrophilic than the comparable PelC region and consists of an extensive network of highly conserved Trp and His residues. The PLB structure provides an atomic explanation for the lack of a catalytic requirement for Ca2+ in the pectin lyase family, in contrast to that found in the pectate lyase enzymes. Surprisingly, however, the PLB site analogous to the Ca2+ site in PelC is filled with a positive charge provided by a conserved Arg in the pectin lyases. The significance of the finding with regard to the enzymatic mechanism is discussed.

Zinc- and iron-rubredoxins from Clostridium pasteurianum at atomic resolution: a high-precision model of a ZnS4 coordination unit in a protein.

The Zn(Scys)4 unit is present in numerous proteins, where it assumes structural, regulatory, or catalytic roles. The same coordination is found naturally around iron in rubredoxins, several structures of which have been refined at resolutions of, or near to, 1 A. The fold of the small protein rubredoxin around its metal ion is an excellent model for many zinc finger proteins. Zn-substituted rubredoxin and its Fe-containing counterpart were both obtained as the products of the expression in Escherichia coli of the rubredoxin-encoding gene from Clostridium pasteurianum. The structures of both proteins have been refined with an anisotropic model at atomic resolution (1.1 A, R = 8.3% for Fe-rubredoxin, and 1.2 A, R = 9.6% for Zn-rubredoxin) and are very similar. The most significant differences are increased lengths of the M-S bonds in Zn-rubredoxin (average length, 2.345 A) as compared with Fe-rubredoxin (average length, 2.262 A). An increase of the CA-CB-SG-M dihedral angles involving Cys-6 and Cys-39, the first cysteines of each of the Cys-Xaa-Xaa-Cys metal binding motifs, has been observed. Another consequence of the replacement of iron by zinc is that the region around residues 36-46 undergoes larger displacements than the remainder of the polypeptide chain. Despite these changes, the main features of the FeS4 site, namely a local 2-fold symmetry and the characteristic network of N-H...S hydrogen bonds, are conserved in the ZnS4 site. The Zn-substituted rubredoxin provides the first precise structure of a Zn(Scys)4 unit in a protein. The nearly identical fold of rubredoxin around iron or zinc suggests that at least in some of the sites where the metal has mainly a structural role-e.g., zinc fingers-the choice of the relevant metal may be directed by its cellular availability and mobilization processes rather than by its chemical nature.

X-ray structure of clotting factor IXa: active site and module structure related to Xase activity and hemophilia B.

Hereditary deficiency of factor IXa (fIXa), a key enzyme in blood coagulation, causes hemophilia B, a severe X chromosome-linked bleeding disorder afflicting 1 in 30,000 males; clinical studies have identified nearly 500 deleterious variants. The x-ray structure of porcine fIXa described here shows the atomic origins of the disease, while the spatial distribution of mutation sites suggests a structural model for factor X activation by phospholipid-bound fIXa and cofactor VIIIa. The 3.0-A-resolution diffraction data clearly show the structures of the serine proteinase module and the two preceding epidermal growth factor (EGF)-like modules; the N-terminal Gla module is partially disordered. The catalytic module, with covalent inhibitor D-Phe-1I-Pro-2I-Arg-3I chloromethyl ketone, most closely resembles fXa but differs significantly at several positions. Particularly noteworthy is the strained conformation of Glu-388, a residue strictly conserved in known fIXa sequences but conserved as Gly among other trypsin-like serine proteinases. Flexibility apparent in electron density together with modeling studies suggests that this may cause incomplete active site formation, even after zymogen, and hence the low catalytic activity of fIXa. The principal axes of the oblong EGF-like domains define an angle of 110 degrees, stabilized by a strictly conserved and fIX-specific interdomain salt bridge. The disorder of the Gla module, whose hydrophobic helix is apparent in electron density, can be attributed to the absence of calcium in the crystals; we have modeled the Gla module in its calcium form by using prothrombin fragment 1. The arched module arrangement agrees with fluorescence energy transfer experiments. Most hemophilic mutation sites of surface fIX residues occur on the concave surface of the bent molecule and suggest a plausible model for the membrane-bound ternary fIXa-FVIIIa-fX complex structure: fIXa and an equivalently arranged fX arch across an underlying fVIIIa subdomain from opposite sides; the stabilizing fVIIIa interactions force the catalytic modules together, completing fIXa active site formation and catalytic enhancement.