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

PubMed1979

Utilization of cross-plane rays for three-dimensional reconstruction by filtered back-projection.

Present popular computed tomography (CT) algorithms reconstruct an object from the ray measurements lying on a set of parallel planes. This paper presents an algorithm that can also utilize "cross-plane" rays (i.e., rays that cross through many planes) to reconstruct the object. In this reconstruction algorithm, the ray measurements are grouped into two-dimensional projections, filtered, and stored. The filtered projections can then be back-projected onto a three-dimensional matrix or any plane through the three-dimensional volume. General theoretical aspects are presented and then applied to the special case in which ray measurements have been made in all directions. The algorithm is tested using computer-generated data. Expressions for the noise power spectrum and the variance in the reconstruction are derived. It is shown that the noise-to-signal ratio per detected photon for this reconstruction method is close to a theoretical limit, as it also is for normal CT. The ability to use ray measurements that cross many planes is especially useful in emission CT, where order-of-magnitude improvements in image quality per unit dose can be achieved.

Computers↗

PubMed1991

Fast space-filling molecular graphics using dynamic partitioning among parallel processors.

We present a novel algorithm for the efficient generation of high-quality space-filling molecular graphics that is particularly appropriate for the creation of the large number of images needed in the animation of molecular dynamics. Each atom of the molecule is represented by a sphere of an appropriate radius, and the image of the sphere is constructed pixel-by-pixel using a generalization of the lighting model proposed by Porter (Comp. Graphics 1978, 12, 282). The edges of the spheres are antialiased, and intersections between spheres are handled through a simple blending algorithm that provides very smooth edges. We have implemented this algorithm on a multiprocessor computer using a procedure that dynamically repartitions the effort among the processors based on the CPU time used by each processor to create the previous image. This dynamic reallocation among processors automatically maximizes efficiency in the face of both the changing nature of the image from frame to frame and the shifting demands of the other programs running simultaneously on the same processors. We present data showing the efficiency of this multiprocessing algorithm as the number of processors is increased. The combination of the graphics and multiprocessor algorithms allows the fast generation of many high-quality images.

Algorithms↗

PubMed1991

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 develops a straightforward but effective algorithm for molecular dynamics simulations 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↗

PubMedDate not supplied

Projection domain compensation of missing angles for fan-beam CT reconstruction.

An improved method is proposed for fan-beam computed tomographic (CT) reconstruction from data with limited views. Compensation for the missing projections for fan-beam CT can be partially accomplished by using the coincident ray or by an interpolation technique using circular sample theory. In this article, the authors propose a more accurate compensation method for the missing projections whether the coincident ray pairs exist or not. The fan-beam reprojection algorithm, which is the inverse operator of the convolution filter, was extended from the projection space iteration reconstruction-reprojection (PSIRR) in parallel beam geometry. In addition, this algorithm was validated by applying the Shepp-Logan phantom for a computer simulation in the equi-angular fan-beam CT geometry.

Algorithms↗

PubMed1991

Computer systems for three-dimensional diagnostic imaging: an examination of the state of the art.

This survey reviews three-dimensional (3D) medical imaging machines and 3D medical imaging operations. The survey is designed to provide a snapshot overview of the present state of computer architectures for 3D medical imaging. The basic volume manipulation, object segmentation, and graphics operations required of a 3D medical imaging machine are described and sample algorithms are presented. The architecture and 3D imaging algorithms employed in 11 machines which render medical images are assessed. The performance of the machines is compared across several dimensions, including image resolution, elapsed time to form an image, imaging algorithms employed in the machine, and the degree of parallelism employed in the architecture. The innovation in each machine, whether architectural or algorithmic, is described in detail. General trends for future developments in this field are delineated and an extensive bibliography is provided.

Computer Systems↗

PubMed1991

Efficient detection of three-dimensional structural motifs in biological macromolecules by computer vision techniques.

Macromolecules carrying biological information often consist of independent modules containing recurring structural motifs. Detection of a specific structural motif within a protein (or DNA) aids in elucidating the role played by the protein (DNA element) and the mechanism of its operation. The number of crystallographically known structures at high resolution is increasing very rapidly. Yet, comparison of three-dimensional structures is a laborious time-consuming procedure that typically requires a manual phase. To date, there is no fast automated procedure for structural comparisons. We present an efficient O(n3) worst case time complexity algorithm for achieving such a goal (where n is the number of atoms in the examined structure). The method is truly three-dimensional, sequence-order-independent, and thus insensitive to gaps, insertions, or deletions. This algorithm is based on the geometric hashing paradigm, which was originally developed for object recognition problems in computer vision. It introduces an indexing approach based on transformation invariant representations and is especially geared toward efficient recognition of partial structures in rigid objects belonging to large data bases. This algorithm is suitable for quick scanning of structural data bases and will detect a recurring structural motif that is a priori unknown. The algorithm uses protein (or DNA) structures, atomic labels, and their three-dimensional coordinates. Additional information pertaining to the structure speeds the comparisons. The algorithm is straightforwardly parallelizable, and several versions of it for computer vision applications have been implemented on the massively parallel connection machine. A prototype version of the algorithm has been implemented and applied to the detection of substructures in proteins.

