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 55 records · Page 3Linked to original sources

PubMed2004

Parallel Metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference.

MOTIVATION: Bayesian estimation of phylogeny is based on the posterior probability distribution of trees. Currently, the only numerical method that can effectively approximate posterior probabilities of trees is Markov chain Monte Carlo (MCMC). Standard implementations of MCMC can be prone to entrapment in local optima. Metropolis coupled MCMC [(MC)(3)], a variant of MCMC, allows multiple peaks in the landscape of trees to be more readily explored, but at the cost of increased execution time. RESULTS: This paper presents a parallel algorithm for (MC)(3). The proposed parallel algorithm retains the ability to explore multiple peaks in the posterior distribution of trees while maintaining a fast execution time. The algorithm has been implemented using two popular parallel programming models: message passing and shared memory. Performance results indicate nearly linear speed improvement in both programming models for small and large data sets.

Algorithms↗

PubMed2004

An annealed chaotic maximum neural network for bipartite subgraph problem.

In this paper, based on maximum neural network, we propose a new parallel algorithm that can help the maximum neural network escape from local minima by including a transient chaotic neurodynamics for bipartite subgraph problem. The goal of the bipartite subgraph problem, which is an NP- complete problem, is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. Lee et al. presented a parallel algorithm using the maximum neural model (winner-take-all neuron model) for this NP- complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to a local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our algorithm finds the optimum or near-optimum solution for the bipartite subgraph problem superior to that of the best existing parallel algorithms.

Algorithms↗

PubMed2002

NMR implementation of a parallel search algorithm.

Recently it has been shown that the dynamics of a cluster of dipolar-coupled spins can be manipulated to store and process a large amount of information in a parallel way [Chem. Phys. Lett. 360, 161 (2002)]]. Here it is further demonstrated that it is possible to realize a cascade of parallel bitwise operations on a spin cluster so that an algorithm of parallel search can be experimentally implemented by means of nuclear magnetic resonance.

Journal Article↗

PubMed2001

Selecting informative genes with parallel genetic algorithms in tissue classification.

Recent advances in biotechnology offer the ability to measure the levels of expression of thousands of genes in parallel. Analysis of such data can provide understanding and insight into gene function and regulatory mechanisms. Several machine learning approaches have been used to aid to understand the functions of genes. However, these tasks are made more difficult due to the noisy nature of array data and the overwhelming number of gene features. In this paper, we use the parallel genetic algorithm to filter out the informative genes relative to classification. By combing with the classification method proposed by Golub et al. and Slonim et al., we classify the data sets with tissues of different classes, and the preliminary results are presented in this paper.

Algorithms↗

PubMed2006

Larger water clusters with edges and corners on their way to ice: structural trends elucidated with an improved parallel evolutionary algorithm.

For the difficult task of finding global minimum energy structures for molecular clusters of nontrivial size, we present a highly efficient parallel implementation of an evolutionary algorithm. By completely abandoning the traditional concept of generations and by replacing it with a less rigid pool concept, we have managed to eliminate serial bottlenecks completely and can operate the algorithm efficiently on an arbitrary number of parallel processes. Nevertheless, our new algorithm still realizes all of the main features of our old, successful implementation. First tests of the new algorithm are shown for the highly demanding problem of water clusters modeled by a potential with flexible, polarizable monomers (TTM2-F). For this problem, our new algorithm not only reproduces all of the global minima proposed previously in considerably less CPU time but also leads to improved proposals in several cases. These, in turn, qualitatively change our earlier predictions concerning the transitions from all-surface structures to cages with a single interior molecule, and from one to two interior molecules. Furthermore, we compare preliminary results up to n = 105 with locally optimized cuts from several ice modifications. This comparison indicates that relaxed ice structures may start to be competitive already at cluster sizes above n = 90.

Journal Article↗

PubMed2004

Rapid testing strategies for HIV-1 serodiagnosis in high-prevalence African settings.

BACKGROUND: Nearly 30 million people in sub-Saharan Africa are infected with HIV. While recent commitment of resources from international donors is heartening, rational use of these resources for AIDS prevention and care will require a major scaling up of HIV diagnostic services in affected countries. OBJECTIVE: This paper considers the various settings and populations in which HIV testing might be implemented, and the goals to be achieved by that testing. It also defines the practical information that public health decision makers in sub-Saharan Africa should have in order to choose an appropriate test or combination of tests for use in a particular clinical setting. METHODS: Using a conditional probability model and published performance characteristics of rapid HIV serologic tests, the clinical effectiveness and costs of three major testing strategies are evaluated: (1) a single, highly sensitive test; (2) a serial algorithm, where positive results on a first test are confirmed with a more specific second test; and (3) a parallel algorithm, where each specimen is tested with two separate rapid tests, and discordant results are resolved with a third, different rapid test. This analysis was performed in 2003. RESULTS: We suggest that in any setting, both a serial and a parallel algorithm yield fewer incorrect results than does a single screening assay, but are more costly. A parallel testing algorithm yields fewer incorrect results than does a serial algorithm, but is more costly. CONCLUSIONS: We suggest that while a parallel testing algorithm has the advantage of avoiding indeterminate results, that strategy may be prohibitively costly for many developing world settings. Furthermore, we suggest that different testing algorithms are appropriate for different clinical settings.

