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 523 records · Page 29Linked to original sources

PubMed2001

Life and evolution in computers.

This paper argues for the possibility of 'artificial life' and computational evolution, first by discussing (via a highly simplified version) John von Neumann's self-reproducing automation and then by presenting some recent work focusing on computational evolution, in which 'cellular automata', a form of parallel and decentralized computing system, are evolved via 'genetic algorithms'. It is argued that such in silico experiments can help to make sense of the question of whether we can eventually build computers that are intelligent and alive.

Algorithms↗

PubMed1995

Microscopic computation in human brain evolution.

When human psychological performance is viewed in terms of cognitive modules, our species displays remarkable differences in computational power. Algorithmically simple computations are generally difficult to perform, whereas optimal routing or "Traveling Salesman" Problems (TSP) of far greater complexity are solved on an everyday basis. It is argued that even "simple" instances of TSP are not purely Euclidian problems in human computations, but involve emotional, autonomic, and cognitive constraints. They therefore require a level of parallel processing not possible in a macroscopic system to complete the algorithm within a brief period of time. A microscopic neurobiological model emphasizing the computational power of excited atoms within the neuronal membrane is presented as an alternative to classical connectionist approaches. The evolution of the system is viewed in terms of specific natural selection pressures driving satisfying computations toward global optimization. The relationship of microscopic computation to the nature of consciousness is examined, and possible mathematical models as a basis for simulation studies are briefly discussed.

Algorithms↗

PubMed2005

GAME: a simple and efficient whole genome alignment method using maximal exact match filtering.

In this paper, we present a simple and efficient whole genome alignment method using maximal exact match (MEM). The major problem with the use of MEM anchor is that the number of hits in non-homologous regions increases exponentially when shorter MEM anchors are used to detect more homologous regions. To deal with this problem, we have developed a fast and accurate anchor filtering scheme based on simple match extension with minimum percent identity and extension length criteria. Due to its simplicity and accuracy, all MEM anchors in a pair of genomes can be exhaustively tested and filtered. In addition, by incorporating the translation technique, the alignment quality and speed of our genome alignment algorithm have been further improved. As a result, our genome alignment algorithm, GAME (Genome Alignment by Match Extension), performs competitively over existing algorithms and can align large whole genomes, e.g., A. thaliana, without the requirement of typical large memory and parallel processors. This is shown using an experiment which compares the performance of BLAST, BLASTZ, PatternHunter, MUMmer and our algorithm in aligning all 45 pairs of 10 microbial genomes. The scalability of our algorithm is shown in another experiment where all pairs of five chromosomes in A. thaliana were compared.

Algorithms↗

PubMed2006

Determination of daunomycin in human plasma and urine by using an interference-free analysis of excitation-emission matrix fluorescence data with second-order calibration.

Daunorubicin (DNR) is a significant antineoplastic antibiotic, which is usually applied to a chemotherapy of acute lymphatic and myelogenous leukaemia. Unfortunately, cardiotoxicity research in animals has indicated that DNR is cardiotoxic. Therefore, it is important to quantify DNR in biological fluids. A new algorithm, the alternating fitting residue (AFR) method, and the traditional parallel factor analysis (PARAFAC) have been utilized to directly determine DNR in human plasma and urine. These methodologies fully exploit the second-order advantage of the employed three-way fluorescence data, allowing the analyte concentrations to be quantified even in the presence of unknown fluorescent interferents. Furthermore, in contrast to PARAFAC, more satisfactory results were gained with AFR.

Algorithms↗

PubMed2006

A survey of methods for classification of gene expression data using evolutionary algorithms.

The rapid increase in the quantity of available biologic data over the last decade, brought about by the introduction of massively parallel methods for gene expression measurements, has highlighted the need for more efficient computational techniques for analysis. This paper reviews the use of evolutionary algorithms (EAs) in connection with classification based on gene expression data matrices. Brief introductions to data classification methods and EAs are given, followed by a survey of studies dealing with the application of evolutionary algorithms to various (cancer related) data sets. The general conclusion, based on the published results surveyed here, is that EAs may constitute an efficient method for optimal gene selection, and can also help in reducing the size (number of features used) of classifiers. In many cases, the classification accuracy obtained using EAs, often in conjunction with other methods, represents a significant improvement over results obtained without the use of EAs. However, long-term, independent clinical follow-up studies will be essential to validate prognostic markers identified by the use of EA-based methods.

