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.

Comparison of structures and energies of CH52+• with CH4+• and their possible role in superacidic methane activation

Contrary to previous theoretical studies at the UHF/6-31G* level, the methonium radical dication CH52+ is not a Cs symmetrical structure with a 2e—3c bond but a C2v symmetrical structure 1 with two 2e—3c bonds (at the UHF/6-31G**, UMP2/6-31G**, and UQCISD(T)/6-311G** levels). The Cs symmetrical structure is not even a minimum at the higher level of calculations. The four hydrogen atoms in 1 are bonded to the carbon atom by two 2e—3c bonds and the fifth hydrogen atom by a 2e—2c bond. The unpaired electron of 1 is located in a formal p-orbital (of the sp2-hybridized carbon atom) perpendicular to the plane of the molecule. Hydrogen scrambling in 1 is however extremely facile, as is in other C1 cations. It is found that the protonation of methane to CH5+ decreases the energy for subsequent homolytic cleavage resulting in the exothermic (24.1 kcal/mol) formation of CH4+•. Subsequent reaction with neutral methane while reforming CH5+ gives the methyl radical enabling reaction with excess methane to ethane and H2. The overall reaction is endothermic by 11.4 kcal/mol, but offers under conditions of oxidative removal of H2 an alternative to the more energetic carbocationic conversion of methane.

Inhibitory sites in enzymes: Zinc removal and reactivation by thionein

Thionein (T) has not been isolated previously from biological material. However, it is generated transiently in situ by removal of zinc from metallothionein under oxidoreductive conditions, particularly in the presence of selenium compounds. T very rapidly activates a group of enzymes in which zinc is bound at an inhibitory site. The reaction is selective, as is apparent from the fact that T does not remove zinc from the catalytic sites of zinc metalloenzymes. T instantaneously reverses the zinc inhibition with a stoichiometry commensurate with its known capacity to bind seven zinc atoms in the form of clusters in metallothionein. The zinc inhibition is much more pronounced than was previously reported, with dissociation constants in the low nanomolar range. Thus, T is an effective, endogenous chelating agent, suggesting the existence of a hitherto unknown and unrecognized biological regulatory system. T removes the metal from an inhibitory zinc-specific enzymatic site with a resultant marked increase of activity. The potential significance of this system is supported by the demonstration of its operations in enzymes involved in glycolysis and signal transduction.

Dynamic expression of multiple scavenger receptor cysteine-rich genes in coelomocytes of the purple sea urchin

Coelomocytes, the heterogeneous population of sea urchin putative immune cells, were found to express a complex set of transcripts featuring scavenger receptor cysteine-rich (SRCR) repeats. SRCR domains define a metazoan superfamily of proteins, many of which are implicated in development and regulation of the immune system of vertebrates. Coelomocytes transcribe multiple SRCR genes from among a multigene family encoding an estimated number of 1,200 SRCR domains in specific patterns particular to each individual. Transcription levels for given SRCR genes may range from pronounced to undetectable, yet all tested animals harbor the genomic loci encoding these genes. Analysis of several SRCR genes revealed multiple loci corresponding to each type. In the case of one SRCR type, a cluster of at least three genes was detected within a 133-kb bacterial artificial chromosome insert, and conserved as well as unique regions were identified in sequences of three genomic clones derived from a single animal. Array hybridizations with repeated samples of coelomocyte messages revealed substantial alterations in levels of expression of many SRCR genes, with fluctuations of up to 10-fold in 1 week and up to 30-fold over a period of 3 months. This report is the first demonstration of genomic and transcriptional complexity in molecules expressed by invertebrate coelomocytes. The mechanisms controlling SRCR gene expression and the functional significance of this dynamic system await elucidation.

The importance of reactant positioning in enzyme catalysis: A hybrid quantum mechanics/molecular mechanics study of a haloalkane dehalogenase

