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 217 records · Page 12Linked to original sources

PubMed1990

A review of the CLIP system for the quantitative analysis of two-dimensional electrophoresis gels.

This paper reviews the CLIP image processing system for the complete analysis of two-dimensional electrophoresis images. The analysis problem for two-dimensional gel images can be broken down into three issues: segmentation of individual gel images, alignment and comparison of pairs of gel images, and information storage and retrieval. This paper describes these problems and reviews how the CLIP system handles each of them. Segmentation is the location and isolation of each protein spot on an individual gel image and also the extraction of individual spot data such as position, area and volume. There are three basic stages: background field correction, noise filtering, spot detection and information extraction. Alignment and comparison of gel images involves matching protein spots between two gels. This can be quite difficult because there is not a simple relationship which can transform one gel image onto another. The database issues concern storing all the information which has been obtained from the above operations such that retrieval of this information can be readily performed. The advantage of the CLIP system over others is speed of processing. CLIP series computers use one processor for every pixel of the camera image such that image processing algorithms run in parallel. The main disadvantage is in the cost of these machines. With the declining trend in the cost of parallel processors, these machines will become more and more viable alternatives. This papers reviews the algorithms for the analysis of two-dimensional gels. It is shown that CLIP is flexible enough to perform more than one type of algorithm for a particular operation.

Algorithms↗

PubMed2004

Efficient algorithm for the forest fire model.

The Drossel-Schwabl forest fire model is one of the best studied models of nonconservative self-organized criticality. However, using an alternative algorithm, which allows us to study the model on large statistical and spatial scales, it has been shown to lack simple scaling. We thereby show that the considered model is not critical. This paper presents the algorithm and its parallel implementation in detail, together with large-scale numerical results for several observables. The algorithm can easily be adapted to related problems such as percolation.

Journal Article↗

PubMed1991

A parallel computing interface to facilitate development of physiologic signal processing algorithms.

We have created a system to aid in the development of algorithms related to the blood pressure waveform. The system performs all of the basic analyses of the waveform, and allows the user to utilize the results of those analyses for the algorithm under development. We have used a parallel programming architecture which keeps the different tasks, or processes, within the system independent of each other. Additionally, we have developed a graphics interface to enable the user to visualize the waveform, the system analysis, and the internal workings of the algorithm under development.

Algorithms↗

PubMed2006

Optimized parallel tempering simulations of proteins.

We apply a recently developed adaptive algorithm that systematically improves the efficiency of parallel tempering or replica exchange methods in the numerical simulation of small proteins. Feedback iterations allow us to identify an optimal set of temperatures/replicas which are found to concentrate at the bottlenecks of the simulations. A measure of convergence for the equilibration of the parallel tempering algorithm is discussed. We test our algorithm by simulating the 36-residue villin headpiece subdomain HP-36 where we find a lowest-energy configuration with a root-mean-square deviation of less than 4 A to the experimentally determined structure.

Algorithms↗

PubMed1998

Computer simulation and spatial modelling in heart surgery.

In this work, three dimensional modelling and computer simulation of heat transfer on generally-shaped nonhomogeneous bodies is proposed and described. The complexity of the calculation is estimated and the potential use of high performance parallel computers is discussed. The method is focused on applications in medicine. As an example, a numerical algorithm for the parallel computer simulation of heart cooling procedures during surgery is presented. On the basis of simulated results, two different methods of cooling are compared.

Algorithms↗

PubMed2005

Three-dimensional segmentation and skeletonization to build an airway tree data structure for small animals.

Quantitative analysis of intrathoracic airway tree geometry is important for objective evaluation of bronchial tree structure and function. Currently, there is more human data than small animal data on airway morphometry. In this study, we implemented a semi-automatic approach to quantitatively describe airway tree geometry by using high-resolution computed tomography (CT) images to build a tree data structure for small animals such as rats and mice. Silicon lung casts of the excised lungs from a canine and a mouse were used for micro-CT imaging of the airway trees. The programming language IDL was used to implement a 3D region-growing threshold algorithm for segmenting out the airway lung volume from the CT data. Subsequently, a fully-parallel 3D thinning algorithm was implemented in order to complete the skeletonization of the segmented airways. A tree data structure was then created and saved by parsing through the skeletonized volume using the Python programming language. Pertinent information such as the length of all airway segments was stored in the data structure. This approach was shown to be accurate and efficient for up to six generations for the canine lung cast and ten generations for the mouse lung cast.

