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 1,171 records · Page 65Linked to original sources

PubMedDate not supplied

A sampling algorithm for segregation analysis.

Methods for detecting Quantitative Trait Loci (QTL) without markers have generally used iterative peeling algorithms for determining genotype probabilities. These algorithms have considerable shortcomings in complex pedigrees. A Monte Carlo Markov chain (MCMC) method which samples the pedigree of the whole population jointly is described. Simultaneous sampling of the pedigree was achieved by sampling descent graphs using the Metropolis-Hastings algorithm. A descent graph describes the inheritance state of each allele and provides pedigrees guaranteed to be consistent with Mendelian sampling. Sampling descent graphs overcomes most, if not all, of the limitations incurred by iterative peeling algorithms. The algorithm was able to find the QTL in most of the simulated populations. However, when the QTL was not modeled or found then its effect was ascribed to the polygenic component. No QTL were detected when they were not simulated.

Algorithms↗

PubMed2006

Genetic analysis of growth curves using the SAEM algorithm.

The analysis of nonlinear function-valued characters is very important in genetic studies, especially for growth traits of agricultural and laboratory species. Inference in nonlinear mixed effects models is, however, quite complex and is usually based on likelihood approximations or Bayesian methods. The aim of this paper was to present an efficient stochastic EM procedure, namely the SAEM algorithm, which is much faster to converge than the classical Monte Carlo EM algorithm and Bayesian estimation procedures, does not require specification of prior distributions and is quite robust to the choice of starting values. The key idea is to recycle the simulated values from one iteration to the next in the EM algorithm, which considerably accelerates the convergence. A simulation study is presented which confirms the advantages of this estimation procedure in the case of a genetic analysis. The SAEM algorithm was applied to real data sets on growth measurements in beef cattle and in chickens. The proposed estimation procedure, as the classical Monte Carlo EM algorithm, provides significance tests on the parameters and likelihood based model comparison criteria to compare the nonlinear models with other longitudinal methods.

Algorithms↗

PubMed2003

Optimal step length EM algorithm (OSLEM) for the estimation of haplotype frequency and its application in lipoprotein lipase genotyping.

BACKGROUND: Haplotype based linkage disequilibrium (LD) mapping has become a powerful and cost-effective method for performing genetic association studies, particularly in the search for genetic markers in linkage disequilibrium with complex disease loci. Various methods (e.g. Monte-Carlo (Gibbs sampling); EM (expectation maximization); and Clark's method) have been used to estimate haplotype frequencies from routine genotyping data. RESULTS: These algorithms can be very slow for large number of SNPs. In order to speed them up, we have developed a new algorithm using numerical analysis technology, a so-called optimal step length EM (OSLEM) that accelerates the calculation. By optimizing approximately the step length of the EM algorithm, OSLEM can run at about twice the speed of EM. This algorithm has been used for lipoprotein lipase (LPL) genotyping analysis. CONCLUSIONS: This new optimal step length EM (OSLEM) algorithm can accelerate the calculation for haplotype frequency estimation for genotyping data without pedigree information. An OSLEM on-line server is available, as well as a free downloadable version.

Algorithms↗

PubMed2004

Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.

BACKGROUND: The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n6)time and O(n4) space algorithm by Rivas and Eddy is currently the best available program. RESULTS: We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n4) time and O(n2) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm. CONCLUSIONS: RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.

Algorithms↗

PubMed2005

A new decoding algorithm for hidden Markov models improves the prediction of the topology of all-beta membrane proteins.

BACKGROUND: Structure prediction of membrane proteins is still a challenging computational problem. Hidden Markov models (HMM) have been successfully applied to the problem of predicting membrane protein topology. In a predictive task, the HMM is endowed with a decoding algorithm in order to assign the most probable state path, and in turn the labels, to an unknown sequence. The Viterbi and the posterior decoding algorithms are the most common. The former is very efficient when one path dominates, while the latter, even though does not guarantee to preserve the HMM grammar, is more effective when several concurring paths have similar probabilities. A third good alternative is 1-best, which was shown to perform equal or better than Viterbi. RESULTS: In this paper we introduce the posterior-Viterbi (PV) a new decoding which combines the posterior and Viterbi algorithms. PV is a two step process: first the posterior probability of each state is computed and then the best posterior allowed path through the model is evaluated by a Viterbi algorithm. CONCLUSION: We show that PV decoding performs better than other algorithms when tested on the problem of the prediction of the topology of beta-barrel membrane proteins.

Algorithms↗

PubMed2006

LS-NMF: a modified non-negative matrix factorization algorithm utilizing uncertainty estimates.