AIDS Serodiagnosis↗

PubMed2005

P-RnaPredict--a parallel evolutionary algorithm for RNA folding: effects of pseudorandom number quality.

This paper presents a fully parallel version of RnaPredict, a genetic algorithm (GA) for RNA secondary structure prediction. The research presented here builds on previous work and examines the impact of three different pseudorandom number generators (PRNGs) on the GA's performance. The three generators tested are the C standard library PRNG RAND, a parallelized multiplicative congruential generator (MCG), and a parallelized Mersenne Twister (MT). A fully parallel version of RnaPredict using the Message Passing Interface (MPI) was implemented on a 128-node Beowulf cluster. The PRNG comparison tests were performed with known structures whose sequences are 118, 122, 468, 543, and 556 nucleotides in length. The effects of the PRNGs are investigated and the predicted structures are compared to known structures. Results indicate that P-RnaPredict demonstrated good prediction accuracy, particularly so for shorter sequences.

Algorithms↗

PubMed2004

Algorithm for parallel Laplacian growth by iterated conformal maps.

We report an algorithm to generate Laplacian growth patterns using iterated conformal maps. The difficulty of growing a complete layer with local width proportional to the gradient of the Laplacian field is overcome. The resulting growth patterns are compared to those obtained by the best algorithms of direct numerical solutions. The fractal dimension of the patterns is discussed.

Journal Article↗

PubMed2006

Hadamard NMR spectroscopy for two-dimensional quantum information processing and parallel search algorithms.

Hadamard spectroscopy has earlier been used to speed-up multi-dimensional NMR experiments. In this work, we speed-up the two-dimensional quantum computing scheme, by using Hadamard spectroscopy in the indirect dimension, resulting in a scheme which is faster and requires the Fourier transformation only in the direct dimension. Two and three qubit quantum gates are implemented with an extra observer qubit. We also use one-dimensional Hadamard spectroscopy for binary information storage by spatial encoding and implementation of a parallel search algorithm.

Algorithms↗

PubMed2001

MRI prior computation and parallel tempering algorithm: a probabilistic resolution of the MEG/EEG inverse problem.

Since the MEG inverse problem is ill-posed and admits many possible solutions, it is not possible to give it a single "true" answer. Therefore, we propose here to use a specific probabilistic algorithm to map the full probability distribution of the MEG sources with Markov Chain Monte Carlo methods. Using a Bayesian approach, the probability of the MEG solutions is expressed as the product of the likelihood by the prior probability. To compute the prior and constrain the MEG inverse problem resolution, MRI data are also acquired and automatically processed to determine the brain position and volume. We then use Parallel Tempering algorithm to estimate the full posterior probability and determine the likely solutions of the inverse problem. We illustrate the method with results obtained from the analysis of somatosensory data. This illustrates both the MRI processing for the prior computation, and how the knowledge of the full posterior probability distribution can be used to estimate the position of the sources, as well as their likely extension.

Adult↗

PubMed2006

Graphical exploratory data analysis of RNA secondary structure dynamics predicted by the massively parallel genetic algorithm.

Studies indicate that RNA may enter intermediate and multiple conformational states, which may impact gene expression and molecular function. It is known that the biologically functional states of RNA molecules may not correspond to their minimum energy conformations, that kinetic barriers may trap the molecule in a local minimum, that folding often occurs during transcription, and that cases exist in which a molecule will transition between one or more functional conformations. Thus, methods for simulating the folding pathway and dynamic behavior of an RNA molecule are important for the prediction of RNA structure and its associated functions. We have developed several data mining techniques guided by interactive visualization tools associated with our massively parallel genetic algorithm for RNA/DNA secondary structure prediction, MPGAfold, and StructureLab analysis workbench. Most of the methods and tools are also applicable to dynamic programming algorithm (DPA) folding data analysis. When applied to MPGAfold results these methodologies are used to determine the significant intermediate and final structures associated with co-transcriptional and full length RNA folding. Since the genetic algorithm is essentially stochastic, multiple runs are required to develop a consensus understanding of an RNA structure. The interactive visualizations facilitate interpretation of results from sequential or full length individual MPGAfold runs, final results of multiple folding runs, including multiple population sizes, and the results from multiple RNA sequences of one family. This paper describes several of these techniques and shows how they are used to help solve this highly combinatoric problem.

Algorithms↗

PubMed1997

Predicting RNA H-type pseudoknots with the massively parallel genetic algorithm.

