PubMed Health⌕ Search

SEARCH · PubMed Health

Results for “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 253 records · Page 14Linked to original sources

A structural EM algorithm for phylogenetic inference.

A central task in the study of molecular evolution is the reconstruction of a phylogenetic tree from sequences of current-day taxa. The most established approach to tree reconstruction is maximum likelihood (ML) analysis. Unfortunately, searching for the maximum likelihood phylogenetic tree is computationally prohibitive for large data sets. In this paper, we describe a new algorithm that uses Structural Expectation Maximization (EM) for learning maximum likelihood phylogenetic trees. This algorithm is similar to the standard EM method for edge-length estimation, except that during iterations of the Structural EM algorithm the topology is improved as well as the edge length. Our algorithm performs iterations of two steps. In the E-step, we use the current tree topology and edge lengths to compute expected sufficient statistics, which summarize the data. In the M-Step, we search for a topology that maximizes the likelihood with respect to these expected sufficient statistics. We show that searching for better topologies inside the M-step can be done efficiently, as opposed to standard methods for topology search. We prove that each iteration of this procedure increases the likelihood of the topology, and thus the procedure must converge. This convergence point, however, can be a suboptimal one. To escape from such "local optima," we further enhance our basic EM procedure by incorporating moves in the flavor of simulated annealing. We evaluate these new algorithms on both synthetic and real sequence data and show that for protein sequences even our basic algorithm finds more plausible trees than existing methods for searching maximum likelihood phylogenies. Furthermore, our algorithms are dramatically faster than such methods, enabling, for the first time, phylogenetic analysis of large protein data sets in the maximum likelihood framework.

Algorithms↗

Algorithms and software for support of gene identification experiments.

MOTIVATION: Gene annotation is the final goal of gene prediction algorithms. However, these algorithms frequently make mistakes and therefore the use of gene predictions for sequence annotation is hardly possible. As a result, biologists are forced to conduct time-consuming gene identification experiments by designing appropriate PCR primers to test cDNA libraries or applying RT-PCR, exon trapping/amplification, or other techniques. This process frequently amounts to 'guessing' PCR primers on top of unreliable gene predictions and frequently leads to wasting of experimental efforts. RESULTS: The present paper proposes a simple and reliable algorithm for experimental gene identification which bypasses the unreliable gene prediction step. Studies of the performance of the algorithm on a sample of human genes indicate that an experimental protocol based on the algorithm's predictions achieves an accurate gene identification with relatively few PCR primers. Predictions of PCR primers may be used for exon amplification in preliminary mutation analysis during an attempt to identify a gene responsible for a disease. We propose a simple approach to find a short region from a genomic sequence that with high probability overlaps with some exon of the gene. The algorithm is enhanced to find one or more segments that are probably contained in the translated region of the gene and can be used as PCR primers to select appropriate clones in cDNA libraries by selective amplification. The algorithm is further extended to locate a set of PCR primers that uniformly cover all translated regions and can be used for RT-PCR and further sequencing of (unknown) mRNA.

Algorithms↗

A RAPID algorithm for sequence database comparisons: application to the identification of vector contamination in the EMBL databases.

MOTIVATION: Word-matching algorithms such as BLAST are routinely used for sequence comparison. These algorithms typically use areas of matching words to seed alignments which are then used to assess the degree of sequence similarity. In this paper, we show that by formally separating the word-matching and sequence-alignment process, and using information about word frequencies to generate alignments and similarity scores, we can create a new sequence-comparison algorithm which is both fast and sensitive. The formal split between word searching and alignment allows users to select an appropriate alignment method without affecting the underlying similarity search. The algorithm has been used to develop software for identifying entries in DNA sequence databases which are contaminated with vector sequence. RESULTS: We present three algorithms, RAPID, PHAT and SPLAT, which together allow vector contaminations to be found and assessed extremely rapidly. RAPID is a word search algorithm which uses probabilities to modify the significance attached to different words; PHAT and SPLAT are alignment algorithms. An initial implementation has been shown to be approximately an order of magnitude faster than BLAST. The formal split between word searching and alignment not only offers considerable gains in performance, but also allows alignment generation to be viewed as a user interface problem, allowing the most useful output method to be selected without affecting the underlying similarity search. Receiver Operator Characteristic (ROC) analysis of an artificial test set allows the optimal score threshold for identifying vector contamination to be determined. ROC curves were also used to determine the optimum word size (nine) for finding vector contamination. An analysis of the entire expressed sequence tag (EST) subset of EMBL found a contamination rate of 0.27%. A more detailed analysis of the 50 000 ESTs in est10.dat (an EST subset of EMBL) finds an error rate of 0.86%, principally due to two large-scale projects. AVAILABILITY: A Web page for the software exists at http://bioinf.man.ac.uk/rapid, or it can be downloaded from ftp://ftp.bioinf.man.ac.uk/RAPID CONTACT: crispin@cs.man.ac.uk