Algorithms↗

PubMed2005

Towards the solution of the eluent elimination problem in high-performance liquid chromatography-infrared spectroscopy measurements by chemometric methods.

The high-performance liquid chromatography-infrared spectroscopy (HPLC-IR) technique utilizing on-line flow through cell (FTC) detection has an inherent practical problem: strong absorption bands of the eluent may mask valuable analytical regions of the IR spectrum. The experimentalists' answer to this challenge is physical elimination of the chromatographic eluent before spectroscopic detection, which however results in off-line measurement of spectra. In the present work, the capabilities of some chemometric algorithms using iteratively applied multi-way methods such as parallel factor analysis (PARAFAC) and PARAFAC2, developed with the aim of overcoming the problems of eluent elimination are examined and evaluated. Test calculations done on simulated liquid chromatographic infrared (LC-IR) data cubes have shown that although PARAFAC2 performs much better than the simple PARAFAC method, it does not give correct decompositions, just like multivariate curve resolution with alternative least squares (MCR-ALS) and related bilinear data based methods. In search for a better solution, a method named objective subtraction of solvent spectrum with iterative use of PARAFAC and PARAFAC2 (OSSS-IU-PARAFAC and OSSS-IU-PARAFAC2) has been developed. Calculations performed with the corresponding Matlab program developed by the authors and run with the appropriate functions in PLS_Toolbox yielded very promising results in evaluations of both simulated and real HPLC-IR data sets, after necessary data pretreatments.

Algorithms↗

PubMed2004

Evaluation of rapid HIV test kits on whole blood and development of rapid testing algorithm for voluntary testing and counseling centers in Ethiopia.

Five simple and rapid HIV antibody detection assays viz. Determine, Capillus, Oraquick, Unigold and Hemastrip were evaluated to examine their performance and to develop an alternative rapid test based testing algorithm for voluntary counseling and testing (VCT) in Ethiopia. All the kits were tested on whole blood, plasma and serum. The evaluation had three phases: Primary lab review, piloting at point of service and implementation. This report includes the results of the first two phases. A total of 2,693 specimens (both whole blood and plasma) were included in the evaluation. Results were compared to double Enzyme Linked Immuno-Sorbent Assay (ELISA) system. Discordant EIA results were resolved using Western Blot. The assays had very good sensitivities and specificities, 99-100%, at the two different phases of the evaluation. A 98-100% result agreement was obtained from those tested at VCT centers and National Referral Laboratory for AIDS (NRLA), in the quality control phase of the evaluation. A testing strategy yielding 100% [95% CI; 98.9-100.0] sensitivity was achieved by the sequential use of the three rapid test kits. Direct cost comparison showed serial testing algorithm reduces the cost of testing by over 30% compared to parallel testing in the current situation. Determine, Capillus/Oraquick (presence/absence of frefrigeration) and Unigold were recommended as screening, confirmation and tiebreaker tests, respectively.

AIDS Serodiagnosis↗

PubMed2003

Constructing large-scale genetic maps using an evolutionary strategy algorithm.

This article is devoted to the problem of ordering in linkage groups with many dozens or even hundreds of markers. The ordering problem belongs to the field of discrete optimization on a set of all possible orders, amounting to n!/2 for n loci; hence it is considered an NP-hard problem. Several authors attempted to employ the methods developed in the well-known traveling salesman problem (TSP) for multilocus ordering, using the assumption that for a set of linked loci the true order will be the one that minimizes the total length of the linkage group. A novel, fast, and reliable algorithm developed for the TSP and based on evolution-strategy discrete optimization was applied in this study for multilocus ordering on the basis of pairwise recombination frequencies. The quality of derived maps under various complications (dominant vs. codominant markers, marker misclassification, negative and positive interference, and missing data) was analyzed using simulated data with approximately 50-400 markers. High performance of the employed algorithm allows systematic treatment of the problem of verification of the obtained multilocus orders on the basis of computing-intensive bootstrap and/or jackknife approaches for detecting and removing questionable marker scores, thereby stabilizing the resulting maps. Parallel calculation technology can easily be adopted for further acceleration of the proposed algorithm. Real data analysis (on maize chromosome 1 with 230 markers) is provided to illustrate the proposed methodology.