Algorithms↗

PubMed1997

Using video-oriented instructions to speed up sequence comparison.

MOTIVATION: This document presents an implementation of the well-known Smith-Waterman algorithm for comparison of proteic and nucleic sequences, using specialized video instructions. These instructions, SIMD-like in their design, make possible parallelization of the algorithm at the instruction level. RESULTS: Benchmarks on an ULTRA SPARC running at 167 MHz show a speed-up factor of two compared to the same algorithm implemented with integer instructions on the same machine. Performance reaches over 18 million matrix cells per second on a single processor, giving to our knowledge the fastest implementation of the Smith-Waterman algorithm on a workstation. The accelerated procedure was introduced in LASSAP--a LArge Scale Sequence compArison Package software developed at INRIA--which handles parallelism at higher level. On a SUN Enterprise 6000 server with 12 processors, a speed of nearly 200 million matrix cells per second has been obtained. A sequence of length 300 amino acids is scanned against SWISSPROT R33 (1,8531,385 residues) in 29 s. This procedure is not restricted to databank scanning. It applies to all cases handled by LASSAP (intra- and inter-bank comparisons, Z-score computation, etc.

Algorithms↗

PubMed2004

Exhaustive whole-genome tandem repeats search.

MOTIVATION: Approximate tandem repeats (ATR) occur frequently in the genomes of organisms, and are a source of polymorphisms observed in individuals, and thus are of interest to those studying genetic disorders. Though extensive work has been done in order to identify ATRs, there are inherent limitations with the current approaches in terms of the number of pattern sizes that can be searched or the size of the input length. RESULTS: This paper describes (1) a new algorithm which exhaustively finds all variable-length ATRs in a genomic sequence and (2) a precise description of, and an algorithm to significantly reduce, redundancy in the output. Our ATR definition is parameterized by a mismatch ratio p which allows for more mismatches in longer tandem repeats (and fewer in shorter). Furthermore, our algorithm is embarrassingly parallel and thus can attain near-linear speed-up on Beowulf clusters. We present results of our algorithm applied to sequences of widely differing lengths (from genes to chromosomes). AVAILABILITY: Source and binaries are available on request.

Algorithms↗

PubMed2005

Exploiting quantum parallelism to simulate quantum random many-body systems.

We present an algorithm that exploits quantum parallelism to simulate randomness in a quantum system. In our scheme, all possible realizations of the random parameters are encoded quantum mechanically in a superposition state of an auxiliary system. We show how our algorithm allows for the efficient simulation of dynamics of quantum random spin chains with known numerical methods. We propose an experimental realization based on atoms in optical lattices in which disorder could be simulated in parallel and in a controlled way through the interaction with another atomic species.

Journal Article↗

PubMed2006

Parallel multifactor dimensionality reduction: a tool for the large-scale analysis of gene-gene interactions.

UNLABELLED: Parallel multifactor dimensionality reduction is a tool for large-scale analysis of gene-gene and gene-environment interactions. The MDR algorithm was redesigned to allow an unlimited number of study subjects, total variables and variable states, and to remove restrictions on the order of interactions being analyzed. In addition, the algorithm is markedly more efficient, with approximately 150-fold decrease in runtime for equivalent analyses. To facilitate the processing of large datasets, the algorithm was made parallel. AVAILABILITY: Parallel MDR is freely available for non-commercial research institutions. For full details see http://chgr.mc.vanderbilt.edu/ritchielab/pMDR. An open-source version of MDR software is available at http://www.epistasis.org.

Algorithms↗

PubMed1992

[Single photon emission computed tomography by using fan beam collimator].

A multislice fan beam collimator which has parallel collimation along the cephalic-caudal axis of a patient and converging collimation within planes that are perpendicular to that axis was designed for a SPECT system with a rotating scintillation camera, and it was constructed by the lead casting method which was developed in recent years. A reconstruction algorithm for fan beam SPECT was formed originally by combining the reconstruction algorithm of the parallel beam SPECT with that of the fan beam X-ray CT. The algorithm for fan beam SPECT was confirmed by means of computer simulation and a head phantom filled with diluted radionuclide. Not only 99mTc but also 131I was used as a radionuclide. A SPECT image with the fan beam collimator was compared with that of a parallel hole, low energy, high resolution collimator which was routinely used for clinical and research SPECT studies. Both system resolution and sensitivity of the fan beam collimator were approximately 20% better than those of the parallel hole collimator. Comparing SPECT images obtained from fan beam collimator with those of parallel hole collimator, the SPECT images using fan beam collimator had far better resolution. A fan beam collimator is a useful implement for the SPECT study.

Algorithms↗

PubMed2005

Evaluation of rapid prenatal human immunodeficiency virus testing in rural cameroon.

Pregnant women (n = 859) in rural Cameroonian prenatal clinics were screened by two rapid human immunodeficiency virus (HIV) antibody tests (rapid tests [RT]) (Determine and Hema-Strip) using either whole blood or plasma. One additional RT (Capillus, HIV-CHEK, or Sero-Card) was used to resolve discordant results. RT results were compared with HIV-1 enzyme immunoassay (EIA) and Western blot (WB) results of matched dried blood spots (DBS) to assess the accuracy of HIV RTs. DBS EIA/WB identified 83 HIV antibody-reactive, 763 HIV antibody-nonreactive, and 13 indeterminate specimens. RT results were evaluated in serial (two consecutive tests) or parallel (two simultaneous tests) testing algorithms. A serial algorithm using Determine and Hema-Strip yielded sensitivity and specificity results of 97.6% and 99.7%, respectively, whereas a parallel RT algorithm using Determine plus a second RT produced a sensitivity and specificity of 100% and 99.7%, respectively. HIV RTs provide excellent alternatives for identifying HIV infection, and their field performance could be monitored using DBS testing strategies.

Algorithms↗

PubMed2006

Robust estimation of peptide abundance ratios and rigorous scoring of their variability and bias in quantitative shotgun proteomics.

The abundance ratio between the light and heavy isotopologues of an isotopically labeled peptide can be estimated from their selected ion chromatograms. However, quantitative shotgun proteomics measurements yield selected ion chromatograms at highly variable signal-to-noise ratios for tens of thousands of peptides. This challenge calls for algorithms that not only robustly estimate the abundance ratios of different peptides but also rigorously score each abundance ratio for the expected estimation bias and variability. Scoring of the abundance ratios, much like scoring of sequence assignment for tandem mass spectra by peptide identification algorithms, enables filtering of unreliable peptide quantification and use of formal statistical inference in the subsequent protein abundance ratio estimation. In this study, a parallel paired covariance algorithm is used for robust peak detection in selected ion chromatograms. A peak profile is generated for each peptide, which is a scatterplot of ion intensities measured for the two isotopologues within their chromatographic peaks. Principal component analysis of the peak profile is proposed to estimate the peptide abundance ratio and to score the estimation with the signal-to-noise ratio of the peak profile (profile signal-to-noise ratio). We demonstrate that the profile signal-to-noise ratio is inversely correlated with the variability and bias of peptide abundance ratio estimation.

Algorithms↗

PubMed2005

Combining smart darting with parallel tempering using Eckart space: application to Lennard-Jones clusters.

The smart-darting algorithm is a Monte Carlo based simulation method used to overcome quasiergodicity problems associated with disconnected regions of configurations space separated by high energy barriers. As originally implemented, the smart-darting method works well for clusters at low temperatures with the angular momentum restricted to zero and where there are no transitions to permutational isomers. If the rotational motion of the clusters is unrestricted or if permutational isomerization becomes important, the acceptance probability of darting moves in the original implementation of the method becomes vanishingly small. In this work the smart-darting algorithm is combined with the parallel tempering method in a manner where both rotational motion and permutational isomerization events are important. To enable the combination of parallel tempering with smart darting so that the smart-darting moves have a reasonable acceptance probability, the original algorithm is modified by using a restricted space for the smart-darting moves. The restricted space uses a body-fixed coordinate system first introduced by Eckart, and moves in this Eckart space are coupled with local moves in the full 3N-dimensional space. The modified smart-darting method is applied to the calculation of the heat capacity of a seven-atom Lennard-Jones cluster. The smart-darting moves yield significant improvement in the statistical fluctuations of the calculated heat capacity in the region of temperatures where the system isomerizes. When the modified smart-darting algorithm is combined with parallel tempering, the statistical fluctuations of the heat capacity of a seven-atom Lennard-Jones cluster using the combined method are smaller than parallel tempering when used alone.

Journal Article↗

PubMed2000

Sensitivity analysis and other improvements to tailored combinatorial library design

"Tailoring" combinatorial libraries was developed several years ago as a very general and intuitive method to design diverse compound collections while controlling the profile of other pharmaceutically relevant properties. The candidate substituents were assigned to "categorical bins" according to their properties, and successive steps of D-optimal design were performed to generate diverse substituent sets consistent with required membership quotas from each bin. This serial algorithm was expedient to implement from existing D-optimal design codes, but was order-dependent and did not generally locate the very best possible design. A new "parallel" Fedorov search algorithm has now been implemented that can find the most diverse property-tailored design. An ambiguous mass penalty has been added, whereby most duplicate masses can be eliminated with little loss of library diversity. Sensitivity analysis has also been added to quantitatively explore the diversity trade-offs due to increasing or decreasing each specific kind of bias.

Journal Article↗

PubMed2004

Simulation of branching blood flows on parallel computers.

We present a fully parallel nonlinearly implicit algorithm for the numerical simulation of some branching blood flow problems, which require efficient and robust solver technologies in order to handle the high nonlinearity and the complex geometry. Parallel processing is necessary because of the large number of mesh points needed to accurately discretize the system of differential equations. In this paper we introduce a parallel Newton-Krylov-Schwarz based implicit method, and software for distributed memory parallel computers, for solving the nonlinear algebraic systems arising from a Q2-Q1 finite element discretization of the incompressible Navier-Stokes equations that we use to model the blood flow in the left anterior descending coronary artery.

Arteries↗

PubMed1995

Effective water model for Monte Carlo simulations of proteins.

We present an effective theory for water. Our goal is to formulate an accurate model for the effects of solvation on protein dynamics, without incurring the huge computational cost and the slow temporal evolution typical of molecular dynamics simulations of liquids. We replace the individual water molecules in an all-atom potential with a local dielectric density field, with self-interactions given by the Landau-Ginzburg free energy and external interactions by Lennard-Jones forces at the surface of the protein atoms. We explore conformational space with finite temperature Monte Carlo dynamics, using parallel Langevin and Fourier acceleration algorithms well suited to data-parallel computer architectures such as the Connection Machine. To establish the validity of our approximations, we compare our electrostatic contribution to the solvation energy with the results of Lim, Bashford, and Karplus using a conventional static continuum dielectric cavity model, and the nonelectrostatic contributions with estimates of hydrophobic surface free energy. Our model can also accommodate ionic charges and temperature fluctuations. We propose future investigations extending our effective theory of solvation to include explicit orientational entropy and hydrogen-bonding terms.

Models, Molecular↗

PubMed1997

Genetically Trained Cellular Neural Networks.

Real-coded genetic algorithms on a parallel architecture are applied to optimize the synaptic couplings of a Cellular Neural Network for specific greyscale image processing tasks. Using supervised learning information in the fitness function, we propose the Genetic Algorithm as a general training method for Cellular Neural Networks. Copyright 1997 Elsevier Science Ltd.

Journal Article↗