Algorithms↗

Analysis of high density expression microarrays with signed-rank call algorithms.

MOTIVATION: We consider the detection of expressed genes and the comparison of them in different experiments with the high-density oligonucleotide microarrays. The results are summarized as the detection calls and comparison calls, and they should be robust against data outliers over a wide target concentration range. It is also helpful to provide parameters that can be adjusted by the user to balance specificity and sensitivity under various experimental conditions. RESULTS: We present rank-based algorithms for making detection and comparison calls on expression microarrays. The detection call algorithm utilizes the discrimination scores. The comparison call algorithm utilizes intensity differences. Both algorithms are based on Wilcoxon's signed-rank test. Several parameters in the algorithms can be adjusted by the user to alter levels of specificity and sensitivity. The algorithms were developed and analyzed using spiked-in genes arrayed in a Latin square format. In the call process, p-values are calculated to give a confidence level for the pertinent hypotheses. For comparison calls made between two arrays, two primary normalization factors are defined. To overcome the difficulty that constant normalization factors do not fit all probe sets, we perturb these primary normalization factors and make increasing or decreasing calls only if all resulting p-values fall within a defined critical region. Our algorithms also automatically handle scanner saturation.

Algorithms↗

Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment.

MOTIVATION: Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce memory consumption often sacrifice speed or alignment accuracy. RESULTS: We present Singletrack, an efficient algorithm for backtrace gap-affine and dual gap-affine alignments that requires storing a single DP matrix while preserving optimal alignment results. Compared to classical DP algorithms, Singletrack removes the need to store additional matrices (i.e. 2 for gap-affine and 4 for dual gap-affine), significantly reducing memory consumption and, in turn, reducing pressure on the memory hierarchy and improving overall performance. Most importantly, Singletrack is a general backtrace method compatible with state-of-the-art DP-based algorithms and heuristics, such as the Suzuki-Kasahara (SK) and the Wavefront Alignment (WFA) algorithms. We demonstrate that Singletrack reduces memory consumption for both SK and WFA algorithms, lowering SK usage by 2× and 4× and WFA usage by 3× and 5× for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2's memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4× at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2-2.1×. Compared to the efficient linear-memory BiWFA algorithm, the Singletrack-accelerated version of WFA trades a practical increase in memory usage for up to 5.2× higher performance. AVAILABILITY AND IMPLEMENTATION: The Singletrack implementations presented in this work are available on Zenodo (DOI: 10.5281/zenodo.18770585) and GitHub (https://github.com/LorienLV/singletrack).

Algorithms↗

Efficacy of a simple intraoperative transfusion algorithm for nonerythrocyte component utilization after cardiopulmonary bypass.