BACKGROUND: Non-negative matrix factorisation (NMF), a machine learning algorithm, has been applied to the analysis of microarray data. A key feature of NMF is the ability to identify patterns that together explain the data as a linear combination of expression signatures. Microarray data generally includes individual estimates of uncertainty for each gene in each condition, however NMF does not exploit this information. Previous work has shown that such uncertainties can be extremely valuable for pattern recognition. RESULTS: We have created a new algorithm, least squares non-negative matrix factorization, LS-NMF, which integrates uncertainty measurements of gene expression data into NMF updating rules. While the LS-NMF algorithm maintains the advantages of original NMF algorithm, such as easy implementation and a guaranteed locally optimal solution, the performance in terms of linking functionally related genes has been improved. LS-NMF exceeds NMF significantly in terms of identifying functionally related genes as determined from annotations in the MIPS database. CONCLUSION: Uncertainty measurements on gene expression data provide valuable information for data analysis, and use of this information in the LS-NMF algorithm significantly improves the power of the NMF technique.

Algorithms↗

PubMed2006

Algorithms for incorporating prior topological information in HMMs: application to transmembrane proteins.

BACKGROUND: Hidden Markov Models (HMMs) have been extensively used in computational molecular biology, for modelling protein and nucleic acid sequences. In many applications, such as transmembrane protein topology prediction, the incorporation of limited amount of information regarding the topology, arising from biochemical experiments, has been proved a very useful strategy that increased remarkably the performance of even the top-scoring methods. However, no clear and formal explanation of the algorithms that retains the probabilistic interpretation of the models has been presented so far in the literature. RESULTS: We present here, a simple method that allows incorporation of prior topological information concerning the sequences at hand, while at the same time the HMMs retain their full probabilistic interpretation in terms of conditional probabilities. We present modifications to the standard Forward and Backward algorithms of HMMs and we also show explicitly, how reliable predictions may arise by these modifications, using all the algorithms currently available for decoding HMMs. A similar procedure may be used in the training procedure, aiming at optimizing the labels of the HMM's classes, especially in cases such as transmembrane proteins where the labels of the membrane-spanning segments are inherently misplaced. We present an application of this approach developing a method to predict the transmembrane regions of alpha-helical membrane proteins, trained on crystallographically solved data. We show that this method compares well against already established algorithms presented in the literature, and it is extremely useful in practical applications. CONCLUSION: The algorithms presented here, are easily implemented in any kind of a Hidden Markov Model, whereas the prediction method (HMM-TM) is freely available for academic users at http://bioinformatics.biol.uoa.gr/HMM-TM, offering the most advanced decoding options currently available.

Algorithms↗

PubMed2006

Development and implementation of an algorithm for detection of protein complexes in large interaction networks.

BACKGROUND: After complete sequencing of a number of genomes the focus has now turned to proteomics. Advanced proteomics technologies such as two-hybrid assay, mass spectrometry etc. are producing huge data sets of protein-protein interactions which can be portrayed as networks, and one of the burning issues is to find protein complexes in such networks. The enormous size of protein-protein interaction (PPI) networks warrants development of efficient computational methods for extraction of significant complexes. RESULTS: This paper presents an algorithm for detection of protein complexes in large interaction networks. In a PPI network, a node represents a protein and an edge represents an interaction. The input to the algorithm is the associated matrix of an interaction network and the outputs are protein complexes. The complexes are determined by way of finding clusters, i. e. the densely connected regions in the network. We also show and analyze some protein complexes generated by the proposed algorithm from typical PPI networks of Escherichia coli and Saccharomyces cerevisiae. A comparison between a PPI and a random network is also performed in the context of the proposed algorithm. CONCLUSION: The proposed algorithm makes it possible to detect clusters of proteins in PPI networks which mostly represent molecular biological functional units. Therefore, protein complexes determined solely based on interaction data can help us to predict the functions of proteins, and they are also useful to understand and explain certain biological processes.

Algorithms↗

PubMed2006

Fast index based algorithms and software for matching position specific scoring matrices.

