PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 6520146

Rapid subgraph search using parallelism.

W T Wipke·D Rogers
View original source ↗Export metadata ↓

Abstract

A new parallel processing algorithm is reported for subgraph matching. Parallelism is achieved for the first time within the process of node-by-node matching of two individual graphs. A SIMULA program is described for simulating this parallel subgraph search algorithm. Simulation results from a series of chemical substructure search problems show an average utilization of 84% on a 25-processor machine and up to a 24-fold speed enhancement over a single processor. Potential applications include starting material selections for synthesis as well as general substructure search problems.

Explore related subjects

Chemical PhenomenaChemistryData DisplayOnline SystemsTime FactorsJournal ArticleResearch Support, Non-U.S. Gov'tResearch Support, U.S. Gov't, P.H.S.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

W T Wipke, D Rogers. 1984. Rapid subgraph search using parallelism.. https://doi.org/10.1021/ci00044a012

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed1998

Extracting contact energies from protein structures: a study using a simplified model.

In this study, we exploited an elementary 2-dimensional square lattice model of HP polymers to test the premise of extracting contact energies from protein structures. Given a set of prespecified energies for H-H, H-P, and P-P contacts, all possible sequences of various lengths were exhaustively enumerated to find sequences that have unique lowest-energy conformations. The lowest-energy structures (or native structures) of such (native) sequences were used to extract contact energies using the Miyazawa-Jernigan procedure and here-defined reference state. The relative magnitudes of the original energies were restored reasonably well, but the extracted contact energies were independent of the absolute magnitudes of the initial energies. We turned to a more detailed characterization of the energy landscapes of the native sequences in light of a new theoretical framework on protein folding. Foldability of such sequences imposes two limits on the absolute value of the prespecified energies: a lower bound entailed by the minimum requirement for thermodynamic stability and an upper bound associated with the entrapment of the chain to local minima. We found that these two limits confine the prespecified energy values to a rather narrow range which, surprisingly, also contains the extracted energies in all the cases examined. These results indicate that the quasi-chemical approximation can be used to connect quantitatively the occurrence of various residue-residue contacts in an ensemble of native structures with the energies of the contacts. More importantly, they suggest that the extracted contact energies do contain information on structural stability and can be used to estimate actual structural energetics. This study also encourages the use of structure-derived contact energies in threading. The finding that there is a rather narrow range of energies that are optimal for folding a sequence also cautions the use of arbitrary energy Hamiltonion in minimal folding models.

Chemical Phenomena↗
PubMed1998

Conduction-band-edge ionization thresholds of DNA components in aqueous solution.

Numerous investigations have focused on DNA damage induced by ionizing radiation; however, photoionization threshold energies of nucleic acid components in aqueous solution are not known. Herein, data from gas-phase photoelectron experiments have been combined with results from self-consistent field and post-self-consistent field molecular orbital calculations and with theoretical Gibbs free energies of hydration to describe aqueous ionization energies of 2'-deoxythymidine 5'-phosphate (5'-dTMP-) and 2'-deoxycytidine 5'-phosphate (5'-dCMP-). For the test molecules, indole and tryptophan, this approach yields aqueous ionization energies (4.46 and 4.58 eV, respectively) in agreement with experimental values (4. 35 and 4.45 eV). When uridine and 2'-deoxythymidine ionization energies are evaluated, the results agree with recent data from 193-nm laser measurements indicating that uridine ionization occurs via a one-photon event. For 5'-dCMP- and 5'-dTMP-, a comparison of aqueous ionization energies with gas-phase ionization potentials (IPs) indicates that hydration alters the relative energies of ionization events. In the gas phase, phosphate vertical IPs are approximately 1.3 eV smaller than base IPs. In aqueous solution, the base and phosphate ionization energies are more similar, and only differ by approximately 0.5 eV. For 5'-dCMP- and 5'-dTMP-, the increased favorableness of base ionization, which accompanies hydration, is consistent with experimental data indicating that, at 77 K in aqueous perchlorate glasses, the primary photoionization pathway involves base ionization followed by deprotonation.

Chemical Phenomena↗
PubMed1998

Asymmetric cyanomet valency hybrid hemoglobin, (alpha+CN-beta+CN-)(alpha beta): the issue of valency exchange.

A new framework for hemoglobin cooperativity was proposed by Ackers and colleagues on the basis of the hyper thermodynamic stability and deoxy (T) quaternary structure of one of diliganded deoxy-cyanomet hybrid hemoglobins, (alpha+CN-beta+CN-)(alpha beta), studied by hybridization of the equimolar mixture of deoxyhemoglobin and cyanomethemoglobin through a long (70-100 h) dimer exchange reaction [Daugherty et al. (1991) Proc. Natl. Acad. Sci. U.S.A. 88, 1110-1114]. Recently, we reported that the published hyperstability of (alpha+CN-beta+CN-)(alpha beta) is incorrect due to the occurrence of valency exchange between the heme sites of both parental hemoglobins during the long deoxy incubation [Shibayama et al. (1997) Biochemistry 36, 4375-4381]. We also noted a difficulty in maintaining both anaerobicity and excess free cyanide of the sample during the long incubation, which led to formation of cyanide-unbound aqometheme in the original deoxyhemoglobin resulting from the electron transfer to cyanometheme. This paper is a response to a recent argument against our work [Ackers et al. (1997) Biochemistry 36, 10822-10829]. Ackers et al. have claimed that no appreciable formation of aqomethemoglobin with their methods ensures their sample integrity, based on a supposition that our observed valency exchange may have occurred via aqometheme. In this paper, however, we demonstrate that appreciable (>27%) valency exchange really occurs between deoxy and cyanometheme sites during 72 h incubation under conditions where both anaerobicity and excess free cyanide of the sample solution are maintained by a continuous flow of humidified N2 with HCN. This confirms our view that previous experimental data on (alpha+CN-beta+CN-)(alpha beta) obtained by the long incubations should be subject to reexamination while our earlier estimation of a lower limit of free energy of (alpha+CN-beta+CN-)(alpha beta) (i.e., >/= -10.1 kcal/mol) by a rapid method (35 min) is still valid. We also suggest a possibility that the T quaternary structure of (alpha+CN-beta+CN-)(alpha beta) assigned by Ackers and colleagues using the long incubations is an artifact arising from the valency exchange. These results suggest that the putative mechanistic picture for hemoglobin cooperativity inferred from studies on deoxy-cyanomet hybrids is without foundation.

Chemical Phenomena↗