SEARCH · PubMed Health

Results for “Parallel Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 73 records · Page 4Linked to original sources

PubMed2003

Development of a multipopulation parallel genetic algorithm for structure solution from powder diffraction data.

Previously, the genetic algorithm (GA) approach for direct-space crystal structure solution from powder diffraction data has been applied successfully in the structure determination of a range of organic molecular materials. In this article, we present a further development of our approach, namely a multipopulation parallel GA (PGA), which is shown to give rise to increased speed, efficiency, and reliability of structure solution calculations, as well as providing new opportunities for further optimizing our GA methodology. The multipopulation PGA is based on the independent evolution of different subpopulations, with occasional interaction (e.g., transfer of structures) allowed to occur between the different subpopulations. Different strategies for carrying out this interpopulation communication are considered in this article, and comparisons are made to the conventional single-population GA. The increased power offered by the PGA approach creates the opportunity for structure determination of molecular crystals of increasing complexity.

Journal Article↗

PubMed2004

A hopfield network learning method for bipartite subgraph problem.

In this paper, we present a gradient ascent learning method of the Hopfield neural network for bipartite subgraph problem. The method is intended to provide a near-optimum parallel algorithm for solving the bipartite subgraph problem. To do this we use the Hopfield neural network to get a near-maximum bipartite subgraph, and increase the energy by modifying weights in a gradient ascent direction of the energy to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm. We also test the learning method on total coloring problem. The simulation results show that our method finds optimal solution in every test graph.

Algorithms↗

PubMedDate not supplied

Parallel random tunneling algorithm for structural optimization of Lennard-Jones clusters up to N=330.

A random tunneling algorithm (RTA) is derived from the terminal repeller unconstrained subenergy tunneling (TRUST) algorithm, and the parallelization of the RTA is implemented with an island parallel paradigm. Combined with the techniques of angular moving, the parallel random tunneling algorithm (PRTA) is applied to the optimization of Lennard-Jones (LJ) atomic clusters, and all the global minima of LJ clusters with size up to 200 are successfully located. For the optimization of larger cluster, a PRTA with an improved seeding technique is developed and successfully applied to the optimization of LJ151-LJ309. Furthermore, the optimized structures of LJ309-330 with the PRTA, which have not been studied before, are also provided.

Journal Article↗

PubMed2002

Parallel Monte Carlo simulations using a residence weight algorithm.

A parallel Monte Carlo (MC) algorithm, the residence weight algorithm, is proposed. This algorithm is an extension to continuous ensembles of the residence time algorithm. The proposed algorithm consists of generating several trial MC moves in parallel, selecting one of them using appropriate relative probabilities and correcting the non-Boltzmannian sampling procedure by means of appropriate configuration weights. The corresponding parallel Boltzmannian scheme is based on a configurational-bias Monte Carlo scheme and will also be considered. The efficiency of both parallel algorithms has been compared in a case study: the slow relaxation dynamics in a model silicate. For a small number of trial moves generated in parallel, we observe that the residence weight algorithm performs less efficiently than its corresponding configurational-bias scheme by a factor of about 2. However, when the number of parallel trial moves increases and becomes larger than ten, we observe that the residence weight algorithm and the corresponding configurational-bias scheme perform with equivalent efficiencies.

Journal Article↗

PubMed1994

Dissociable mechanisms of subitizing and counting: neuropsychological evidence from simultanagnosic patients.

Do people have to count to determine visual numerosity, or is there a fast "subitizing" procedure dedicated to small sets of 1-3 items? Numerosity naming time and errors were measured in 5 simultanagnosic patients who suffered from severe difficulties in serial counting. Although these patients made close to 100% errors in quantifying sets comprising more than 3 items, they were excellent at quantifying sets of 1, 2, and sometimes 3 items. Their performances in visual search tasks suggested that they suffered from a deficit of serial visual exploration, due to a fundamental inability to use spatial tags to keep track of previously explored locations. The present data suggest that the patients' preserved subitizing abilities were based not on serial processing but rather on a parallel algorithm dedicated to small numerosities. Several ways in which this parallel subitizing algorithm might function are discussed.

Adult↗

PubMed2002

Aligning multiple protein sequences by parallel hybrid genetic algorithm.

This paper presents a parallel hybrid genetic algorithm (GA) for solving the sum-of-pairs multiple protein sequence alignment. A new chromosome representation and its corresponding genetic operators are proposed. A multi-population GENITOR-type GA is combined with local search heuristics. It is then extended to run in parallel on a multiprocessor system for speeding up. Experimental results of benchmarks from the BAliBASE show that the proposed method is superior to MSA, OMA, and SAGA methods with regard to quality of solution and running time. It can be used for finding multiple sequence alignment as well as testing cost functions.

Algorithms↗

PubMed2004

Surface tension of quantum fluids from molecular simulations.