Algorithms↗

PubMed2005

Practical conversion from torsion space to Cartesian space for in silico protein synthesis.

Many applications require a method for translating a large list of bond angles and bond lengths to precise atomic Cartesian coordinates. This simple but computationally consuming task occurs ubiquitously in modeling proteins, DNA, and other polymers as well as in many other fields such as robotics. To find an optimal method, algorithms can be compared by a number of operations, speed, intrinsic numerical stability, and parallelization. We discuss five established methods for growing a protein backbone by serial chain extension from bond angles and bond lengths. We introduce the Natural Extension Reference Frame (NeRF) method developed for Rosetta's chain extension subroutine, as well as an improved implementation. In comparison to traditional two-step rotations, vector algebra, or Quaternion product algorithms, the NeRF algorithm is superior for this application: it requires 47% fewer floating point operations, demonstrates the best intrinsic numerical stability, and offers prospects for parallel processor acceleration. The NeRF formalism factors the mathematical operations of chain extension into two independent terms with orthogonal subsets of the dependent variables; the apparent irreducibility of these factors hint that the minimal operation set may have been identified. Benchmarks are made on Intel Pentium and Motorola PowerPC CPUs.

Algorithms↗

PubMed2005

PARALIGN: rapid and sensitive sequence similarity searches powered by parallel computing technology.

PARALIGN is a rapid and sensitive similarity search tool for the identification of distantly related sequences in both nucleotide and amino acid sequence databases. Two algorithms are implemented, accelerated Smith-Waterman and ParAlign. The ParAlign algorithm is similar to Smith-Waterman in sensitivity, while as quick as BLAST for protein searches. A form of parallel computing technology known as multimedia technology that is available in modern processors, but rarely used by other bioinformatics software, has been exploited to achieve the high speed. The software is also designed to run efficiently on computer clusters using the message-passing interface standard. A public search service powered by a large computer cluster has been set-up and is freely available at www.paralign.org, where the major public databases can be searched. The software can also be downloaded free of charge for academic use.

Algorithms↗

PubMedDate not supplied

Reconstruction for fan beam with an angular-dependent displaced center-of-rotation.

A convolutional backprojection algorithm is derived for a fan beam geometry that has an angular-dependent displacement in its center-of-rotation from the midline of the fan beam. In both x-ray computed tomography and single photon emission computed tomography, misalignment can occur when the mechanical center-of-rotation is not colinear with midline of the fan beam. In some cases the shift in the center-of-rotation is constant for every angle, whereas, in other cases it varies with angular position. Standard reconstruction algorithms, which directly filter and backproject the fan beam data without rebinning into parallel beam geometry, have been derived for a geometry having its center-of-rotation at the midline of the fan beam. However, in the case of any misalignment of the center-of-rotation, if these conventional reconstruction algorithms are used to reconstruct the fan beam projections, structured artifacts and a loss of resolution will result. Simulations are performed that illustrate these artifacts and demonstrate how the new algorithm corrects for this misalignment. A method for estimating the parameters of the fan beam geometry, including the angular-dependent shift in the center-of-rotation, is also described.

Algorithms↗

PubMed1998

[The Monte Carlo method and parallel estimation in the drawing up of radiosurgery treatment plans].