Hybrid quantum mechanics/molecular mechanics calculations using Austin Model 1 system-specific parameters were performed to study the SN2 displacement reaction of chloride from 1,2-dichloroethane (DCE) by nucleophilic attack of the carboxylate of acetate in the gas phase and by Asp-124 in the active site of haloalkane dehalogenase from Xanthobacter autotrophicus GJ10. The activation barrier for nucleophilic attack of acetate on DCE depends greatly on the reactants having a geometry resembling that in the enzyme or an optimized gas-phase structure. It was found in the gas-phase calculations that the activation barrier is 9 kcal/mol lower when dihedral constraints are used to restrict the carboxylate nucleophile geometry to that in the enzyme relative to the geometries for the reactants without dihedral constraints. The calculated quantum mechanics/molecular mechanics activation barriers for the enzymatic reaction are 16.2 and 19.4 kcal/mol when the geometry of the reactants is in a near attack conformer from molecular dynamics and in a conformer similar to the crystal structure (DCE is gauche), respectively. This haloalkane dehalogenase lowers the activation barrier for dehalogenation of DCE by 2–4 kcal/mol relative to the single point energies of the enzyme's quantum mechanics atoms in the gas phase. SN2 displacements of this sort in water are infinitely slower than in the gas phase. The modest lowering of the activation barrier by the enzyme relative to the reaction in the gas phase is consistent with mutation experiments.

Packing at the protein-water interface.

We have determined the packing efficiency at the protein-water interface by calculating the volumes of atoms on the protein surface and nearby water molecules in 22 crystal structures. We find that an atom on the protein surface occupies, on average, a volume approximately 7% larger than an atom of equivalent chemical type in the protein core. In these calculations, larger volumes result from voids between atoms and thus imply a looser or less efficient packing. We further find that the volumes of individual atoms are not related to their chemical type but rather to their structural location. More exposed atoms have larger volumes. Moreover, the packing around atoms in locally concave, grooved regions of protein surfaces is looser than that around atoms in locally convex, ridge regions. This as a direct manifestation of surface curvature-dependent hydration. The net volume increase for atoms on the protein surface is compensated by volume decreases in water molecules near the surface. These waters occupy volumes smaller than those in the bulk solvent by up to 20%; the precise amount of this decrease is directly related to the extent of contact with the protein.

Imaging of single molecule diffusion.

In recent years observations at the level of individual atoms and molecules became possible by microscopy and spectroscopy. Imaging of single fluorescence molecules has been achieved but has so far been restricted to molecules in the immobile state. Here we provide methodology for visualization of the motion of individual fluorescent molecules. It is applied to imaging of the diffusional path of single molecules in a phospholipid membrane by using phospholipids carrying one rhodamine dye molecule. For this methodology, fluorescence microscopy was carried to a sensitivity so that single fluorescent molecules illuminated for only 5 ms were resolvable at a signal/noise ratio of 28. Repeated illuminations permitted direct observation of the diffusional motion of individual molecules with a positional accuracy of 30 nm. Such capability has fascinating potentials in bioscience--for example, to correlate biological functions of cell membranes with movements, spatial organization, and stoichiometries of individual components.

EChO. Exoplanet characterisation observatory

