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 289 records · Page 16Linked to original sources

PubMed1986

A model for insertion loss degradation for parallel highway noise barriers.

An algorithm is developed and validated for the prediction of the reduction, or degradation, of traffic noise barrier insertion loss when a second barrier is placed on the opposite side of the highway. The algorithm combines the basic emission, propagation, and barrier attenuation features of the Federal Highway Administration traffic noise prediction model with a geometrical acoustics approach for multiple reflections. The resultant model can accommodate any number of source lanes or receivers, three vehicle categories, and independently variable barrier heights and absorption coefficients. The model was validated against mathematical, scale model, and full scale field data received from other researchers, and has proved to be a good predictor of insertion loss degradation.

Algorithms↗

PubMed1992

Molecular dynamics simulation on a network of workstations using a machine-independent parallel programming language.

Molecular dynamics simulations investigate local and global motion in molecules. Several parallel computing approaches have been taken to attack the most computationally expensive phase of molecular simulations, the evaluation of long range interactions. This paper reviews these approaches and develops a straightforward but effective algorithm using the machine-independent parallel programming language, Linda. The algorithm was run both on a shared memory parallel computer and on a network of high performance Unix workstations. Performance benchmarks were performed on both systems using two proteins. This algorithm offers a portable cost-effective alternative for molecular dynamics simulations. In view of the increasing numbers of networked workstations, this approach could help make molecular dynamics simulations more easily accessible to the research community.

Algorithms↗

PubMed1997

Parallel pattern search energy minimization.

This article describes the adaptation of a pattern search algorithm, for the computational optimization of model molecular structures, to run on a parallel computer. The parallel efficiency (speedup) of the algorithm is discussed, and the rate of convergence of the parallel procedure is compared to that of the sequential implementation. More generally, the article also illustrates how inherently nonparallelizable stochastic procedures may be successfully parallelized by rearrangement of the algorithm.

Algorithms↗

PubMed2004

A case study of high-throughput biological data processing on parallel platforms.

MOTIVATION: Analysis of large biological data sets using a variety of parallel processor computer architectures is a common task in bioinformatics. The efficiency of the analysis can be significantly improved by properly handling redundancy present in these data combined with taking advantage of the unique features of these compute architectures. RESULTS: We describe a generalized approach to this analysis, but present specific results using the program CEPAR, an efficient implementation of the Combinatorial Extension algorithm in a massively parallel (PAR) mode for finding pairwise protein structure similarities and aligning protein structures from the Protein Data Bank. CEPAR design and implementation are described and results provided for the efficiency of the algorithm when run on a large number of processors. AVAILABILITY: Source code is available by contacting one of the authors.

Algorithms↗

PubMed1996

A real-time scan conversion algorithm on commercially available microprocessors.

We have developed a new ultrasound scan conversion algorithm that can be executed very efficiently on modern microprocessors. Our algorithm is designed to handle the address calculations and input and output (I/O) data loading concurrently with the interpolation. The processing unit's computing power can be dedicated to performing pixel interpolations while the other operations are handled by an independent direct memory access (DMA) controller. By making intelligent use of the I/O transfer capabilities of the DMA controller, the algorithm avoids spending the processing unit's valuable computing cycles in address calculations and nonactive pixel blanking. Furthermore, the new approach speeds up the computation by utilizing the ability of superscalar and very long instruction word (VLIW) processors to perform multiple operations in parallel. Our scan conversion algorithm was implemented on a multimedia and imaging system based on the Texas Instruments TMS320C80 Multimedia Video Processor (MVP). Computing cycles are spent only on predeterminable nonzero output pixels. For example, an execution time of 11.4 ms was achieved when there are 101,829 nonzero output pixels. This algorithm demonstrates a substantial improvement over previous scan conversion algorithms, and its optimized implementation enables modern commercially available programmable processors to support scan conversion at video rates.

Algorithms↗

PubMed2006

Implementation and performance evaluation of reconstruction algorithms on graphics processors.