BACKGROUND: Abnormal bleeding after cardiopulmonary bypass (CPB) is a common complication of cardiac surgery, with important health and economic consequences. Coagulation test-based algorithms may reduce transfusion of non-erythrocyte allogeneic blood in patients with abnormal bleeding. METHODS: The authors performed a randomized prospective trial comparing allogeneic transfusion practices in 92 adult patients with abnormal bleeding after CPB. Patients with abnormal bleeding were randomized to one of two groups: a control group following individual anesthesiologist's transfusion practices and a protocol group using a transfusion algorithm guided by coagulation tests. RESULTS: Among 836 eligible patients having all types of elective cardiac surgery requiring CPB, 92 patients developed abnormal bleeding after CPB (incidence, 11%). The transfusion algorithm group received less allogeneic fresh frozen plasma in the operating room after CPB (median, 0 units; range, 0-7 units) than the control group (median, 3 units; range, 0-10 units) (P = 0.0002). The median number of platelet units transfused in the operating room after CPB was 4 (range, 0-12) in the algorithm group compared with 6 (range, 0-18) in the control group (P = 0.0001). Intensive care unit (ICU) mediastinal blood loss was significantly less in the algorithm group. Multivariate analysis demonstrated that transfusion algorithm use resulted in reduced ICU blood loss. The control group also had a significantly greater incidence of surgical reoperation of the mediastinum for bleeding (11.8% vs. 0%; P = 0.032). CONCLUSIONS: Use of a coagulation test-based transfusion algorithm in cardiac surgery patients with abnormal bleeding after CPB reduced non-erythrocyte allogeneic transfusions in the operating room and ICU blood loss.

Adult↗

A reexamination of the NRMP matching algorithm. National Resident Matching Program.

Most graduating medical students in the United States find their first professional appointments through the National Resident Matching Program (NRMP). This service receives rank-order lists of preferences from students and from hospitals, and then generates final assignments of students to hospitals through the use of a specific computerized matching algorithm. The author uses recent findings from the mathematics and economics literatures to demonstrate three difficulties with the NRMP's matching algorithm and the official descriptions thereof. First, the algorithm favors hospitals over students, a feature known to the NRMP since at least 1976, but, in the author's opinion, not made clear in NRMP literature for students. Second, the author argues that the NRMP's justification that its algorithm mimics orderly, noncentralized admission processes is not correct. Institutions operating under non-centralized procedures must typically make more initial offers than there are positions, in the realization that some fraction of their offers will be declined. This arrangement enlarges the choices available to many applicants, and thereby benefits them, whereas the NRMP's algorithm unrealistically assumes that no institution would ever send out any extra offers. Third, the NRMP's algorithm contains incentives for students to misrepresent their true preferences when constructing their rank-order lists. This feature is a substantial disadvantage of the current algorithm and is incorrectly described in literature distributed to students and in published articles from the NRMP.(ABSTRACT TRUNCATED AT 250 WORDS)

Algorithms↗

Algorithms for detecting antibodies to HIV-1: results from a rural Ugandan cohort.

OBJECTIVE: To evaluate an algorithm using two enzyme immunoassays (EIA) for anti-HIV-1 antibodies in a rural African population and to assess alternative simplified algorithms. METHODS: Sera obtained from 7895 individuals in a rural population survey were tested using an algorithm based on two different EIA systems: Recombigen HIV-1 EIA and Wellcozyme HIV-1 Recombinant. Alternative algorithms were assessed using negative or confirmed positive sera. RESULTS: None of the 227 sera classified as unequivocably negative by the two assays were positive by Western blot. Of 192 sera unequivocably positive by both assays, four were seronegative by Western blot. The possibility of technical error cannot be ruled out in three of these. One of the alternative algorithms assessed classified all borderline or discordant assay results as negative had a specificity of 100% and a sensitivity of 98.4%. The cost of this algorithm is one-third that of the conventional algorithm. CONCLUSIONS: Our evaluation suggests that high specificity and sensitivity can be obtained without using Western blot and at a considerable reduction in cost.

Algorithms↗

A microcomputer algorithm for solving first-order compartmental models involving recycling.