We present the first molecular simulations of the vapor-liquid surface tension of quantum liquids. The path integral formalism of Feynman was used to account for the quantum mechanical behavior of both the liquid and the vapor. A replica-data parallel algorithm was implemented to achieve good parallel performance of the simulation code on at least 32 processors. We have computed the surface tension and the vapor-liquid phase diagram of pure hydrogen over the temperature range 18-30 K and pure deuterium from 19 to 34 K. The simulation results for surface tension and vapor-liquid orthobaric densities are in very good agreement with experimental data. We have computed the interfacial properties of hydrogen-deuterium mixtures over the entire concentration range at 20.4 and 24 K. The calculated equilibrium compositions of the mixtures are in excellent agreement with experimental data. The computed mixture surface tension shows negative deviations from ideal solution behavior, in agreement with experimental data and predictions from Prigogine's theory. The magnitude of the deviations at 20.4 K are substantially larger from simulations and from theory than from experiments. We conclude that the experimentally measured mixture surface tension values are systematically too high. Analysis of the concentration profiles in the interfacial region shows that the nonideal behavior can be described entirely by segregation of H(2) to the interface, indicating that H(2) acts as a surfactant in H(2)-D(2) mixtures.

Journal Article↗

PubMed2004

Parallel hash-based EST clustering algorithm for gene sequencing.

EST clustering is a simple, yet effective method to discover all the genes present in a variety of species. Although using ESTs is a cost-effective approach in gene discovery, the amount of data, and hence the computational resources required, make it a very challenging problem. Time and storage requirements for EST clustering problems are prohibitively expensive. Existing tools have quadratic time complexity resulting from all against all sequence comparisons. With the rapid growth of EST data we need better and faster clustering tools. In this paper, we present HECT (Hash based EST Clustering Tool), a novel time- and memory-efficient algorithm for EST clustering. We report that HECT can cluster a 10,000 Human EST dataset (which is also used in benchmarking d2_cluster), in 207 minutes on a 1 GHz Pentium III processor which is 36 times faster than the original d2_cluster algorithm. A parallel version of HECT (PECT) is also developed and used to cluster 269,035 soybean EST sequences on IA-32 Linux cluster at National Center for Supercomputing Applications at UIUC. The parallel algorithm exhibited excellent speedup over its sequential counterpart and its memory requirements are almost negligible making it suitable to run virtually on any data size. The performance of the proposed clustering algorithms is compared against other known clustering techniques and results are reported in the paper.

Algorithms↗

PubMed2002

Application of the parallel generalized projection algorithm to the control of two finite-resolution deformable mirrors for scintillation compensation.

A modification of the parallel generalized projection algorithm is presented that allows for the use of projections in a weighted norm. Convergence properties of the modified algorithm, denoted the weighted parallel generalized projection algorithm, are developed. The weighted parallel generalized projection algorithm is applied to the control of two finite-resolution deformable mirrors to compensate for both the amplitude and the phase fluctuations that result from propagation through a turbulent medium. Numerical results are shown that indicate that a two-deformable-mirror system can provide improved performance over that of a single-deformable-mirror system.

Journal Article↗

PubMed2006

Optimized and parallelized implementation of the electronegativity equalization method and the atom-bond electronegativity equalization method.

The most common way to calculate charge distribution in a molecule is ab initio quantum mechanics (QM). Some faster alternatives to QM have also been developed, the so-called "equalization methods" EEM and ABEEM, which are based on DFT. We have implemented and optimized the EEM and ABEEM methods and created the EEM SOLVER and ABEEM SOLVER programs. It has been found that the most time-consuming part of equalization methods is the reduction of the matrix belonging to the equation system generated by the method. Therefore, for both methods this part was replaced by the parallel algorithm WIRS and implemented within the PVM environment. The parallelized versions of the programs EEM SOLVER and ABEEM SOLVER showed promising results, especially on a single computer with several processors (compact PVM). The implemented programs are available through the Web page http://ncbr.chemi.muni.cz/~n19n/eem_abeem.

Journal Article↗

PubMed2003

The most efficient use of resources to identify those in need of antiretroviral treatment in Africa: empirical data from Côte d'Ivoire's Drug Access Initiative.