The high-throughput needs in electron tomography and in single particle analysis have driven the parallel implementation of several reconstruction algorithms and software packages on computing clusters. Here, we report on the implementation of popular reconstruction algorithms as weighted backprojection, simultaneous iterative reconstruction technique (SIRT) and simultaneous algebraic reconstruction technique (SART) on common graphics processors (GPUs). The speed gain achieved on the GPUs is in the order of sixty (60x) to eighty (80x) times, compared to the performance of a single central processing unit (CPU), which is comparable to the acceleration achieved on a medium-range computing cluster. This acceleration of the reconstruction is caused by the highly specialized architecture of the GPU. Further, we show that the quality of the reconstruction on the GPU is comparable to the CPU. We present detailed flow-chart diagrams of the implementation. The reconstruction software does not require special hardware apart from the commercially available graphics cards and could be easily integrated in software packages like SPIDER, XMIPP, TOM-Package and others.

Algorithms↗

PubMed1996

Sequential and parallel molecular mechanics calculations.

This article describes a gradient algorithm for the computational optimization of model molecular structures, and discusses the various compromises inherent in the practical expression of the algorithm in a Fortran computer program (VULCAN) for both sequential and parallel computers. Details are given of some previously undiscussed properties of gradient algorithms; various acceleration techniques are compared; and some traps for the unwary are highlighted.

Algorithms↗

PubMed1993

Near-IR imaging of atheromas in living arterial tissue.

A near-IR imaging system and parallel vector supercomputer are used with a fiber-optic probe to produce chemical maps of the intimal surface of living arteries. Spectrometric information collected at hundreds of near-IR wavelengths is assembled into color pictures of the lipoprotein and apolipoprotein composition of atheromas using a vectorized 3-D cellular automaton-based algorithm that operates in parallel. The nonparametric mathematics developed to identify and quantify the constituents of each voxel in the artery wall avoid the matrix factorizations that generate excess error in other pattern recognition methods and permit analysis in a wavelength space of over 1000 dimensions using fewer than 100 calibration samples. A surface feature resolution of 5.5 microns and depth resolution of 6.5 microns are achieved with the system. Data from the fiber optics confirm the injury hypothesis of lesion formation and the differing roles of HDL and LDL in cholesterol transport. In clinical studies, approximately 1/2 of human arterial lesions appear fibrous and contain little or no lipid. As such, these lesions would not be expected to regress in response to cholesterol-lowering agents such as lovastatin. Identification of lesion types in vivo will enhance the efficacy of treatment programs.

Apolipoproteins↗

PubMedDate not supplied

Structure analysis and classification of cervical cells using a processing system based on TV.

This paper presents preliminary results of a cell classification experiment using a new approach for feature extraction. The algorithm takes into account the special requirements of a fast parallel processing system (processor-oriented algorithms). A cell image is described by several hundred features derived from the nucleus only. The most significant features with respect to classification are determined by statistical analysis. Applying principal axis transform, a new feature set is computed, reduced considerably in dimensions. The data base (1,925 cell images of Papanicolaou-stained cervical specimens) was divided into a training set (963 images) and a test set (962 images). The classification results of the test set show that the recognition rate for the two-class problem (normal, suspicious) is better than 91%, using only ten morphologic features.

Cervix Mucus↗

PubMed2006

Insight into the structure of amyloid fibrils from the analysis of globular proteins.

The conversion from soluble states into cross-beta fibrillar aggregates is a property shared by many different proteins and peptides and was hence conjectured to be a generic feature of polypeptide chains. Increasing evidence is now accumulating that such fibrillar assemblies are generally characterized by a parallel in-register alignment of beta-strands contributed by distinct protein molecules. Here we assume a universal mechanism is responsible for beta-structure formation and deduce sequence-specific interaction energies between pairs of protein fragments from a statistical analysis of the native folds of globular proteins. The derived fragment-fragment interaction was implemented within a novel algorithm, prediction of amyloid structure aggregation (PASTA), to investigate the role of sequence heterogeneity in driving specific aggregation into ordered self-propagating cross-beta structures. The algorithm predicts that the parallel in-register arrangement of sequence portions that participate in the fibril cross-beta core is favoured in most cases. However, the antiparallel arrangement is correctly discriminated when present in fibrils formed by short peptides. The predictions of the most aggregation-prone portions of initially unfolded polypeptide chains are also in excellent agreement with available experimental observations. These results corroborate the recent hypothesis that the amyloid structure is stabilised by the same physicochemical determinants as those operating in folded proteins. They also suggest that side chain-side chain interaction across neighbouring beta-strands is a key determinant of amyloid fibril formation and of their self-propagating ability.

Amino Acid Sequence↗

PubMed1988