A general algorithm for solving first-order compartmental models including recycling systems has been developed and its implementation on a microcomputer is described. Matrix algebra is used to obtain for any compartmental model an analytical solution, which is expressed as the exponential of a matrix of rate constants. A special technique is used in the algorithm to enable this exponential to be evaluated with a rapidly converging series. Truncation errors incurred in this process are estimated automatically. Thus, in an extreme case, where these errors may be significant, the appropriate action can be taken. Given a particular model, the user enters the model parameters into a rate matrix according to a simple rule. The algorithm then uses this matrix to solve the model, and thus no specialized mathematical knowledge is needed. The algorithm is given in a short BASIC program (60 lines) listed in an appendix. No additional software is required. By running this program on a standard microcomputer, the user can solve models of any complexity: those up to 15 compartments in seconds and those up to 30 compartments within a minute. The algorithm is thus ideally suited to solve kinetic models describing the transport of radionuclides in the environment or the translocation of elements in biological systems such as the metabolic models recommended by the International Commission on Radiological Protection (ICRP). Given the initial amount of material in each compartment at time t = 0, together with its radioactive decay constant, the algorithm gives both the amount in each compartment at any future time t and the number of disintegrations that will have occurred in each compartment up to time t. The computer program, shown in an appendix, could easily be used to calculate disintegrations over any time interval of interest, or to predict the quantities or fractions of an intake expected to be present in any in vivo or excretion compartments of interest. Thus, the algorithm can be useful in both the design and conduct of bioassay and internal dose assessment procedures.

Algorithms↗

Prospective evaluation of a dose prediction algorithm for intravenous tobramycin in adolescent and adult patients with cystic fibrosis.

The predictive performance of a new algorithm to calculate the initial daily dose of tobramycin in patients with cystic fibrosis (CF) was prospectively evaluated. Twenty-six patients with CF (15 men, 11 women, 18-45 years of age) with an acute exacerbation of their chronic pulmonary infection were treated with intravenous tobramycin. The initial dose was calculated with a previously presented algorithm. This algorithm was derived from correlation analysis performed on the adjusted daily dose guided by the determination of serum concentrations: dose (mg three times daily) = 90 + 2.13 x LBM (kg), where LBM (male) = (1.1 x body weight [BW]) - (128 x BW2/height2) and LBM (female) = (1.07 x BW) - (148 x BW2/height2). The predictive performance of this algorithm was evaluated comparing the calculated initial daily dose with the adjusted daily dose for peak and trough levels of 9-11 mg/L and 1.0 mg/L, respectively. Mean squared error and mean error were determined as reflections of precision and bias. The predictive performance of the algorithm was compared with historical data on the predictive performance of the standard equation to dose of 3.3 mg/kg body weight three times daily. The dose calculated with the algorithm proved to give peak serum concentrations in a narrower range and to have a greater precision, but bias was equal. Applying the algorithm, more patients had initial peak serum concentrations in the pre-determined range of 9-11 mg/L than when using the standard equation, so fewer dose adjustments had to be made.

Adolescent↗

HIV-1 protease and reverse transcriptase mutation patterns responsible for discordances between genotypic drug resistance interpretation algorithms.

Several rules-based algorithms have been developed to interpret results of HIV-1 genotypic resistance tests. To assess the concordance of these algorithms and to identify sequences causing interalgorithm discordances, we applied four publicly available algorithms to the sequences of isolates from 2,045 individuals in northern California. Drug resistance interpretations were classified as S for susceptible, I for intermediate, and R for resistant. Of 30,675 interpretations (2,045 sequences x 15 drugs), 4.4% were completely discordant, with at least one algorithm assigning an S and another an R; 29.2% were partially discordant, with at least one algorithm assigning an S and another an I, or at least one algorithm assigning an I and another an R; and 66.4% displayed complete concordance, with all four algorithms assigning the same interpretation. Discordances between nucleoside reverse transcriptase inhibitor interpretations usually resulted from several simple, frequently occurring mutational patterns. Discordances between protease inhibitor interpretations resulted from a larger number of more complex mutation patterns. Discordances between nonnucleoside reverse transcriptase inhibitor interpretations were uncommon and resulted from a small number of individual drug resistance mutations. Determining the clinical significance of these mutation patterns responsible for interalgorithm discordances will improve interalgorithm concordance and the accuracy of genotypic resistance interpretation.

Algorithms↗

Exact and approximate rebinning algorithms for 3-D PET data.