OBJECTIVE: To describe the cost and outcome associated with the use of CD4 cell count and viral load tests as part of screening strategies to identify persons eligible for subsidized antiretroviral therapy (ART) in Côte d'Ivoire. METHODS: Empirical data from the Drug Access Initiative in Côte d'Ivoire (DAI-CI) were used to describe the laboratory cost of patient screening using sequential clinical staging, CD4 cell count, and viral load and the proportion of screened patients identified as eligible for ART. We also estimated costs modelling a parallel screening algorithm, across a range of laboratory costs and with current international recommendations to assess treatment eligibility. Benefit was defined as being found eligible for ART. RESULTS: Of the 2138 HIV-positive, ART-naive, adults who presented to the DAI-CI between July 1998 and July 2000, median CD4 cell count was 172 x 10(6) cells/microl. DAI-CI criteria identified 2057 (96%) of these persons eligible for antiretroviral treatment. In a serial screening algorithm, 75% were eligible by CDC clinical stage B or C; 18% by CD4 cell count less than 500 x 10(6) cells/microl; and an estimated 3.9% by a viral load greater than 10 000 copies/ml. Use of the current US recommendations and a serial algorithm would have resulted in 1977 (92%) persons eligible for ART: 75% by CDC clinical stage B or C; 15% by CD4 cell count less than 350 x 10(6) cells/microl (including 8% < 200 x 10(6) cells/microl); and an estimated 3.6% due to viral load greater than 55 000 copies/ml. Using DAI-CI criteria and heavily subsidized laboratory test costs, the addition of CD4 cell count to clinical criteria cost US dollar 50 (serial algorithm) and US dollar 203 (parallel algorithm) to identify each additional eligible person. Modelling current recommendations with a serial algorithm, CD4 cell count cost an average US dollar 62/eligible person (US recommendations) and US dollar 109 (WHO recommendations). The addition of viral load cost between US dollar 108 (serial algorithm DAI) to US dollar 1700 (parallel algorithm DAI) to identify each additional eligible person. CONCLUSION: In the African context of scarce resources and the huge unmet demands for voluntary HIV testing and for ART, simple screening strategies are needed to identify those most in need of ART. Health personnel should be trained to identify and refer clinically symptomatic persons. Viral load testing is of high cost and dubious benefit and should not be part of screening algorithms for initiating ART.

Adolescent↗

PubMed1980

On the respresentation of multi-input systems: computational properties of polynomial algorithms.

This paper introduces a theoretical frame-work for characterizing and classifying simple parallel algorithms and systems with many inputs, for example an array of photoreceptors. The polynomial representation (Taylor series development) of a large class of operators is introduced and its range of validity discussed. The problems involved in the polynomial approximation of systems are also briefly reviewed. Symmetry properties of the input-output map and their implications for the system structure (i.e. its kernels) are studied. Finally, the computational properties of polynomial mappings are characterized.

Mathematics↗

PubMed1999

Evaluation of HIV serial and parallel serologic testing algorithms in Abidjan, Côte d'Ivoire.

OBJECTIVE: To evaluate HIV serologic testing algorithms based on a combination of three enzyme linked immunosorbent assays (ELISA) for the confirmation of HIV infection in Abidjan, Côte d'Ivoire, where HIV-2 and HIV-1 non-B subtypes are prevalent. METHODS: A total of 1069 human sera with known serologic status, in addition to a seroconversion and low titer antibody panel were initially tested by six ELISA to determine the sensitivity, specificity and delta values of the assays. On the basis of the performance of the assays, three ELISA (Enzygnost, ICE 1.0.2, and Vironostika) were selected for use in a parallel and serial testing algorithm in analyzing 8283 consecutively collected sera. In the parallel testing algorithm, sera concordantly reactive or non-reactive by Enzygnost and ICE 1.0.2 were considered as true positive or true negative, respectively. In the serial algorithm, sera reactive by Enzygnost were retested by ICE 1.0.2. Sera with discordant results were tested by Vironostika, and the results was considered definitive. All reactive sera, plus a random sample of negative sera were tested for confirmation by Peptilav. In addition, a random sample of reactive sera was tested by Western blot. RESULTS: All ELISA had 100% sensitivity; specificities ranged from 96.8 to 100%. Positive and negative delta values of the ELISA were high (range, 6.89 to 46.07 and -2.05 to -5.75, respectively). Of the 8283 sera, 2054 were considered true positives and were correctly classified by the parallel testing algorithm (sensitivity, 100%). Of the 6229 true negative sera, 6226 were negative by the parallel testing algorithm (specificity, 99.95%). The sensitivity of the serial algorithm was 99.96%, and specificity was 99.95%. None of the 250 concordant ELISA-negative sera in the algorithm that were randomly tested in Peptilav was positive; similarly, all of the 103 concordant ELISA-positive sera were confirmed by Western blot. The three-ELISA algorithm resulted in reagent cost-savings of at least 50% compared with the Peptilav-based algorithm. CONCLUSION: These results suggest that a combination of ELISA using different principles or antigens in a serial or parallel algorithm is an efficient and cost-effective alternative to the standard algorithm in areas where HIV-1 and HIV-2 are prevalent.

Algorithms↗

PubMed1995

RNA secondary structure prediction using highly parallel computers.