Parallel integration of vision modules.

Computer algorithms have been developed for several early vision processes, such as edge detection, stereopsis, motion, texture, and color, that give separate cues to the distance from the viewer of three-dimensional surfaces, their shape, and their material properties. Not surprisingly, biological vision systems still greatly outperform computer vision programs. One of the keys to the reliability, flexibility, and robustness of biological vision systems is their ability to integrate several visual cues. A computational technique for integrating different visual cues has now been developed and implemented with encouraging results on a parallel supercomputer.

Algorithms↗

PubMed2005

Efficient algorithms and software for detection of full-length LTR retrotransposons.

LTR retrotransposons constitute one of the most abundant classes of repetitive elements in eukaryotic genomes. In this paper, we present a new algorithm for detection of full-length LTR retrotransposons in genomic sequences. The algorithm identifies regions in a genomic sequence that show structural characteristics of LTR retrotransposons. Three key components distinguish our algorithm from that of current software - (i) a novel method that preprocesses the entire genomic sequence in linear time and produces high quality pairs of LTR candidates in running time that is constant per pair, (ii) a thorough alignment-based evaluation of candidate pairs to ensure high quality prediction, and (iii) a robust parameter set encompassing both structural constraints and quality controls providing users with a high degree of flexibility. Validation of both our serial and parallel implementations of the algorithm against the yeast genome indicates both superior quality and performance results when compared to existing software.

Algorithms↗

PubMed1997

Simultaneous acquisition of spatial harmonics (SMASH): fast imaging with radiofrequency coil arrays.

SiMultaneous Acquisition of Spatial Harmonics (SMASH) is a new fast-imaging technique that increases MR image acquisition speed by an integer factor over existing fast-imaging methods, without significant sacrifices in spatial resolution or signal-to-noise ratio. Image acquisition time is reduced by exploiting spatial information inherent in the geometry of a surface coil array to substitute for some of the phase encoding usually produced by magnetic field gradients. This allows for partially parallel image acquisitions using many of the existing fast-imaging sequences. Unlike the data combination algorithms of prior proposals for parallel imaging, SMASH reconstruction involves a small set of MR signal combinations prior to Fourier transformation, which can be advantageous for artifact handling and practical implementation. A twofold savings in image acquisition time is demonstrated here using commercial phased array coils on two different MR-imaging systems. Larger time savings factors can be expected for appropriate coil designs.

Abdomen↗

PubMed1999

The Goldman algorithm revisited: prospective evaluation of a computer-derived algorithm versus unaided physician judgment in suspected acute myocardial infarction.

BACKGROUND: It has been nearly a decade since Goldman's computer-driven algorithm to predict myocardial infarction was validated. Despite the potential to avoid admission of patients without acute myocardial infarction (AMI) to the coronary care unit (CCU), the routine use of computer-generated protocols has not been widely adopted. METHODS: Two hundred consecutive patients admitted to a university-affiliated community hospital with the suspected diagnosis of AMI as determined by physicians without the aid of the Goldman protocol underwent a blinded prospective evaluation to assess the performance of the Goldman algorithm in predicting the presence of AMI. Over the same time period, the Goldman algorithm was applied by retrospective chart review in 762 patients with non-AMI admitting diagnoses. Prospective history, physical examination, and electrocardiographic data were obtained within 24 hours of admission to the CCU by a physician blinded to each patient's clinical course. Retrospective chart reviews were conducted for 762 patients with chest pain given with non-AMI diagnoses. RESULTS: The diagnosis of AMI was confirmed in 68.5% (137/200) of patients with suspected AMI admitted to the CCU. In prospective parallel evaluations the Goldman algorithm predicted the presence of AMI in 167 (83.5%) of these 200 patients. All 137 confirmed patients with AMI were correctly identified by the Goldman algorithm. All major in-hospital complications occurred in the 137 patients who were diagnosed as having AMI. Of the 762 patients with chest pain with non-AMI diagnoses, only 27 (3.5%) sustained an AMI. The Goldman algorithm predicted the presence of AMI in 85% (23/27) of these patients. Adherence to the use of Goldman's algorithm in the triage of chest pain could have prevented 16.5% of CCU admissions for AMI. CONCLUSIONS: Routine adherence to the Goldman algorithm for the evaluation of patients with acute chest pain could have decreased the number of CCU admissions for suspected AMI by 16. 5%. Because major in-hospital complications occurred only in patients with AMI, this strategy would result in significant cost savings to our health care system without jeopardizing patient safety.

