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 109 records · Page 6Linked to original sources

PubMed2004

A strategy for assembling the maize (Zea mays L.) genome.

UNLABELLED: Because the bulk of the maize (Zea mays L.) genome consists of repetitive sequences, sequencing efforts are being targeted to its 'gene-rich' fraction. Traditional assembly programs are inadequate for this approach because they are optimized for a uniform sampling of the genome and inherently lack the ability to differentiate highly similar paralogs. RESULTS: We report the development of bioinformatics tools for the accurate assembly of the maize genome. This software, which is based on innovative parallel algorithms to ensure scalability, assembled 730,974 genomic survey sequences fragments in 4 h using 64 Pentium III 1.26 GHz processors of a commodity cluster. Algorithmic innovations are used to reduce the number of pairwise alignments significantly without sacrificing quality. Clone pair information was used to estimate the error rate for improved differentiation of polymorphisms versus sequencing errors. The assembly was also used to evaluate the effectiveness of various filtering strategies and thereby provide information that can be used to focus subsequent sequencing efforts.

Algorithms↗

PubMed1986

Mammalian phylogeny: comparison of morphological and molecular results.

In an attempt to resolve the "bushy" part at the root of the eutherian tree, 182 nondental morphological characters from 100 species (79 extant and 21 extinct; 98 mammalian and 2 nonmammalian) were analyzed using two maximum-parsimony tree-building algorithms. Parallel analyses of 2,258 pairwise immunodiffusion comparisons with chicken antisera on 101 mammalian species and of amino acid sequence data of alpha and beta hemoglobins and other published protein sequences were also carried out. The morphological and molecular phylogenies agree in depicting the infraclass Eutheria as consisting of five major clades (thus resolving part of the "bush"). Rates of evolution were also found to be similar in the two types of phylogenies.

Amino Acid Sequence↗

PubMed2004

Structural and computational depth of diffusion-limited aggregation.

Diffusion-limited aggregation (DLA) is studied from the perspective of computational complexity. A parallel algorithm is exhibited that requires a number of steps that scales as the depth of the tree defined by the cluster. The existence of this algorithm suggests a connection between a fundamental computational and structural property of DLA.

Algorithms↗

PubMed1995

Phase refinement and extension by means of non-crystallographic symmetry averaging using parallel computers.

Electron-density averaging, fast Fourier synthesis and fast Fourier analysis programs have been adapted for parallel-computing systems. These have been linked to perform iterative phase improvement and extension utilizing non-crystallographic symmetry and solvent flattening. Various strategies for parallel algorithms have been tested on a variety of computers as a function of the number of computer nodes. Some experimental timing results are discussed.

Journal Article↗

PubMed2001

Visualization of computer simulated heart temperature during topical cooling.

A local hypothermia is often used during cardiac operations to slow down the tissue metabolism. The heart is cooled down with cold cardioplegic solution. Sometimes even the topical cooling with or without ice slush is used. Different heart models have been used earlier to simulate heart temperature distribution, but the resolution of the model has always been limited by the speed of the computer. We used the computer heart model derived from Visible Human Dataset with the spatial resolution of 1 mm. In this article, the step-by-step generation of 3D computer heart model is described. The heat transfer was modeled by a diffusion equation that was discretised in space and time and solved by a parallel algorithm. Finally, the cooling of heart during an operation, with and without topical ice slush, was simulated on a cluster of 9 PC-based computers, which assured sufficient computing power. The simulated results are presented as images of cross sections in different planes with temperatures shown by different colors.

Body Temperature↗

PubMed1992

Impact of massively parallel computation on protein structure determination.

For the past two decades, an important paradigm in protein chemistry has been the assertion that a biologically active protein is at thermodynamic equilibrium and therefore adopts its minimum free energy structure. Although some evidence now suggests that not all proteins conform to this notion, it is true often enough to remain an important guiding principle in structure determination, whether by direct computation or by the computationally assisted approaches of diffraction and resonance. Among the difficulties in predicting structure from sequence are the lack of a useful potential function incorporating the influence of solvent and the inability to sample the phase space efficiently or even to determine whether a free energy minimum is, in fact, the global minimum. These problems are general. Although they are greatly mitigated by experimental information, they become increasingly severe as empirical constraints are reduced. We review the difficulties involved in the general problem of protein structure prediction and discuss the impact of increased computer power in the context of new approaches to solvation and parallel algorithm design. A general focus of our discussion is the need to understand the theoretical basis for effective theories and to accommodate in numerical methods the interplay of different temporal and spatial scales.