Algorithms↗

PubMed1990

Solution structure of the DNA-binding domain of the yeast transcriptional activator protein GCN4.

The solution structure of an active synthetic peptide containing both the leucine zipper and the adjacent basic domain of the yeast transcription factor GCN4 (residues 220-280) was determined by NMR. The two domains show structurally distinct behaviours. In the absence of DNA, the basic domain is, although very flexible, structured and fluctuating around a helical conformation. The leucine zipper region forms a long, uninterrupted helix. From a suitable set of NMR distances the three-dimensional structure of the leucine zipper monomeric sub-domain was calculated by distance geometry algorithms. The structure of the symmetrical parallel dimer was obtained by model building using the NMR information. A smaller peptide with the sequence of the isolated basic region (residues 1-35 of the 61 residue peptide) was also synthesized. Circular dichroism studies showed 30-40% helicity. A flexible helix spans the region between residues 8 and 21. The comparison of our results with suggested models is discussed in detail.

Algorithms↗

PubMed1989

Phase I trial using adaptive control dosing of hexamethylene bisacetamide (NSC 95580).

Hexamethylene bisacetamide (HMBA), a potent differentiating agent, was administered to patients with refractory malignant tumors. Thirteen patients received 30 evaluable courses. HMBA was given by continuous i.v. infusion for 5 days. Therapy was repeated every 28 days, if patients had recovered from toxicity. The starting dose was 24 g/m2/day. Because our previous trial had shown wide interpatient variability in HMBA pharmacokinetics and excess toxicity at HMBA plasma concentrations greater than 2 mM (HMBA doses between 24 and 33.6 g/m2/day), we attempted to individualize each patient's dose based on a dosing scheme using an adaptive (feedback) control algorithm, which assumed linear clearance for HMBA. In all courses, a plasma sample was assayed daily and infusion rates were adjusted to achieve an HMBA plasma concentration of 1.5-2.0 mM (300-400 mg/liter). The patients included 12 men and 1 woman with a median age of 56 years (range, 34-76) and median Karnofsky performance status of 90% (range, 60-100). All patients had received prior chemotherapy and 9 patients had also received radiation therapy. The linear adaptive control algorithm was reasonably precise, with a mean absolute error of 0.28 (SE 0.04) mM. However, adjustments in infusion rate systematically overshot the desired change in steady state concentration, probably due to nonlinear clearance of HMBA. For levels within 24 h of a change in infusion rate, this resulted in significant bias, with a mean error of 0.24 (SE 0.09) mM. The mean absolute error was 0.40 (SE 0.06) mM. A second adaptive control algorithm, using a pharmacokinetic model with parallel first-order (renal) clearance and Michaelis-Menten (nonrenal) clearance and using Bayesian parameter estimation with a priori estimates based on our previous phase I trial, proved to be much more precise than the linear method and was unbiased when applied retrospectively to the same observations, with a mean error (within 24 h of a change in infusion rate) of 0.02 (SE 0.06) mM and a mean absolute error of 0.22 (SE 0.03) mM. Toxicity was reversible in all cases. Neurotoxicity, consisting of hallucinations, agitation, somnolence, or confusion, was seen in 2 patients. Four patients complained of insomnia or anxiety. Mild asymptomatic acidosis was seen in 3 patients. Other toxicity included grade 1-2 nausea and vomiting (10 patients), grade 2 diarrhea (2 patients), grade 3 thrombocytopenia (3 patients), grade 1-3 leukopenia (3 patients), and oral herpes simplex infection (4 patients). Mild reversible renal insufficiency (measured by creatinine clearance) was seen in 8 patients.(ABSTRACT TRUNCATED AT 400 WORDS)

Acetamides↗

PubMed1990

Hypermedia and randomized algorithms for medical expert systems.