This paper presents two new rebinning algorithms for the reconstruction of three-dimensional (3-D) positron emission tomography (PET) data. A rebinning algorithm is one that first sorts the 3-D data into an ordinary two-dimensional (2-D) data set containing one sinogram for each transaxial slice to be reconstructed; the 3-D image is then recovered by applying to each slice a 2-D reconstruction method such as filtered-backprojection. This approach allows a significant speedup of 3-D reconstruction, which is particularly useful for applications involving dynamic acquisitions or whole-body imaging. The first new algorithm is obtained by discretizing an exact analytical inversion formula. The second algorithm, called the Fourier rebinning algorithm (FORE), is approximate but allows an efficient implementation based on taking 2-D Fourier transforms of the data. This second algorithm was implemented and applied to data acquired with the new generation of PET systems and also to simulated data for a scanner with an 18 degrees axial aperture. The reconstructed images were compared to those obtained with the 3-D reprojection algorithm (3DRP) which is the standard "exact" 3-D filtered-backprojection method. Results demonstrate that FORE provides a reliable alternative to 3DRP, while at the same time achieving an order of magnitude reduction in processing time.

Algorithms↗

Comparison of 3-D maximum a posteriori and filtered backprojection algorithms for high-resolution animal imaging with microPET.

We have evaluated the performance of two three-dimensional (3-D) reconstruction algorithms with data acquired from microPET, a high resolution tomograph dedicated to small animal imaging. The first was a linear filtered-backprojection algorithm (FBP) with reprojection of the missing data, and the second was a statistical maximum a posteriori probability algorithm (MAP). The two algorithms were evaluated in terms of their resolution performance, both in phantoms and in vivo. Sixty independent realizations of a phantom simulating the brain of a baby monkey were acquired, each containing three million counts. Each of these realizations was reconstructed independently with both algorithms. The ensemble of the 60 reconstructed realizations was used to estimate the standard deviation as a measure of the noise for each reconstruction algorithm. More detail was recovered in the MAP reconstruction without an increase in noise relative to FBP. Studies in a simple cylindrical compartment phantom demonstrated improved recovery of known activity ratios with MAP. Finally, in vivo studies also demonstrated a clear improvement in spatial resolution using the MAP algorithm. The quantitative accuracy of the MAP reconstruction was also evaluated by comparison with autoradiography and direct well counting of tissue samples and was shown to be superior.

Algorithms↗

Quasi-exact filtered backprojection algorithm for long-object problem in helical cone-beam tomography.

Exact reconstruction from axially truncated cone-beam projections acquired with a helical vertex path is a challenging problem for which solutions are currently under investigation by some researchers. This paper deals with a difficult class of this problem called the long-object problem. Its purpose is to reconstruct a central region of interest (ROI) of a long object when the helical path extends only a little bit above and below the ROI. By extending the authors' recent approach based on the triangular decomposition of the Grangeat formula, we derive quasi-exact reconstruction algorithms whose overall structure is of filtered backprojection (FBP) style. Unlike the previous similar approaches to the long-object problem, the proposed FBP algorithms do not require additional two circular scans at the ends of the helical path. Furthermore, the algorithms require a significantly smaller detector area and achieve improved image quality even for a large pitch compared with the approximate Feldkamp algorithms. One drawback of the proposed algorithms is the computational time, which is much longer than for the Feldkamp algorithms. We show some simulation results to demonstrate the performances of the proposed algorithms.

Algorithms↗

An interior point iterative maximum-likelihood reconstruction algorithm incorporating upper and lower bounds with application to SPECT transmission imaging.

The algorithm we consider here is a block-iterative (or ordered subset) version of the interior point algorithm for transmission reconstruction. Our algorithm is an interior point method because each vector of the iterative sequence [x(k)], k = 0, 1, 2, ... satisfies the constraints a(j) < x(j)k < b(j), j = 1, ..., J. Because it is a block-iterative algorithm that reconstructs the transmission attenuation map and places constraints above and below the pixel values of the reconstructed image, we call it the BITAB method. Computer simulations using the three-dimensional mathematical cardiac and torso phantom, reveal that the BITAB algorithm in conjunction with reasonably selected prior upper and lower bounds has the potential to improve the accuracy of the reconstructed attenuation coefficients from truncated fan beam transmission projections. By suitably selecting the bounds, it is possible to restrict the over estimation of coefficients outside the fully sampled region, that results from reconstructing truncated fan beam projections with iterative transmission algorithms such as the maximum-likelihood gradient type algorithm.