A dedicated mission to investigate exoplanetary atmospheres represents a major milestone in our quest to understand our place in the universe by placing our Solar System in context and by addressing the suitability of planets for the presence of life. EChO—the Exoplanet Characterisation Observatory—is a mission concept specifically geared for this purpose. EChO will provide simultaneous, multi-wavelength spectroscopic observations on a stable platform that will allow very long exposures. The use of passive cooling, few moving parts and well established technology gives a low-risk and potentially long-lived mission. EChO will build on observations by Hubble, Spitzer and ground-based telescopes, which discovered the first molecules and atoms in exoplanetary atmospheres. However, EChO’s configuration and specifications are designed to study a number of systems in a consistent manner that will eliminate the ambiguities affecting prior observations. EChO will simultaneously observe a broad enough spectral region—from the visible to the mid-infrared—to constrain from one single spectrum the temperature structure of the atmosphere, the abundances of the major carbon and oxygen bearing species, the expected photochemically-produced species and magnetospheric signatures. The spectral range and resolution are tailored to separate bands belonging to up to 30 molecules and retrieve the composition and temperature structure of planetary atmospheres. The target list for EChO includes planets ranging from Jupiter-sized with equilibrium temperatures T_ eq up to 2,000 K, to those of a few Earth masses, with T _eq \u223c 300 K. The list will include planets with no Solar System analog, such as the recently discovered planets GJ1214b, whose density lies between that of terrestrial and gaseous planets, or the rocky-iron planet 55 Cnc e, with day-side temperature close to 3,000 K. As the number of detected exoplanets is growing rapidly each year, and the mass and radius of those detected steadily decreases, the target list will be constantly adjusted to include the most interesting systems. We have baselined a dispersive spectrograph design covering continuously the 0.4–16 μm spectral range in 6 channels (1 in the visible, 5 in the InfraRed), which allows the spectral resolution to be adapted from several tens to several hundreds, depending on the target brightness. The instrument will be mounted behind a 1.5 m class telescope, passively cooled to 50 K, with the instrument structure and optics passively cooled to \u223c45 K. EChO will be placed in a grand halo orbit around L2. This orbit, in combination with an optimised thermal shield design, provides a highly stable thermal environment and a high degree of visibility of the sky to observe repeatedly several tens of targets over the year. Both the baseline and alternative designs have been evaluated and no critical items with Technology Readiness Level (TRL) less than 4–5 have been identified. We have also undertaken a first-order cost and development plan analysis and find that EChO is easily compatible with the ESA M-class mission framework.

Calibration of the length of a chain of single gold atoms

Using a scanning tunnelling microscope or mechanically controllable break junction it has been shown that it is possible to control the formation of a wire made of single gold atoms. In these experiments an interatomic distance between atoms in the chain of ∼3.6 Å was reported which is not consistent with recent theoretical calculations. Here, using precise calibration procedures for both techniques, we measure the length of the atomic chains. Based on the distance between the peaks observed in the chain length histogram we find the mean value of the interatomic distance before chain rupture to be 2.5±0.2 Å. This value agrees with the theoretical calculations for the bond length. The discrepancy with the previous experimental measurements was due to the presence of He gas, that was used to promote the thermal contact, and which affects the value of the work function that is commonly used to calibrate distances in scanning tunnelling microscopy and mechanically controllable break junctions at low temperatures.

Onset of energy dissipation in ballistic atomic wires

Electronic transport at finite voltages in free-standing gold atomic chains of up to seven atoms in length is studied at low temperatures using a scanning tunneling microscope. The conductance vs voltage curves show that transport in these single-mode ballistic atomic wires is nondissipative up to a finite voltage threshold of the order of several mV. The onset of dissipation and resistance within the wire corresponds to the excitation of the atomic vibrations by the electrons traversing the wire and is very sensitive to strain.

Cotunneling theory of atomic spin inelastic electron tunneling spectroscopy

We propose cotunneling as the microscopic mechanism that makes possible inelastic electron tunneling spectroscopy of magnetic atoms in surfaces for a wide range of systems, including single magnetic adatoms, molecules, and molecular stacks. We describe electronic transport between the scanning tip and the conducting surface through the magnetic system (MS) with a generalized Anderson model, without making use of effective spin models. Transport and spin dynamics are described with an effective cotunneling Hamiltonian in which the correlations in the magnetic system are calculated exactly and the coupling to the electrodes is included up to second order in the tip MS and MS substrate. In the adequate limit our approach is equivalent to the phenomenological Kondo exchange model that successfully describes the experiments. We apply our method to study in detail inelastic transport in two systems, stacks of cobalt phthalocyanines and a single Mn atom on Cu2N. Our method accounts for both the large contribution of the inelastic spin exchange events to the conductance and the observed conductance asymmetry.

Interplay between sublattice and spin symmetry breaking in graphene