Algorithms↗

PubMed2003

Single breath-hold real-time cine MR imaging: improved temporal resolution using generalized autocalibrating partially parallel acquisition (GRAPPA) algorithm.

The purpose of this study was to test parallel imaging techniques for improvement of temporal resolution in multislice single breath-hold real-time cine steady-state free precession (SSFP) in comparison with standard segmented single-slice SSFP techniques. Eighteen subjects were examined on a 1.5-T scanner using a multislice real-time cine SSFP technique using the GRAPPA algorithm. Global left ventricular parameters (EDV, ESV, SV, EF) were evaluated and results compared with a standard segmented single-slice SSFP technique. Results for EDV ( r=0.93), ESV ( r=0.99), SV ( r=0.83), and EF ( r=0.99) of real-time multislice SSFP imaging showed a high correlation with results of segmented SSFP acquisitions. Systematic differences between both techniques were statistically non-significant. Single breath-hold multislice techniques using GRAPPA allow for improvement of temporal resolution and for accurate assessment of global left ventricular functional parameters.

Algorithms↗

PubMed2005

A parallel-line detection algorithm based on HMM decoding.

The detection of groups of parallel lines is important in applications such as form processing and text (handwriting) extraction from rule lined paper. These tasks can be very challenging in degraded documents where the lines are severely broken. In this paper, we propose a novel model-based method which incorporates high-level context to detect these lines. After preprocessing (such as skew correction and text filtering), we use trained Hidden Markov Models (HMM) to locate the optimal positions of all lines simultaneously on the horizontal or vertical projection profiles, based on the Viterbi decoding. The algorithm is trainable so it can be easily adapted to different application scenarios. The experiments conducted on known form processing and rule line detection show our method is robust, and achieves better results than other widely used line detection methods.

Algorithms↗

PubMed2004

A parallel graph decomposition algorithm for DNA sequencing with nanopores.

MOTIVATION: With the potential availability of nanopore devices that can sense the bases of translocating single-stranded DNA (ssDNA), it is likely that 'reads' of length approximately 10(5) will be available in large numbers and at high speed. We address the problem of complete DNA sequencing using such reads. We assume that approximately 10(2) copies of a DNA sequence are split into single strands that break into randomly sized pieces as they translocate the nanopore in arbitrary orientations. The nanopore senses and reports each individual base that passes through, but all information about orientation and complementarity of the ssDNA subsequences is lost. Random errors (both biological and transduction) in the reads create further complications. RESULTS: We have developed an algorithm that addresses these issues. It can be considered an extreme variation of the well-known Eulerian path approach. It searches over a space of de Bruijn graphs until it finds one in which (a) the impact of errors is eliminated and (b) both possible orientations of the two ssDNA sequences can be identified separately and unambiguously. Our algorithm is able to correctly reconstruct real DNA sequences of the order of 10(6) bases (e.g. the bacterium Mycoplasma pneumoniae) from simulated erroneous reads on a modest workstation in about 1 h. We describe, and give measured timings of, a parallel implementation of this algorithm on the Cray Multithreaded Architecture (MTA-2) supercomputer, whose architecture is ideally suited to this 'unstructured' problem. Our parallel implementation is crucial to the problem of rapidly sequencing long DNA sequences and also to the situation where multiple nanopores are used to obtain a high-bandwidth stream of reads.

Algorithms↗

PubMed1991

Parallel computation and FASTA: confronting the problem of parallel database search for a fast sequence comparison algorithm.

We have parallelized the FASTA algorithm for biological sequence comparison using Linda, a machine-independent parallel programming language. The resulting parallel program runs on a variety of different parallel machines. A straight-forward parallelization strategy works well if the amount of computation to be done is relatively large. When the amount of computation is reduced, however, disk I/O becomes a bottleneck which may prevent additional speed-up as the number of processors is increased. The paper describes the parallelization of FASTA, and uses FASTA to illustrate the I/O bottleneck problem that may arise when performing parallel database search with a fast sequence comparison algorithm. The paper also describes several program design strategies that can help with this problem. The paper discusses how this bottleneck is an example of a general problem that may occur when parallelizing, or otherwise speeding up, a time-consuming computation.