Algorithms↗

PubMed1995

Applications of parallel computing to biological problems.

Parallel computers should provide the greatest processing power and memory for scientific simulations in the coming decades. This review discusses general strategies and specific algorithms for the use of various parallel architectures in simulations of biological and artificial polymers. General strategies include space partitioning (domain decomposition cell methods) and distributed independent simulations. Specific algorithms include cellular automata for efficient abstract polymer simulation. One algorithm, the two-space algorithm, is particularly efficient both for parallel and serial computation. Three applications, 2D melts, gel electrophoresis, and polymer collapse, are described. Simulations of high-density melts in 2D show that contrary to expectations, polymers do not completely segregate at the highest densities; instead, polymer interpenetration is significant. Preliminary simulations of gel electrophoresis show its behavior in the diffusive regimen and demonstrate the use of Cellular Automaton Machines (CAMs). Polymer collapse is studied in the regime of large departures from good solvent conditions. In this regime, kinetics plays a significant role. Collapse is dominated (nucleated) by migration of the chain ends.

Algorithms↗

PubMed1998

Optimization of beam orientation in radiotherapy using planar geometry.

This paper proposes a new geometrical formulation of the coplanar beam orientation problem combined with a hybrid multiobjective genetic algorithm. The approach is demonstrated by optimizing the beam orientation in two dimensions, with the objectives being formulated using planar geometry. The traditional formulation of the objectives associated with the organs at risk has been modified to account for the use of complex dose delivery techniques such as beam intensity modulation. The new algorithm attempts to replicate the approach of a treatment planner whilst reducing the amount of computation required. Hybrid genetic search operators have been developed to improve the performance of the genetic algorithm by exploiting problem-specific features. The multiobjective genetic algorithm is formulated around the concept of Pareto optimality which enables the algorithm to search in parallel for different objectives. When the approach is applied without constraining the number of beams, the solution produces an indication of the minimum number of beams required. It is also possible to obtain non-dominated solutions for various numbers of beams, thereby giving the clinicians a choice in terms of the number of beams as well as in the orientation of these beams.

Algorithms↗

PubMed2005

Derivation of the distribution of extrafocal radiation for head scatter factor calculation.

Head scatter factors for high energy photon beams from linear accelerators can be modeled using a two-source model consisting of focal and extrafocal radiation. The focal radiation can be approximated as a point source, and the distribution of the extrafocal radiation is a two-dimensional (2D) radial symmetric function. Various methods, including analytical, Monte Carlo, and empirical trial functions, have been used to determine the radial symmetric function of extrafocal radiation distribution. This article describes a method for directly determining the extrafocal radiation distribution without assuming any empirical trial function. The extrafocal radiation distribution is determined with measured head scatter factors for rectangular fields defined by the lower jaw (X) fixed at 40 cm and the upper jaw (Y) varying from 3 to 40 cm. The derivatives of the measured head scatter factors, with respect to the Y jaw position projected in the plane of extrafocal radiation, are proportional to the one-dimensional (1D) projection (also called the line spread function) of the extrafocal radiation distribution. Two methods are used to solve the radial function of extrafocal radiation from the 1D projection. The first method uses a 2D filtered backprojection algorithm, originally developed for parallel beam computed tomography reconstruction, to directly derive the radial dependence of the extrafocal radiation distribution. The method has been applied to 6 and 18 MV photon beams from a Siemens linear accelerator and has been tested by comparing measured and calculated head scatter factors for square and rectangular fields. The second method uses a Fourier transform followed by a Fourier-Bessel transform to solve the problem. The distributions of extrafocal radiation derived from these two methods are virtually identical.

Algorithms↗

PubMed1998

New phylogenetic venues opened by a novel implementation of the DNAml algorithm.

SUMMARY: This note describes the parallelization of a key biological application, such as the construction of phylogenetic trees, using the DNAml program. A careful run-time analysis allowed us to propose an efficient parallelization that scaled very well to large problem sizes. AVAILABILITY: By anonymous ftp at ftp.ac.uma. es (/pub/ots/pDNAml) or from our web site http://www.cnb.uam. es/www/software/software_index.html CONTACT: ots@ac.uma.es

Algorithms↗