Algorithms↗

A novel algorithm for cardiac biosignal filtering based on filtered residue method.

In this paper, a new algorithm is presented for the filtering (de-noising) of cardiac bioelectrical signals. The primary target of this algorithm is the class of cardiac action potentials recorded using voltage-sensitive dyes, although the method is also applied to electrocardiographic signals. High periodicity is one of the main features of cardiac biosignals. The proposed algorithm exploits this feature in filtering signals with a minimum amount of distortion. The basic idea is to use signal averaging in time to find the stationary portion of the signal. The residue is found by subtracting the signal average from the corresponding points of the input. After passing through a low-pass filter, the filtered residue (FR) is added back to the signal average to reconstruct the output. The practical implementation of the filter residue algorithm is discussed. Stretching and shrinking operations are the basis for the conversion of quasi-periodic signals into periodic signals, which can then be subjected to the FR algorithm. Various examples are presented, and error estimation is performed to guide the selection of optimal parameters for the algorithm. The ability of the algorithm to reconstruct the variation among beats is demonstrated, and its limitations are discussed.

Action Potentials↗

A new pacing algorithm for overdrive suppression of atrial fibrillation. Chorus Multicentre Study Group.

Constant rapid pacing may suppress arrhythmias, but it is usually poorly tolerated in the long term. We report a pilot study of a new pacing algorithm for overdrive suppression of atrial premature complexes (APCs) and atrial fibrillation (AF), which prevents postextrasystolic pauses and varies the pacing rate in response to the frequency of APCs. The algorithm was tested in a multiple crossover study for 24 hours in dual chamber pacemakers implanted in 70 patients. Comparison was made on ambulatory recordings between the number of atrial arrhythmias commencing with the algorithm active and inactive. In all cases, the algorithm functioned as designed. No patient was aware of its operation, and no malignant arrhythmias were induced. The 36 recordings that showed atrial arrhythmia were included for analysis. The effects of the algorithm were: APCs (estimated from pacemaker statistics) reduced in 18 patients, increased in 8 (P = 0.02); atrial salvos reduced in 12, increased in 4 (P = 0.041); and AF reduced in 11, increased in 8 (P = NS). In all patients with frequent AF (> 5 episodes in total), fewer episodes occurred when the algorithm was active. We conclude that the algorithm is safe and well tolerated, reduces atrial ectopic activity, and may reduce the frequency of sustained atrial fibrillation.

Adult↗

Limitations of tachycardia confirmation and rate classification algorithms in a third-generation implantable cardioverter defibrillator.

Newer ICDs provide antitachycardia (ATP) and bradycardia pacing and cardioversion and defibrillation shocks based on sensed interval criteria. The objectives of this investigation were to determine the algorithm related errors in tachycardia confirmation and rate classification that occurred in patients with a third-generation, noncommitted, tiered ICD therapy. Forty-three consecutive patients with the Guardian ATP 4210 ICD, which uses an X out of Y sensed interval counting algorithm for tachycardia detection, confirmation, and classification were studied. Surface ECGs, intracardiac electrograms, stored data logs, and sense histories were reviewed to diagnose errors due to these algorithms that resulted in delivery of inappropriate therapy or inhibition of appropriate therapy. Sixty-eight classification or confirmation algorithm errors from 7,610 tachycardia detections (< 1%) were diagnosed in 23 (53%) of 43 patients. Three types of errors not related to device or sensing lead malfunction or programming mistakes were seen. In 26 episodes, the confirmation algorithm failed to detect late tachycardia reversion of nonsustained tachyarrhythmias, on the last or next to last sensed interval, and did not inhibit ATP (n = 17) or shocks (n = 9). In 28 episodes, inaccurate classification of tachycardia rate resulted in inappropriate ATP (n = 23) or shock (n = 5) therapy. In 14 episodes, the posttherapy reconformation algorithm produced inhibition of VVI pacing and prolonged asystole following shock therapy. These errors in tachycardia confirmation and rate classification were due to the inherent limitations of the X out of Y counting algorithm.

Adult↗