KNET is an environment for constructing probabilistic, knowledge-intensive systems within the axiomatic framework of decision theory. The KNET architecture defines a complete separation between the hypermedia user interface on the one hand, and the representation and management of expert opinion on the other. KNET offers a choice of algorithms for probabilistic inference. We and our coworkers have used KNET to build consultation systems for lymph-node pathology, bone-marrow transplantation therapy, clinical epidemiology, and alarm management in the intensive-care unit. Most important, KNET contains a randomized approximation scheme (RAS) for the difficult and almost certainly intractable problem of Bayesian inference. Our algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models of medical diagnosis. In this article, we describe the architecture of KNET, construct a randomized algorithm for probabilistic inference, and analyze the algorithm's performance. Finally, we characterize our algorithms' empiric behavior and explore its potential for parallel speedups. From design to implementation, then, KNET demonstrates the crucial interaction between theoretical computer science and medical informatics.

Algorithms↗

PubMed1991

Multiresolution, error-convergence halftone algorithm.

A new halftone algorithm is described. The algorithm is designed for implementation on a parallel architecture in order to provide fast, progressive coding of moderate-resolution images. The design is based on a multiresolution, hierarchical, pyramidal structure. At each pyramid level, the binarized image is compared with the original, gray-tone image over a successively larger window of pixels for calculation of a weighted averaged error. Within each level, selected binarized pixels are tested for possible changes in the binary assignment. The binary assignment is changed if the change results in a lower average error over the entire window. Varying the selection of test pixels can cause the same process to provide clustered-dot patterns and dithering. A comparison of performance with the best implementation of the error-propagation algorithm is presented visually. Quality is compared also in terms of isotropy of the texture and the appropriate blue-noise characteristics in areas of uniform gray tone. The benefits of this algorithm are realized with moderate-resolution display of the order of 512 dots X 512 dots. The processing can be carried out on smaller blocks since the results can be combined without any visible seams or edge effects.

Algorithms↗

PubMed1991

Scanning protein sequence databanks using a distributed processing workstation network.

The programme pscan has been developed to distribute protein databank scans over a network of computers that share a common file system. pscan may be used in conjunction with most conventional sequence comparison programmes with few modifications. In test runs using the Smith-Waterman dynamic programming algorithm, the time required to scan a 6858 sequence databank using a query sequence 740 residues long was reduced from approximately 50 min for a single processor, to approximately 11 minutes for five processors. Accordingly, pscan provides a low-cost, portable alternative to dedicated parallel processing computers.

Algorithms↗

PubMed1991

Bayesian image reconstruction for emission tomography incorporating Good's roughness prior on massively parallel processors.

Since the introduction by Shepp and Vardi [Shepp, L. A. & Vardi, Y. (1982) IEEE Trans. Med. Imaging 1, 113-121] of the expectation-maximization algorithm for the generation of maximum-likelihood images in emission tomography, a number of investigators have applied the maximum-likelihood method to imaging problems. Though this approach is promising, it is now well known that the unconstrained maximum-likelihood approach has two major drawbacks: (i) the algorithm is computationally demanding, resulting in reconstruction times that are not acceptable for routine clinical application, and (ii) the unconstrained maximum-likelihood estimator has a fundamental noise artifact that worsens as the iterative algorithm climbs the likelihood hill. In this paper the computation issue is addressed by proposing an implementation on the class of massively parallel single-instruction, multiple-data architectures. By restructuring the superposition integrals required for the expectation-maximization algorithm as the solutions of partial differential equations, the local data passage required for efficient computation on this class of machines is satisfied. For dealing with the "noise artifact" a Markov random field prior determined by Good's rotationally invariant roughness penalty is incorporated. These methods are demonstrated on the single-instruction multiple-data class of parallel processors, with the computation times compared with those on conventional and hypercube architectures.

Algorithms↗

PubMed1989

[Radial long-axis tomography: a new reconstructing algorithm for thallium-201 myocardial SPECT].

The long-axis (L-A) tomograms of the heart in thallium-201 SPECT have been conventionally reconstructed as those parallel to the midventricular vertical or horizontal L-A plane. We developed a new algorithm for reconstructing the rotated L-A tomograms around the L-A to longitudinally observe thallium-201 myocardial distribution and to provide an optimal view of the cardiac apex. After determining the orientation of the L-A and reconstructing the short-axis (S-A) tomograms using standard techniques, the coordinates of the S-A planes were transformed to the polar coordinates whose origin is located at the position of the L-A in each plane. Then, "radial L-A tomograms", i.e. midventricular L-A planes oriented at the angle of every 6 degrees to the midventricular horizontal L-A plane, were reconstructed. Also, we developed a new technique for analyzing thallium-201 distribution of the L-A tomograms. For the basal 2/3 regions, two profiles which consist of the pixels with maximum count on the upper and lower myocardial portions of the lines (spaced at 1 pitch) vertically to the L-A were computed. For the remaining apical 1/3 regions, the semi-circumferential maximum-count profile from the values of 30 radii spaced at 6 degrees interval were computed. Based on these profiles, a 2D polar representation was then generated. From the study using a cardiac phantom with an apical small infarction, the usefulness of this new tomographic method for the detection of apical myocardial ischemia was demonstrated. The application to the exercise/redistribution studies in patients with effort angina indicated that radial long-axis tomography provides precise information about the longitudinal extent of perfusion defects, particularly in the apical regions.