MOTIVATION: Using the genetic algorithm (GA) for RNA folding on a massively parallel supercomputer, MasPar MP-2 with 16,384 processors, we successfully predicted the existence of H-type pseudoknots in several sequences. RESULTS: The GA is applied to folding the tRNA-like 3' end of turnip yellow mosaic virus (TYMV) RNA sequence with 82 nucleotides, the 3' UTRs of satellite tobacco necrosis virus (STNV)-2 RNA sequence with 619 nucleotides and STNV-I RNA sequence with 622 nucleotides, and the bacteriophage T2, T4 and T6 gene 32 mRNA sequences with 946, 1340 and 946 nucleotides, respectively. The GA's results match the phylogenetically supported tertiary structures of these sequences.

Algorithms↗

PubMed2000

Model-based spectral estimation of Doppler signals using parallel genetic algorithms.

Conventional spectral analysis methods use a fast Fourier transform (FFT) on consecutive or overlapping windowed data segments. For Doppler ultrasound signals, this approach suffers from an inadequate frequency resolution due to the time segment duration and the non-stationarity characteristics of the signals. Parametric or model-based estimators can give significant improvements in the time-frequency resolution at the expense of a higher computational complexity. This work describes an approach which implements in real-time a parametric spectral estimator method using genetic algorithms (GAs) in order to find the optimum set of parameters for the adaptive filter that minimises the error function. The aim is to reduce the computational complexity of the conventional algorithm by using the simplicity associated to GAs and exploiting its parallel characteristics. This will allow the implementation of higher order filters, increasing the spectrum resolution, and opening a greater scope for using more complex methods.

Algorithms↗

PubMed2001

A probabilistic solution to the MEG inverse problem via MCMC methods: the reversible jump and parallel tempering algorithms.

We investigated the usefulness of probabilistic Markov chain Monte Carlo (MCMC) methods for solving the magnetoencephalography (MEG) inverse problem, by using an algorithm composed of the combination of two MCMC samplers: Reversible Jump (RJ) and Parallel Tempering (PT). The MEG inverse problem was formulated in a probabilistic Bayesian approach, and we describe how the RJ and PT algorithms are fitted to our application. This approach offers better resolution of the MEG inverse problem even when the number of source dipoles is unknown (RJ), and significant reduction of the probability of erroneous convergence to local modes (PT). First estimates of the accuracy and resolution of our composite algorithm are given from results of simulation studies obtained with an unknown number of sources, and with white and neuromagnetic noise. In contrast to other approaches, MCMC methods do not just give an estimation of a "single best" solution, but they provide confidence interval for the source localization, probability distribution for the number of fitted dipoles, and estimation of other almost equally likely solutions.

Algorithms↗

PubMed2000

Measurement of Debye-Waller factors in Co3Ti by quantitative CBED

The Debye-Waller factors (DWFs) of Co and Ti atoms in Co3Ti have been obtained by quantitative convergent-beam electron diffraction (QCBED). They are B(Co) = 0.20-0.24 and BTi = 0.41-0.43 A2 in Co3Ti at room temperature. A modified simulated-annealing algorithm and its parallel algorithm were employed to obtain reliable results efficiently.

Journal Article↗

PubMed2003

Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES).

This paper presents a novel evolutionary optimization strategy based on the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). This new approach is intended to reduce the number of generations required for convergence to the optimum. Reducing the number of generations, i.e., the time complexity of the algorithm, is important if a large population size is desired: (1) to reduce the effect of noise; (2) to improve global search properties; and (3) to implement the algorithm on (highly) parallel machines. Our method results in a highly parallel algorithm which scales favorably with large numbers of processors. This is accomplished by efficiently incorporating the available information from a large population, thus significantly reducing the number of generations needed to adapt the covariance matrix. The original version of the CMA-ES was designed to reliably adapt the covariance matrix in small populations but it cannot exploit large populations efficiently. Our modifications scale up the efficiency to population sizes of up to 10n, where n is the problem dimension. This method has been applied to a large number of test problems, demonstrating that in many cases the CMA-ES can be advanced from quadratic to linear time complexity.

Algorithms↗

PubMed2003

An efficient approximation algorithm for finding a maximum clique using Hopfield network learning.

In this article, we present a solution to the maximum clique problem using a gradient-ascent learning algorithm of the Hopfield neural network. This method provides a near-optimum parallel algorithm for finding a maximum clique. To do this, we use the Hopfield neural network to generate a near-maximum clique and then modify weights in a gradient-ascent direction to allow the network to escape from the state of near-maximum clique to maximum clique or better. The proposed parallel algorithm is tested on two types of random graphs and some benchmark graphs from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). The simulation results show that the proposed learning algorithm can find good solutions in reasonable computation time.

Algorithms↗

PubMed2001

Using three-dimensional microfluidic networks for solving computationally hard problems.

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.

Algorithms↗