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 235 records · Page 13Linked to original sources

PubMed1997

Clique-detection algorithms for matching three-dimensional molecular structures.

The representation of chemical and biological molecules by means of graphs permits the use of a maximum common subgraph (MCS) isomorphism algorithm to identify the structural relationships existing between pairs of such molecular graphs. Clique detection provides an efficient way of implementing MCS detection, and this article reports a comparison of several different clique-detection algorithms when used for this purpose. Experiments with both small molecules and proteins demonstrate that the most efficient of these particular applications, which typically involve correspondence graphs with low edge densities, is the algorithm described by Carraghan and Pardalos. This is shown to be two to three times faster than the Bron-Kerbosch algorithm that has been used previously for MCS applications in chemistry and biology. However, the latter algorithm enables all substructures common to a pair of molecules to be identified, and not just the largest ones, as with the other algorithms considered here. The two algorithms can usefully be combined to increase the efficiency of database-searching systems that use the MCS as a measure of structural similarity.

Algorithms↗

PubMed2003

Q9, a content-balancing accuracy index to evaluate algorithms of protein secondary structure prediction.

A content-balancing accuracy index, called Q(9), has been proposed to evaluate algorithms of protein secondary structure prediction. Here the content-balancing means that the evaluation is independent of the contents of helix, strand and coil in the protein being predicted. It is shown that Q(9) is much superior to the widely used index Q(3). Therefore, algorithms are more objectively evaluated by Q(9) than Q(3). Based on 396 non-homologous proteins, five algorithms of secondary structure prediction were evaluated and compared by the new index Q(9). Of the five algorithms, PHD turned out to be the unique algorithm with an average Q(9) better than 60%. Based on the new index, it is shown that the performance of the consensus method based on a jury-decision from several algorithms is even worse than that of the best individual method. Rather than Q(3), we believe that Q(9) should be used to evaluate algorithms of protein secondary structure prediction in future studies in order to improve prediction quality.

Algorithms↗

PubMed2001

Volume learning algorithm artificial neural networks for 3D QSAR studies.

The current study introduces a new method, the volume learning algorithm (VLA), for the investigation of three-dimensional quantitative structure-activity relationships (QSAR) of chemical compounds. This method incorporates the advantages of comparative molecular field analysis (CoMFA) and artificial neural network approaches. VLA is a combination of supervised and unsupervised neural networks applied to solve the same problem. The supervised algorithm is a feed-forward neural network trained with a back-propagation algorithm while the unsupervised network is a self-organizing map of Kohonen. The use of both of these algorithms makes it possible to cluster the input CoMFA field variables and to use only a small number of the most relevant parameters to correlate spatial properties of the molecules with their activity. The statistical coefficients calculated by the proposed algorithm for cannabimimetic aminoalkyl indoles were comparable to, or improved, in comparison to the original study using the partial least squares algorithm. The results of the algorithm can be visualized and easily interpreted. Thus, VLA is a new convenient tool for three-dimensional QSAR studies.

Algorithms↗

PubMed1997

A comparison of heuristic search algorithms for molecular docking.

This paper describes the implementation and comparison of four heuristic search algorithms (genetic algorithm, evolutionary programming, simulated annealing and tabu search) and a random search procedure for flexible molecular docking. To our knowledge, this is the first application of the tabu search algorithm in this area. The algorithms are compared using a recently described fast molecular recognition potential function and a diverse set of five protein-ligand systems. Statistical analysis of the results indicates that overall the genetic algorithm performs best in terms of the median energy of the solutions located. However, tabu search shows a better performance in terms of locating solutions close to the crystallographic ligand conformation. These results suggest that a hybrid search algorithm may give superior results to any of the algorithms alone.

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↗

PubMed2000

Clinical experience of a new rate drop response algorithm in the treatment of vasovagal and carotid sinus syncope.

Dual chamber pacing has proven beneficial in patients with sudden drops in heart rate as seen in vasovagal syncope and carotid sinus syndrome. Newer algorithms for faster detection of an insidious drop in heart rate and short lasting intervention pacing at a high rate, as in the rate drop response algorithm in the Medtronic Kappa series of pacemakers, might improve the effect of pacing. Two case reports, that demonstrate the use of these rate drop response algorithms, are presented. A 24-year-old woman with recurrent episodes of syncope and repeated tilt-table tests with vasovagal cardioinhibitory outcomes had a Medtronic Kappa 400 pacemaker implanted. Syncope was abolished during repeat tilt-table testing following pacemaker implantation and proper functioning of the rate drop response algorithm. The patient has been free of syncope during follow-up apart from a single episode that occurred due to neglect of vasovagal warning symptoms. A 52-year-old man with coronary artery disease developed recurrent blackouts. Carotid sinus massage resulted in 5.5 s of asystole and presyncope. A Medtronic Kappa 700 pacemaker with a rate drop response algorithm was implanted and the patient became asymptomatic. The rate drop response algorithm is discussed in detail based upon the case reports, and recommendations are given for the use of this algorithm in patients with vasovagal syncope and carotid sinus syndrome.

Adult↗

PubMed2001

A real-time ST-segment monitoring algorithm for implantable devices.