We study the effect of sublattice symmetry breaking on the electronic, magnetic, and transport properties of two-dimensional graphene as well as zigzag terminated one- and zero-dimensional graphene nanostructures. The systems are described with the Hubbard model within the collinear mean field approximation. We prove that for the noninteracting bipartite lattice with an unequal number of atoms in each sublattice, in-gap states still exist in the presence of a staggered on-site potential ±Δ/2. We compute the phase diagram of both 2D and 1D graphene with zigzag edges, at half filling, defined by the normalized interaction strength U/t and Δ/t, where t is the first neighbor hopping. In the case of 2D we find that the system is always insulating, and we find the Uc(Δ) curve above which the system goes antiferromagnetic. In 1D we find that the system undergoes a phase transition from nonmagnetic insulator for Uinteredge coupling. The conduction properties of the magnetic phase depend on Δ and can be insulating, conducting, and even half-metallic, yet the total magnetic moment in the system is zero. We compute the transport properties of a heterojunction with two magnetic graphene ribbon electrodes connected to a finite length armchair ribbon and we find a strong spin filter effect.

Cleavage of the C–C Bond in the Ethanol Oxidation Reaction on Platinum. Insight from Experiments and Calculations

Using a combination of experimental and computational methods, mainly FTIR and DFT calculations, new insights are provided here in order to better understand the cleavage of the C–C bond taking place during the complete oxidation of ethanol on platinum stepped surfaces. First, new experimental results pointing out that platinum stepped surfaces having (111) terraces promote the C–C bond breaking are presented. Second, it is computationally shown that the special adsorption properties of the atoms in the step are able to promote the C–C scission, provided that no other adsorbed species are present on the step, which is in agreement with the experimental results. In comparison with the (111) terrace, the cleavage of the C–C bond on the step has a significantly lower activation energy, which would provide an explanation for the observed experimental results. Finally, reactivity differences under acidic and alkaline conditions are discussed using the new experimental and theoretical evidence.

Low generation triazine-based dendrimers-synthesis, characterzation and in vitro biological activity

In the present study, two low generation triazine-based dendrimers, G1.0(Cl)4 dendrimer and G1.5(OH)8 dendrimer, were synthesized and their cytotoxicity were tested by using the NIH 3T3 and the A2780 cell lines. In the synthesis process of the G1.0(Cl)4 dendrimer, cyanuric chloride (CAC) which has high reactivity chlorine atom was connected to the terminal of triethylene glycol (TEG) via nucleophilic substitution by controlling temperature. The prepared G1.0(Cl)4 dendrimer was purified by silica gel column chromatography. Then the four chlorine atoms in the G1.0(Cl)4 dendrimer were substituted by diethanolamine (DEA) to give dendrimer with the hydroxyl terminal group G1.5(OH)8. The starting materials, CAC, G1.0(Cl)4 dendrimer and G1.5(OH)8 dendrimer were analyzed by one-dimensional NMR, FTIR and MS techniques. The two dendrimers, G1.0(Cl)4 and G1.5(OH)8, showed perfect stability in the air environment at room temperature. However, G1.0(Cl)4 is not soluble in water while the G1.5(OH)8 dendrimer is a water soluble compound. Furthermore, cell biological evaluation at the studied concentrations showed that the CAC, as well as the prepared G1.0(Cl)4 and G1.5(OH)8 dendrimers, have no cytotoxicity towards the NIH 3T3 and A2780 cell lines.

(Table 2) Concentrations of dissolved aluminum in interstitial water from sediments of the Indian Ocean

Results are presented of application of laser stepwise photoionization of atoms in combination with thermal atomization of matter in vacuum for direct determination of aluminum dissolved in sea and interstitial waters. Dry residue from evaporation of 40 ?l sea water was atomized in a crucible at 1800°C, and aluminum atoms in the beam thus formed were energized into Rydberg state in two steps by two tunable dye laser beams; the atoms were then ionized by an electric pulse and resulting ions were recorded by secondary emission electron multiplier (ion detector). Ionic signal dependence on sample vaporization time was studied. The procedure is suggested for separating out a selective signal in a single measurement. Dissolved aluminum concentrations in interstitial waters of the Indian Ocean and in waters of the river-sea zone were determined using preliminarily plotted calibration characteristics for aluminum solutions in deionized and sea waters. The minimum detectable Al concentration in seawater was 1 ?g/l that corresponds to 40 pg of Al in a sample.