BACKGROUND: In biological sequence analysis, position specific scoring matrices (PSSMs) are widely used to represent sequence motifs in nucleotide as well as amino acid sequences. Searching with PSSMs in complete genomes or large sequence databases is a common, but computationally expensive task. RESULTS: We present a new non-heuristic algorithm, called ESAsearch, to efficiently find matches of PSSMs in large databases. Our approach preprocesses the search space, e.g., a complete genome or a set of protein sequences, and builds an enhanced suffix array that is stored on file. This allows the searching of a database with a PSSM in sublinear expected time. Since ESAsearch benefits from small alphabets, we present a variant operating on sequences recoded according to a reduced alphabet. We also address the problem of non-comparable PSSM-scores by developing a method which allows the efficient computation of a matrix similarity threshold for a PSSM, given an E-value or a p-value. Our method is based on dynamic programming and, in contrast to other methods, it employs lazy evaluation of the dynamic programming matrix. We evaluated algorithm ESAsearch with nucleotide PSSMs and with amino acid PSSMs. Compared to the best previous methods, ESAsearch shows speedups of a factor between 17 and 275 for nucleotide PSSMs, and speedups up to factor 1.8 for amino acid PSSMs. Comparisons with the most widely used programs even show speedups by a factor of at least 3.8. Alphabet reduction yields an additional speedup factor of 2 on amino acid sequences compared to results achieved with the 20 symbol standard alphabet. The lazy evaluation method is also much faster than previous methods, with speedups of a factor between 3 and 330. CONCLUSION: Our analysis of ESAsearch reveals sublinear runtime in the expected case, and linear runtime in the worst case for sequences not shorter than the absolute value of A(m) + m - 1, where m is the length of the PSSM and A a finite alphabet. In practice, ESAsearch shows superior performance over the most widely used programs, especially for DNA sequences. The new algorithm for accurate on-the-fly calculations of thresholds has the potential to replace formerly used approximation approaches. Beyond the algorithmic contributions, we provide a robust, well documented, and easy to use software package, implementing the ideas and algorithms presented in this manuscript.

Algorithms↗

PubMed2006

Rank-statistics based enrichment-site prediction algorithm developed for chromatin immunoprecipitation on chip experiments.

BACKGROUND: High density oligonucleotide tiling arrays are an effective and powerful platform for conducting unbiased genome-wide studies. The ab initio probe selection method employed in tiling arrays is unbiased, and thus ensures consistent sampling across coding and non-coding regions of the genome. Tiling arrays are increasingly used in chromatin immunoprecipitation (IP) experiments (ChIP on chip). ChIP on chip facilitates the generation of genome-wide maps of in-vivo interactions between DNA-associated proteins including transcription factors and DNA. Analysis of the hybridization of an immunoprecipitated sample to a tiling array facilitates the identification of ChIP-enriched segments of the genome. These enriched segments are putative targets of antibody assayable regulatory elements. The enrichment response is not ubiquitous across the genome. Typically 5 to 10% of tiled probes manifest some significant enrichment. Depending upon the factor being studied, this response can drop to less than 1%. The detection and assessment of significance for interactions that emanate from non-canonical and/or un-annotated regions of the genome is especially challenging. This is the motivation behind the proposed algorithm. RESULTS: We have proposed a novel rank and replicate statistics-based methodology for identifying and ascribing statistical confidence to regions of ChIP-enrichment. The algorithm is optimized for identification of sites that manifest low levels of enrichment but are true positives, as validated by alternative biochemical experiments. Although the method is described here in the context of ChIP on chip experiments, it can be generalized to any treatment-control experimental design. The results of the algorithm show a high degree of concordance with independent biochemical validation methods. The sensitivity and specificity of the algorithm have been characterized via quantitative PCR and independent computational approaches. CONCLUSION: The algorithm ranks all enrichment sites based on their intra-replicate ranks and inter-replicate rank consistency. Following the ranking, the method allows segmentation of sites based on a meta p-value, a composite array signal enrichment criterion, or a composite of these two measures. The sensitivities obtained subsequent to the segmentation of data using a meta p-value of 10-5, an array signal enrichment of 0.2 and a composite of these two values are 88%, 87% and 95%, respectively.

Algorithms↗

PubMed2006

Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost.

BACKGROUND: Multiple sequence alignment (MSA) is a useful tool in bioinformatics. Although many MSA algorithms have been developed, there is still room for improvement in accuracy and speed. In the alignment of a family of protein sequences, global MSA algorithms perform better than local ones in many cases, while local ones perform better than global ones when some sequences have long insertions or deletions (indels) relative to others. Many recent leading MSA algorithms have incorporated pairwise alignment information obtained from a mixture of sources into their scoring system to improve accuracy of alignment containing long indels. RESULTS: We propose a novel group-to-group sequence alignment algorithm that uses a piecewise linear gap cost. We developed a program called PRIME, which employs our proposed algorithm to optimize the well-defined sum-of-pairs score. PRIME stands for Profile-based Randomized Iteration MEthod. We evaluated PRIME and some recent MSA programs using BAliBASE version 3.0 and PREFAB version 4.0 benchmarks. The results of benchmark tests showed that PRIME can construct accurate alignments comparable to the most accurate programs currently available, including L-INS-i of MAFFT, ProbCons, and T-Coffee. CONCLUSION: PRIME enables users to construct accurate alignments without having to employ pairwise alignment information. PRIME is available at http://prime.cbrc.jp/.