Continuous ST-segment monitoring by implantable devices may lead to clarification of the substrate of arrhythmias, clarification of the origin of nonspecific chest pain, and titration or preventative application of established anti-ischemic therapies. Although ST-segment monitoring algorithms are available for surface electrocardiogram, the computational demand of algorithms for implantable devices must be minimized for considerations of device longevity. The new algorithm first locates a fiducial point (FPT) at the dominant peak of each QRS complex. The ST-segment deviation (measured at 2 rate-adaptive delays after FPT, eg, FPT + 96 ms and FPT + 152 ms at 60 BPM) with respect to the isoelectric level (measured at the minimum slope preceding the QRS) is then measured. The following features are also quantified by simple operations: R-R interval, R-wave slope, R-wave amplitude, ST-segment slope, and noise content during the isoelectric segment. Inconsistencies in these features relative to their adaptive normal ranges are used to reject noisy or ectopic beats and sudden morphology changes. Finally, the ST-segment deviation over time is filtered to reject rates of change that are not likely attributable to human ischemia. Performance of the algorithm was evaluated on the European Society of Cardiology ST-T Database, which contains 180 hours of ambulatory electrocardiogram with 250 expert-annotated ischemic episodes. The sensitivity was 79% [74% 84%] (mean [95% CI]) and positive predictivity was 81% [76% 86%]. This performance is statistically equivalent to that of published electrocardiogram algorithms that were validated on the same dataset. Estimates of computational burden suggest that the algorithm could process two channels of electrogram continuously for more than 5 years with current implanted device technology. In conclusion, we have developed an algorithm for ST-segment monitoring that can be implemented in current implantable devices with sensitivity and positive predictivity that are comparable with the state-of-the-art.

Algorithms↗

PubMed2002

Evaluation of gene-finding algorithms by a content-balancing accuracy index.

A content-balancing accuracy index, called q(9), to evaluate gene-finding algorithms has been proposed. Here the concept of content-balancing means that the evaluation by this index is independent of the coding and non-coding composition of the sequence being evaluated. Since the coding and non-coding compositions are severely unbalanced in eukaryotic genomes, the performance of gene-finding algorithms is either over- or under-evaluated by the widely used accuracy indices, e.g., the correlation coefficient, due to the lack of content-balancing ability. Using the new accuracy index q(9), seven gene-finding algorithms, FGENES; Gene-Mark.hmm; Genie; Genescan; HMMgene; Morgan and MZEF, were compared and evaluated. It is shown that Genescan is still the best one, but with q(9)= 89%, averaged over the prediction for 195 sequences. In addition to the content-balancing ability, q(9) has the merit of having definition in all possible cases. It is also shown that the traditional specificity s(p) carries important information on the performance of the algorithm being evaluated. The set of sensitivity s(n), specificity s(p) and the accuracy q(9) constitutes a complete kit to evaluate gene-finding algorithms at nucleotide level. In addition, a graphic method to compare and evaluate gene-finding algorithms has been proposed, too. Its major advantage is that the overall performance of algorithms can be grasped quickly in a perceivable form. Additionally, the new accuracy index q(9) may be applied to evaluate the performance of weather forecast, clinical diagnosis, psychological examination and protein secondary structure prediction etc.

Algorithms↗

PubMed1994

Evaluation of algorithms for tomographic reconstruction of chemical concentrations in indoor air.

Numerical studies were performed to evaluate and compare four different algorithms for tomographically reconstructing pollutant concentrations in indoor air measured with an optical remote sensing system. With a remote sensing/computed tomography system, two-dimensional maps of air concentrations can be created for an entire room with good spatial and temporal resolution. The success of such a system for characterizing the flow of contaminants in air, exposure assessment, and leak detection depends on the choice of tomographic reconstruction algorithm. A systematic method was developed to evaluate the performance of four algorithms: ART, ART3, SIRT, and SART. One hundred and twenty test maps were reconstructed by each algorithm under ideal and nonideal sampling conditions, and image quality was evaluated using four criteria. The nonideal sampling conditions included simulation of measurement noise and reduction in the number density of rays. Performance of the algorithms was found to be intimately related to the number of peaks in the test maps. The importance of using multiple measures of image quality was underscored by the fact that for some sampling conditions simulated, performance of the algorithms was judged differently depending on the evaluation criteria. Results indicated that using numerical studies is successful for evaluating such algorithms.

Air Pollutants, Occupational↗

PubMed2001

A sequence alignment algorithm with an arbitrary gap penalty function.

An algorithm for aligning biological sequences is presented that is an adaptation of the sequence generating function approach used in the statistical mechanics of biopolymers. This algorithm uses recursion relationships developed from a partition function formalism of alignment probabilities. It is implemented within a dynamic programming format that closely resembles the forward algorithm used in hidden Markov models (HMM). The algorithm aligns sequences or structures according to the statistically dominant alignment path and will be referred to as the SDP algorithm. An advantage of this method over previous ones is that it allows more complicated and physically realistic gap penalty functions to be incorporated into the algorithm in a facile manner. The performance of this algorithm in a case study of aligning the heavy and light chain from the variable region of an immunoglobulin is investigated.

Algorithms↗

PubMed2001

A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nalpha(n)) algorithm, based on a Union-Find structure, to find its connected components, where alpha is the inverse Ackerman function. Since for all practical purposes alpha(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.

Algorithms↗

PubMed2002

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↗

PubMed1998

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↗

PubMed1999

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↗

PubMed2002

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↗

PubMed2026

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↗

PubMed2001

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↗

PubMed1995

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↗