PURPOSE: We investigated the practical application of a calculation algorithm based on the Monte Carlo method to stereotactic radiosurgery treatment planning. In radiosurgery, high dose gradients and the lack of electronic disequilibrium make high resolution matrices and high computing power and speed necessary to obtain accurate dose distribution. To date, the main obstacle to the wider-spread use of the Monte Carlo method has been the huge computing time necessary to obtain a dose distribution on current hardware. MATERIAL AND METHODS: In this project, developed within the ESPRIT program, funded by the European Union, a Parsytec CC (Cognitive Computing) computer was used with 9 processors (Power PC 604, 133 Mhz, RAM 64 Mb) with IBM AIX/EPX OS and availability for Fortran parallel codes compilation, connected to a PC for data input, results rendering, and dose distribution calculation with a conventional algorithm for comparison with the Monte Carlo code (an EGS4 user code). The module named Rapt Region Extractor performs data compression with an octree method without decreasing resolution, for RAM and computing time requirements to remain acceptable. A model of the 6 MV photon beam from Clinac 2100C Varian linear accelerator was devised, based on incident photon energy spectrum and, for each collimator dimension, on bidimensional dose distribution orthogonal to beam direction measured at SSd = SAD = 100 cm. RESULTS: Parallelization was carried out on event numbers, allowing a simulation speed to number of processor ratio close to unity. A new random number generator was used, capable of correctly running on the parallel architecture. The simulation procedure includes: 1) CT acquisition in DICOM 3.0 format, Analyze or with scanner; 2) Target delineation, treatment arc definition. 3) Dose calculation, with both conventional and Monte Carlo methods. 4) Dose distribution rendering on every transverse, sagittal or coronal planes overlapped in color wash on anatomical representation. Comparison between conventional and Monte Carlo algorithms were carried out on an anthropomorphic phantom and 10 real patients, with 2.5 mm anatomical resolution and standard deviation never exceeding 2%. A simulation with 10,000,000 events and 1% maximum variance can be run in 43'. When PTV is an homogeneous areas the differences between the two methods are around 5%, while when PTV is localized in dishomogeneous areas discrepancies reach 20% in the bone. CONCLUSIONS: In conclusion, the feasibility of direct simulation with the Monte Carlo method in radiosurgery has been demonstrated within time and hardware costs compatible with clinical practice.

Algorithms↗

PubMed2005

Sample-sort simulated annealing.

A simulated annealing (SA) algorithm called Sample-Sort that is artificially extended across an array of samplers is proposed. The sequence of temperatures for a serial SA algorithm is replaced with an array of samplers operating at static temperatures and the single stochastic sampler is replaced with a set of samplers. The set of samplers uses a biased generator to sample the same distribution of a serial SA algorithm to maintain the same convergence property. Sample-Sort was compared to SA by applying both to a set of global optimization problems and found to be comparable if the number of iterations per sampler was sufficient. If the evaluation phase dominates the computational requirements, Sample-Sort could take advantage of parallel processing.

Algorithms↗

PubMed2002

A species conserving genetic algorithm for multimodal function optimization.

This paper introduces a new technique called species conservation for evolving parallel subpopulations. The technique is based on the concept of dividing the population into several species according to their similarity. Each of these species is built around a dominating individual called the species seed. Species seeds found in the current generation are saved (conserved) by moving them into the next generation. Our technique has proved to be very effective in finding multiple solutions of multimodal optimization problems. We demonstrate this by applying it to a set of test problems, including some problems known to be deceptive to genetic algorithms.

Algorithms↗

PubMed2006

Extension of Chandrasekhar's formula to a homogeneous non-Lambertian surface and comparison with the 6S formulation.

The classical Chandrasekhar's formula relating the surface reflectance to the top of the atmosphere radiance rigorously applies to a Lambertian surface. For a homogeneous non-Lambertian surface in a plane-parallel atmosphere, an extension of this formula was proposed in the 1980s and has been recently implemented in the second simulation of the satellite signal in the solar spectrum (6S) algorithm. To analyze this extension, the rigorous formula of the top of the atmosphere signal is derived in a plane-parallel atmosphere bounded by a homogeneous non-Lambertian surface. Then the 6S algorithm extension is compared with the exact formula and approximations and their validity are pointed out. The methods used for the derivation of the exact formula are classical. They are based on the separation of direct and diffuse components of the radiation fields, on the introduction of the Green's function of the problem, and on integrations of boundary values of the radiation fields with the Green's function.

Journal Article↗

PubMed1994

Processing of hierarchic stimulus structures has advantages in humans and animals.

Carmesin and Schwegler (1994) have determined theoretically that a linear hierarchical stimulus structure can be encoded by a parallel network of minimal complexity. The experiments reported here compare the efficiency with which humans and pigeons process sets of stimulus pairs embodying different inequality structures. Groups of subjects of each species were taught to discriminate all 10 pairwise combinations of 5 stimuli with an operant conditioning method. For one group, the reward/punishment allocations within the pairs agreed with a linear hierarchy. For a second and third group, the reinforcement allocations of one or three, respectively, of the stimulus pairs deviated from such ordering. The time it took the subjects to learn the tasks as well as the final choice latencies and/or error rates increased with the number of deviating inequalities. The results agree with the assumption that both humans and pigeons encode stimulus inequality structures with parallel processing neural networks rather than with a sequentially processing algorithm.

Adult↗

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↗