Algorithms↗

PubMed2006

Gene selection algorithms for microarray data based on least squares support vector machine.

BACKGROUND: In discriminant analysis of microarray data, usually a small number of samples are expressed by a large number of genes. It is not only difficult but also unnecessary to conduct the discriminant analysis with all the genes. Hence, gene selection is usually performed to select important genes. RESULTS: A gene selection method searches for an optimal or near optimal subset of genes with respect to a given evaluation criterion. In this paper, we propose a new evaluation criterion, named the leave-one-out calculation (LOOC, A list of abbreviations appears just above the list of references) measure. A gene selection method, named leave-one-out calculation sequential forward selection (LOOCSFS) algorithm, is then presented by combining the LOOC measure with the sequential forward selection scheme. Further, a novel gene selection algorithm, the gradient-based leave-one-out gene selection (GLGS) algorithm, is also proposed. Both of the gene selection algorithms originate from an efficient and exact calculation of the leave-one-out cross-validation error of the least squares support vector machine (LS-SVM). The proposed approaches are applied to two microarray datasets and compared to other well-known gene selection methods using codes available from the second author. CONCLUSION: The proposed gene selection approaches can provide gene subsets leading to more accurate classification results, while their computational complexity is comparable to the existing methods. The GLGS algorithm can also better scale to datasets with a very large number of genes.

Algorithms↗

PubMed2006

An improved ant colony algorithm with diversified solutions based on the immune strategy.

BACKGROUND: Ant colony algorithm has emerged recently as a new meta-heuristic method, which is inspired from the behaviours of real ants for solving NP-hard problems. However, the classical ant colony algorithm also has its defects of stagnation and premature. This paper aims at remedying these problems. RESULTS: In this paper, we propose an adaptive ant colony algorithm that simulates the behaviour of biological immune system. The solutions of the problem are much more diversified than traditional ant colony algorithms. CONCLUSION: The proposed method for improving the performance of traditional ant colony algorithm takes into account the polarization of the colonies, and adaptively adjusts the distribution of the solutions obtained by the ants. This makes the solutions more diverse so as to avoid the stagnation and premature phenomena.

Algorithms↗

PubMedDate not supplied

Effects of an opioid taper algorithm in hematopoietic progenitor cell transplant recipients.

PURPOSE/OBJECTIVES: To examine the effects of an opioid taper algorithm on the length of taper, pain levels, withdrawal symptoms, and satisfaction with pain management in hematopoietic progenitor cell transplant (HPCT) recipients and nurse documentation of patient response to taper. DESIGN: Quasi-experimental. SETTING: A 32-bed HPCT unit in a large tertiary U.S. healthcare center. SAMPLE: 106 HPCT recipients, 5-64 years of age. METHODS: In phase 1, baseline data were collected from 45 patients during opioid tapers, with no study intervention. In phase 2, an opioid taper algorithm was implemented as the study intervention for 61 patients. MAIN RESEARCH VARIABLES: Phase 1 and phase 2 pretaper and taper opioid dosage, length of taper, nurse documentation, patient-reported pain and withdrawal symptoms, and nurses' perspectives about the use of tapers. FINDINGS: Use of the algorithm in phase 2 resulted in decreasing taper time by a mean of 0.4 days, a significant decrease in withdrawal symptoms, a significant increase in only 1 of 10 aspects of nurse documentation, and no significant differences in patient self-reports of worst pain or satisfaction with pain management. Nausea, vomiting, diarrhea, insomnia, and runny nose were the withdrawal symptoms reported most frequently. CONCLUSIONS: Use of the algorithm improved tapering practice somewhat without disadvantaging patients. IMPLICATIONS FOR NURSING PRACTICE: Use of an opioid taper algorithm may promote consistency of tapering practice.

Adolescent↗

PubMed2005

Identifying palliative care patients with symptoms of depression: an algorithm.