Algorithms↗

PubMed1989

Supercomputers and biological sequence comparison algorithms.

Comparison of biological (DNA or protein) sequences provides insight into molecular structure, function, and homology and is increasingly important as the available databases become larger and more numerous. One method of increasing the speed of the calculations is to perform them in parallel. We present the results of initial investigations using two dynamic programming algorithms on the Intel iPSC hypercube and the Connection Machine as well as an inexpensive, heuristically-based algorithm on the Encore Multimax.

Algorithms↗

PubMed1979

Application of optimized parallel processing digital computers and numerical approximation methods to the ultra high-speed three-dimensional reconstruction of the intact thorax.

In order to achieve the computational capability to carry out many thousands of cross-sectional reconstructions, necessary to support a prototype high temporal and spatial resolution cylindrical scanning multiaxial tomographic unit, a series of design, software simulation, and fabrication studies is underway to develop a special-purpose high-speed reconstruction computer. This processor will rely upon integrated circuit arithmetic components of advanced design, and highly parallel architecture to execute X-ray based transaxial reconstruction algorithms at the rate of hundreds of cross sections/sec.

Computers↗

PubMed1979

Whole-body single-photon emission computed tomography using dual, large-field-of-view scintillation cameras.

A whole-body single-photon emission computed tomography system (SPECT) consisting of two large-field-of-view scintillation cameras mounted on a rotatable gantry, a minicomputer and a display station has been designed, constructed and evaluated. In its usual mode of operation, eleven contiguous transverse sections, each 12.5 or 25 mm thick, are reconstructed from projection data acquired during a single, continuous 360 degree rotation lasting from 2 to 22 min. A generalised filtered and weighted backprojection algorithm is used to reconstruct data obtained with conventional parallel-hole collimators in the case of body scanning, or with specially designed fan beam collimators in the case of centrally positioned organs. A simple, yet effective, correction is used to compensate for the effects of gamma ray attenuation within the patient. In addition to providing transverse section images, the system is capable of simultaneous acquisition of opposed conventional scintigrams, the reconstruction of longitudinal section images, and the acquisition of gated cardiac transverse sections. Resolutions in the reconstructed images are typically 15 mm for body scans and 11 mm for brain scans, with only slight variations in sensitivity and resolution within the image. Phantoms and clinical data demonstrate that the SPECT system generates high quality section images while maintaining most of the flexibility of normal scintillation cameras, with the added advantage of dual heads.

Tomography, Emission-Computed↗

PubMed1992

[Online control of evaluation algorithms of the image applied to identification of deglutition function].

Comprehensive software and hardware have been developed for the processing of biosignals. Such automatic signal processing, however not only has advantages, but also drawbacks. The question as to the reliability of the evaluation algorithm arises when the signal is modified, in the presence of interindividual differences, and in particular when noise is superimposed. This is of great interest for long-term recording when the original signal can no longer be inspected visually. The aim of our work was to display the signals on the screen of a monitor simultaneously with lines marking the points (start, end, extreme value, etc.) processed by the specific signal processing algorithm. The program package permits the on-line recording and monitoring of signals, the parallel processing and marking of detected events on the monitor, as well as storage of the parameters extracted. It is a very effective tool for developing, improving and monitoring of algorithms and their efficiency for signal processing.

Algorithms↗

PubMed1990

Self-organising learning control and its application to muscle relaxant anaesthesia.

The concept of a self-organising control system is attractive in biomedicine because of the imprecise nature of available physiological models. In this paper a particular strategy called a self-organising controller (SOC) originating from the work of Barron on aerospace systems is applied to the control of muscle relaxant anaesthesia. The SOC algorithm, which requires no prior knowledge of system dynamics, is described, both in single variable and multivariable format. Simulation results are presented for SOC performance on a well-established pancuronium model. Three implementations are described, being the use of a general purpose language, a SUN workstation approach, and a parallel computer transputer solution. The latter approach becomes important for multivariable control because of the computing-intensive nature of SOC. The transputer is shown to be a suitable vehicle for implementation in terms of speed and parallelism for SOC.

Algorithms↗