Algorithms↗

PubMed2005

A model-based parallel origin and orientation refinement algorithm for cryoTEM and its application to the study of virus structures.

We present a model-based parallel algorithm for origin and orientation refinement for 3D reconstruction in cryoTEM. The algorithm is based upon the Projection Theorem of the Fourier Transform. Rather than projecting the current 3D model and searching for the best match between an experimental view and the calculated projections, the algorithm computes the Discrete Fourier Transform (DFT) of each projection and searches for the central section ("cut") of the 3D DFT that best matches the DFT of the projection. Factors that affect the efficiency of a parallel program are first reviewed and then the performance and limitations of the proposed algorithm are discussed. The parallel program that implements this algorithm, called PO(2)R, has been used for the refinement of several virus structures, including those of the 500 Angstroms diameter dengue virus (to 9.5 Angstroms resolution), the 850 Angstroms mammalian reovirus (to better than 7A), and the 1800 Angstroms paramecium bursaria chlorella virus (to 15 Angstroms).

Algorithms↗

PubMed2001

Clinical evaluation of morphology discrimination: an algorithm for rhythm discrimination in cardioverter defibrillators.

The aim of this study was to test the new morphology discrimination diagnostic algorithm for ICDs that differentiates supraventricular tachycardias (SVTs) from VTs by analysis of ventricular depolarization complexes morphology. Twenty-five patients implanted with a St. Jude Ventritex single chamber ICD were studied during electrophysiological evaluation at predischarge and were followed for 7 +/- 4 months. Sensitivity and specificity for VT detection and overall diagnostic accuracy of the morphology discrimination algorithm were calculated on 326 detected events. At electrophysiological evaluation, the algorithm was tested during 67 episodes of right atrial pacing, during 119 episodes of RV pacing (at basal interventricular septum and RV apex) and during 27 episodes of sustained AF: specificity was 98%, sensitivity was 66%, and diagnostic accuracy was 80%. All episodes of AF were correctly diagnosed as SVT. Exclusion of detections related to pacing at the basal interventricular septum, resulted in a specificity of 98%, a sensitivity of 85%, and a diagnostic accuracy of 93%. During follow-up, evaluation of the morphology discrimination algorithm on 113 spontaneous episodes (31 VTs, 31 AF, 7 SVTs, and 44 sinus tachycardias) exhibited a specificity of 89%, a sensitivity of 100%, and a diagnostic accuracy of 92%. In conclusion, the morphology discrimination algorithm exhibits a high specificity in discriminating VTs from SVTs, although with a corresponding reduction in sensitivity. The preliminary experience on spontaneous episodes is promising. To correct for the reduction in sensitivity, it is advisable to use this algorithm in parallel with other algorithms for rhythm discrimination (sudden onset, stability) coupled with extended high rate.

Adult↗

PubMed1990

Physiologic trend detection and artifact rejection: a parallel implementation of a multi-state Kalman filtering algorithm.

Using a parallel implementation of the multi-state Kalman filtering algorithm, we have developed an accurate method of reliably detecting and identifying trends, abrupt changes, and artifacts from multiple physiologic data streams in real-time. The Kalman filter algorithm was implemented within an innovative software architecture for parallel computation: a parallel process trellis. Examples, processed in real-time, of both simulated and actual data serve to illustrate the potential value of the Kalman filter as a tool in physiologic monitoring.

Algorithms↗

PubMed1993

SIMD parallelization of the WORDUP algorithm for detecting statistically significant patterns in DNA sequences.

The development of new techniques in sequencing nuclei acids has produced a great amount of sequence data and has led to the discovery of new relationships. In this paper, we study a method for parallelizing the algorithm WORDUP, which detects the presence of statistically significant patterns in DNA sequences. WORDUP implements an efficient method to identify the presence of statistically significant oligomers in a non-homologous group of sequences. It is based on a modified version of the Boyer-Moore algorithm, which is one of the fastest algorithms for string matching available in the literature. The aim of the parallel version of WORDUP presented here is to speed up the computational time and allow the analysis of a greater set of longer nucleotide sequences, which is usually impractical with sequential algorithms.

Algorithms↗

PubMed2002

New method for parallel computation of Hessian matrix of conformational energy function in internal coordinates.