INTRODUCTION: Even though depression has serious and wide-ranging effects on outcomes in palliative care, errors in the identification of depressed patients are common. OBJECTIVES: To examine the clinical validity of widely publicised one- and two-question screening tools for depression in two palliative care settings. Also, to examine the construct validity and acceptability of a new empirically derived algorithm. METHOD: Participants were Australian palliative care patients in an inpatient hospice (n=22) or the community (n=69). Patients completed an unstructured interview about their feelings, questions relevant to three reference standards, two screening questions for depression and questions about the acceptability of the screening questions. RESULTS: The clinical validity of the one- and two-question screening tools did not generalise across the two care settings. In contrast, the algorithm met stringent criteria for clinical validity for two reference standards in both settings. The algorithm also selectively identified patients whose unstructured interviews referred to themes consistent with depression. The algorithm includes potentially sensitive questions about anhedonia and depressed affect. However, almost all patients and staff reported that asking such questions soon after referral was acceptable. CONCLUSIONS: A four-question algorithm designed to identify patients who warrant follow-up for depression showed clinical validity, generalizability and construct validity, and the content was acceptable to patients and clinicians.

Adult↗

PubMed2005

An algorithm for processing vital sign monitoring data to remotely identify operating room occupancy in real-time.

We developed an algorithm for processing networked vital signs (VS) to remotely identify in real-time when a patient enters and leaves a given operating room (OR). The algorithm addresses two types of mismatches between OR occupancy and VS: a patient is in the OR but no VS are available (e.g., patient is being hooked up), and no patient is in the OR but artifactual VS are present (e.g., because of staff handling of sensors). The algorithm was developed with data from 7 consecutive days (122 cases) in a 6 OR trauma center. The algorithm was then tested on data from another 7 consecutive days (98 cases), against patient in- and out-times captured by OR surveillance videos. When pulse oximetry, electrocardiogram, and temperature readings were used, OR occupancy was correctly identified 96% (95% confidence interval [CI] 95%-97%) and OR vacancy >99% of the time. Identified patient in- and out-times were accurate within 4.9 min (CI 4.2-5.7) and 2.8 min (CI 2.3-3.5), respectively, and were not different in accuracy from times reported by staff on OR records. The algorithm's usefulness was demonstrated partly by its continued operational use. We conclude that VS can be processed to accurately report OR occupancy in real-time.

Algorithms↗

PubMed1994

Technical note: evaluation of a region growing algorithm for segmenting pelvic computed tomography images during radiotherapy planning.

A clinical evaluation of a computer segmentation algorithm was performed to determine whether the incorporation of such an algorithm into a radiotherapy treatment planning computer would increase the speed of segmentation and therefore increase user productivity. Six pelvic computed tomography (CT) data cubes were manually segmented akin to current radiotherapy practice on three occasions and the mean times for each data cube recorded to provide baseline measurements. The same images were then segmented using the new region growing algorithm, backed up by manual segmentation and contour editing tools where necessary, and the times compared with the baseline for each data cube. The results confirm that this algorithm can decrease segmentation times by a factor of 2.4 without compromising the quality of the final plan (p < 0.0001). Most of this time gain is from a rapid segmentation of the pelvic bones and external contour rather than the soft tissues of the pelvis. We conclude that such algorithms will be of value for segmenting large pelvic CT data cubes for radiotherapy planning by making the procedure less labour intensive.

Algorithms↗

PubMed2006

Development of a cone angle weighted three-dimensional image reconstruction algorithm to reduce cone-beam artefacts.

OBJECTIVES: Image reconstruction from cone-beam projections collected along a single circular source trajectory is commonly done using the Feldkamp algorithm, which performs well only with a small cone angle. In this report, we propose an algorithm to reduce cone-beam artefacts by increasing the cone angle by several fold to achieve satisfactory image quality at the same radiation dose. METHODS: To examine the factors involved in the occurrence of cone-beam artefacts, a microspheres-phantom was arranged longitudinally at different positions and a computer simulation was performed. Due to differences in projection angle, data projected onto the detector surface were projected along trajectories shown as different periodic functions depending on the distance and position from the mid-plane position. Therefore, projection along several detector channels based on different projection data resulting from different periodic functions is considered responsible for the increase in cone-beam artefacts associated with an increase in the distance of reconstruction planes from the mid-plane position. Our recommended algorithm to reduce such artefacts features a change in weighting with respect to projection data obtained at different projection angles, three-dimensional back-projection of corrected projection data. RESULTS: Numerical phantom simulation and real human head origin study (a prototype cone-beam CT) showed that the effect of the reduction in cone-beam artefacts of an object located at the edges was markedly enhanced at reconstruction planes at positions further from the mid-plane position. CONCLUSION: We propose a projection angle weight-based algorithm to increase the cone angle by several fold to achieve satisfactory image quality at the same radiation dose. These findings confirmed that this algorithm reduces cone-beam artefacts and generates high-quality reconstruction images.

Algorithms↗