An RNA secondary structure prediction method using a highly parallel computer is reported. We focus on finding thermodynamically stable structures of a single-stranded RNA molecule. Our approach is based on a parallel combinatorial method which calculates the free energy of a molecule as the sum of the free energies of all the physically possible hydrogen bonds. Our parallel algorithm finds many highly stable structures all at once, while most of the conventional prediction methods find only the most stable structure. The important idea in our algorithm is search tree pruning, with dynamic load balancing across the processor elements in a parallel computer. Software tools for visualization and classification of secondary structures are also presented using the sequence of cadang-cadang coconut viroid as an example. Our software system runs on CM-5.

Algorithms↗

PubMed2006

Parallel coupled perturbed CASSCF equations and analytic CASSCF second derivatives.

A parallel algorithm for solving the coupled-perturbed MCSCF (CPMCSCF) equations and analytic nuclear second derivatives of CASSCF wave functions is presented. A parallel scheme for evaluating derivative integrals and their subsequent use in constructing other derivative quantities is described. The task of solving the CPMCSCF equations is approached using a parallelization scheme that partitions the electronic hessian matrix over all processors as opposed to simple partitioning of the 3 N solution vectors among the processors. The scalability of the current algorithm, up to 128 processors, is demonstrated. Using three test cases, results indicate that the parallelization of derivative integral evaluation through a simple scheme is highly effective regardless of the size of the basis set employed in the CASSCF energy calculation. Parallelization of the construction of the MCSCF electronic hessian during solution of the CPMCSCF equations varies quantitatively depending on the nature of the hessian itself, but is highly scalable in all cases.

Journal Article↗

PubMed2000

Extremal-point densities of interface fluctuations

We introduce and investigate the stochastic dynamics of the density of local extrema (minima and maxima) of nonequilibrium surface fluctuations. We give a number of analytic results for interface fluctuations described by linear Langevin equations, and for on-lattice, solid-on-solid surface-growth models. We show that, in spite of the nonuniversal character of the quantities studied, their behavior against the variation of the microscopic length scales can present generic features, characteristic of the macroscopic observables of the system. The quantities investigated here provide us with tools that give an unorthodox approach to the dynamics of surface morphologies: a statistical analysis from the short-wavelength end of the Fourier decomposition spectrum. In addition to surface-growth applications, our results can be used to solve the asymptotic scalability problem of massively parallel algorithms for discrete-event simulations, which are extensively used in Monte Carlo simulations on parallel architectures.

Journal Article↗

PubMed2001

ParAlign: a parallel sequence alignment algorithm for rapid and sensitive database searches.

There is a need for faster and more sensitive algorithms for sequence similarity searching in view of the rapidly increasing amounts of genomic sequence data available. Parallel processing capabilities in the form of the single instruction, multiple data (SIMD) technology are now available in common microprocessors and enable a single microprocessor to perform many operations in parallel. The ParAlign algorithm has been specifically designed to take advantage of this technology. The new algorithm initially exploits parallelism to perform a very rapid computation of the exact optimal ungapped alignment score for all diagonals in the alignment matrix. Then, a novel heuristic is employed to compute an approximate score of a gapped alignment by combining the scores of several diagonals. This approximate score is used to select the most interesting database sequences for a subsequent Smith-Waterman alignment, which is also parallelised. The resulting method represents a substantial improvement compared to existing heuristics. The sensitivity and specificity of ParAlign was found to be as good as Smith-Waterman implementations when the same method for computing the statistical significance of the matches was used. In terms of speed, only the significantly less sensitive NCBI BLAST 2 program was found to outperform the new approach. Online searches are available at http://dna.uio.no/search/

Algorithms↗

PubMed1997

Multimodal function optimization using minimal representation size clustering and its application to planning multipaths.

A novel genetic algorithm (GA) using minimal representation size cluster (MRSC) analysis is designed and implemented for solving multimodal function optimization problems. The problem of multimodal function optimization is framed within a hypothesize-and-test paradigm using minimal representation size (minimal complexity) for species formation and a GA. A multiple-population GA is developed to identify different species. The number of populations, thus the number of different species, is determined by the minimal representation size criterion. Therefore, the proposed algorithm reveals the unknown structure of the multimodal function when a priori knowledge about the function is unknown. The effectiveness of the algorithm is demonstrated on a number of multimodal test functions. The proposed scheme results in a highly parallel algorithm for finding multiple local minima. In this paper, a path-planning algorithm is also developed based on the MRSC_GA algorithm. The algorithm utilizes MRSC_GA for planning paths for mobile robots, piano-mover problems, and N-link manipulators. The MRSC_GA is used for generating multipaths to provide alternative solutions to the path-planning problem. The generation of alternative solutions is especially important for planning paths in dynamic environments. A novel iterative multiresolution path representation is used as a basis for the GA coding. The effectiveness of the algorithm is demonstrated on a number of two-dimensional path-planning problems.

Algorithms↗