A new algorithm for parallel calculation of the second derivatives (Hessian) of the conformational energy function of biomolecules in internal coordinates is proposed. The basic scheme of this algorithm is the division of the entire calculation of the Hessian matrix (called "task") into subtasks and the optimization of the assignment of processors to each subtask by considering both the load balancing and reduction of the communication cost. A genetic algorithm is used for this optimization considering the dependencies between subtasks. We applied this method to a glutaminyl transfer RNA (Gln-tRNA) molecule for which the scalability of our previously developed parallel algorithm was significantly decreased when the large number of processors was used. The speedup for the calculation was 32.6 times with 60 processors, which is considerably better than the speedup for our previously reported parallel algorithm. The elapsed time for the calculation of subtasks, data sending, and data receiving was analyzed, and the effect of the optimization using the genetic algorithm is discussed.

Algorithms↗

PubMed2002

Parallel image restoration with a two-dimensional likelihood-based algorithm.

We describe a pixelwise parallel algorithm for the restoration of images that have been corrupted by a low-pass optical channel and additive noise. This new algorithm is based on an iterative soft-decision method of error correction (i.e., turbo decoding) and offers performance on binary-valued imagery that is comparable to the Viterbi algorithm. We quantify the restoration performance of this new algorithm on random binary imagery for which it is superior to both the Wiener filter and the projection onto convex sets algorithms over a wide range of channels. For typical optical channels, the new algorithm is within 0.5 dB of the two-dimensional Viterbi restoration method [J. Opt. Soc. Am. A 17, 265 (2000)]. We also demonstrate the extension of our new algorithm to correlated and gray-scale images using vector quantization to mitigate the associated complexity burden. A highly parallel focal-plane implementation is also discussed, and a design study is presented to quantify the capabilities of such a VLSI hardware solution. We find that video-rate restoration on 252 x 252 pixel images is possible using current technology.

Journal Article↗

PubMed2006

Parallel asynchronous particle swarm optimization.

The high computational cost of complex engineering optimization problems has motivated the development of parallel optimization algorithms. A recent example is the parallel particle swarm optimization (PSO) algorithm, which is valuable due to its global search capabilities. Unfortunately, because existing parallel implementations are synchronous (PSPSO), they do not make efficient use of computational resources when a load imbalance exists. In this study, we introduce a parallel asynchronous PSO (PAPSO) algorithm to enhance computational efficiency. The performance of the PAPSO algorithm was compared to that of a PSPSO algorithm in homogeneous and heterogeneous computing environments for small- to medium-scale analytical test problems and a medium-scale biomechanical test problem. For all problems, the robustness and convergence rate of PAPSO were comparable to those of PSPSO. However, the parallel performance of PAPSO was significantly better than that of PSPSO for heterogeneous computing environments or heterogeneous computational tasks. For example, PAPSO was 3.5 times faster than was PSPSO for the biomechanical test problem executed on a heterogeneous cluster with 20 processors. Overall, PAPSO exhibits excellent parallel performance when a large number of processors (more than about 15) is utilized and either (1) heterogeneity exists in the computational task or environment, or (2) the computation-to-communication time ratio is relatively small.

Journal Article↗

PubMed2006

High-resolution continuously acquired peripheral MR angiography featuring partial parallel imaging GRAPPA.

Continuously-moving-table MRI, in contrast to traditional multistation techniques, potentially can improve the scan time efficiency of whole-body applications and provide seamless images of an extended field of view (FOV). Contrast-enhanced MR angiography (CE-MRA) in particular requires high spatial resolution and at the same time has rigid scan time constraints due to the limited arterial contrast window. In this study a reconstruction method for continuously acquired 3D data sets during table movement was combined with a self-calibrated partial parallel imaging algorithm (generalized autocalibrating partially parallel acquisitions (GRAPPA)). The method was applied to peripheral CE-MRA and compared with a standard continuously-moving-table MRA protocol. The gain in scan time was used to increase the data acquisition matrix and decrease the slice thickness. The method was evaluated in five healthy volunteers and applied to one patient with peripheral arterial occlusive disease (PAOD). The protocols were intraindividually compared with respect to the signal-to-noise ratio (SNR) and contrast-to-noise ratio (CNR) in selected vessel segments, as well as overall vessel depiction. The combination of the continuously-moving-table technique with parallel imaging enabled the acquisition of seamless peripheral 3D MRA with increased resolution and an overall crisper appearance.

Algorithms↗