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,639 records · Page 91Linked to original sources

PubMed2004

Simultaneous search for multiple QTL using the global optimization algorithm DIRECT.

MOTIVATION: A simultaneous search is necessary for maximizing the power to detect epistatic quantitative trait loci (QTL). The computational complexity demands that the traditional exhaustive search be replaced by a more efficient global optimization algorithm. RESULTS: We have the previously known algorithm adapted DIRECT, to the problem of simultaneous mapping of multiple QTL. We have compared DIRECT with standard exhaustive search and a genetic algorithm previously used for QTL mapping in two dimensions. In all two- and three-QTL test cases, DIRECT accurately finds the global optimum two to four orders of magnitude faster than when using an exhaustive search, and one order of magnitude faster than when using the genetic algorithm. Thus, randomization testing for determining empirical significance thresholds for at least three QTL is made feasible by the use of DIRECT. AVAILABILITY: The code of the prototype implementation is available at http://user.it.uu.se/~kl/qtl_software.html

Algorithms↗

PubMed2004

A memory-efficient algorithm for multiple sequence alignment with constraints.

MOTIVATION: Recently, the concept of the constrained sequence alignment was proposed to incorporate the knowledge of biologists about structures/functionalities/consensuses of their datasets into sequence alignment such that the user-specified residues/nucleotides are aligned together in the computed alignment. The currently developed programs use the so-called progressive approach to efficiently obtain a constrained alignment of several sequences. However, the kernels of these programs, the dynamic programming algorithms for computing an optimal constrained alignment between two sequences, run in (gamman2) memory, where gamma is the number of the constraints and n is the maximum of the lengths of sequences. As a result, such a high memory requirement limits the overall programs to align short sequences only. RESULTS: We adopt the divide-and-conquer approach to design a memory-efficient algorithm for computing an optimal constrained alignment between two sequences, which greatly reduces the memory requirement of the dynamic programming approaches at the expense of a small constant factor in CPU time. This new algorithm consumes only O(alphan) space, where alpha is the sum of the lengths of constraints and usually alpha << n in practical applications. Based on this algorithm, we have developed a memory-efficient tool for multiple sequence alignment with constraints. AVAILABILITY: http://genome.life.nctu.edu.tw/MUSICME.

Algorithms↗

PubMed2005

Reconsidering complete search algorithms for protein backbone NMR assignment.

MOTIVATION: Nuclear magnetic resonance (NMR) spectroscopy is widely used to determine and analyze protein structures. An essential step in NMR studies is determining the backbone resonance assignment, which maps individual atoms to experimentally measured resonance frequencies. Performing assignment is challenging owing to the noise and ambiguity in NMR spectra. Although automated procedures have been investigated, by-and-large they are still struggling to gain acceptance because of inherent limits in scalability and/or unacceptable levels of assignment error. To have confidence in the results, an algorithm should be complete, i.e. able to identify all solutions consistent with the data, including all arbitrary configurations of extra and missing peaks. The ensuing combinatorial explosion in the space of possible assignments has led to the perception that complete search is hopelessly inefficient and cannot scale to realistic datasets. RESULTS: This paper presents a complete branch-contract-and-bound search algorithm for backbone resonance assignment. The algorithm controls the search space by hierarchically agglomerating partial assignments and employing statistically sound pruning criteria. It considers all solutions consistent with the data, and uniformly treats all combinations of extra and missing data. We demonstrate our approach on experimental data from five proteins ranging in size from 70 to 154 residues. The algorithm assigns >95% of the positions with >98% accuracy. We also present results on simulated data from 259 proteins from the RefDB database, ranging in size from 25 to 257 residues. The median computation time for these cases is 1 min, and the assignment accuracy is >99%. These results demonstrate that complete search not only has the advantage of guaranteeing fair treatment of all feasible solutions, but is efficient enough to be employed effectively inpractice. AVAILABILITY: The MBA(2) software package is made available under an open-source software license. The datasets featured in the Results section can also be obtained from the contact author.

Algorithms↗

PubMed2004

A fuzzy guided genetic algorithm for operon prediction.

MOTIVATION: The operon structure of the prokaryotic genome is a critical input for the reconstruction of regulatory networks at the whole genome level. As experimental methods for the detection of operons are difficult and time-consuming, efforts are being put into developing computational methods that can use available biological information to predict operons. METHOD: A genetic algorithm is developed to evolve a starting population of putative operon maps of the genome into progressively better predictions. Fuzzy scoring functions based on multiple criteria are used for assessing the 'fitness' of the newly evolved operon maps and guiding their evolution. RESULTS: The algorithm organizes the whole genome into operons. The fuzzy guided genetic algorithm-based approach makes it possible to use diverse biological information like genome sequence data, functional annotations and conservation across multiple genomes, to guide the organization process. This approach does not require any prior training with experimental operons. The predictions from this algorithm for Escherchia coli K12 and Bacillus subtilis are evaluated against experimentally discovered operons for these organisms. The accuracy of the method is evaluated using an ROC (receiver operating characteristic) analysis. The area under the ROC curve is around 0.9, which indicates excellent accuracy. CONTACT: roschen_csir@rediffmail.com.

Algorithms↗

PubMed2005

A new algorithm for comparing and visualizing relationships between hierarchical and flat gene expression data clusterings.

MOTIVATION: Clustering is one of the most widely used methods in unsupervised gene expression data analysis. The use of different clustering algorithms or different parameters often produces rather different results on the same data. Biological interpretation of multiple clustering results requires understanding how different clusters relate to each other. It is particularly non-trivial to compare the results of a hierarchical and a flat, e.g. k-means, clustering. RESULTS: We present a new method for comparing and visualizing relationships between different clustering results, either flat versus flat, or flat versus hierarchical. When comparing a flat clustering to a hierarchical clustering, the algorithm cuts different branches in the hierarchical tree at different levels to optimize the correspondence between the clusters. The optimization function is based on graph layout aesthetics or on mutual information. The clusters are displayed using a bipartite graph where the edges are weighted proportionally to the number of common elements in the respective clusters and the weighted number of crossings is minimized. The performance of the algorithm is tested using simulated and real gene expression data. The algorithm is implemented in the online gene expression data analysis tool Expression Profiler. AVAILABILITY: http://www.ebi.ac.uk/expressionprofiler

Algorithms↗

PubMed2005

Residue-rotamer-reduction algorithm for the protein side-chain conformation problem.

MOTIVATION: The protein side-chain conformation problem is a central problem in proteomics with wide applications in protein structure prediction and design. Computational complexity results show that the problem is hard to solve. Yet, instances from realistic applications are large and demand fast and reliable algorithms. RESULTS: We propose a new global optimization algorithm, which for the first time integrates residue reduction and rotamer reduction techniques previously developed for the protein side-chain conformation problem. We show that the proposed approach simplifies dramatically the topology of the underlining residue graph. Computations show that our algorithm solves problems using only 1-10% of the time required by the mixed-integer linear programming approach available in the literature. In addition, on a set of hard side-chain conformation problems, our algorithm runs 2-78 times faster than SCWRL 3.0, which is widely used for solving these problems. AVAILABILITY: The implementation is available as an online server at http://eudoxus.scs.uiuc.edu/r3.html

Algorithms↗

PubMed2001

The relationship between cervical secretions and the daily probabilities of pregnancy: effectiveness of the TwoDay Algorithm.

BACKGROUND: The TwoDay Algorithm is a simple method for identifying the fertile window. It classifies a day as fertile if cervical secretions are present on that day or were present on the day before. This approach may be an effective alternative to the ovulation and symptothermal methods for populations and programmes that find current natural family planning methods difficult to implement. METHODS: We used data on secretions from a large multinational European fecundability study to assess the relationship between the days predicted to be potentially fertile by the TwoDay Algorithm and the day-specific probabilities of pregnancy based on intercourse patterns in 434 conception cycles from the study. RESULTS: The days around ovulation that had the highest fecundability were the days most likely to be classified as fertile by the TwoDay Algorithm. In addition, intercourse on a particular day in the fertile interval was twice as likely to result in a pregnancy if cervical secretions were present on that day or the day before. CONCLUSIONS: The TwoDay Algorithm is effective, both in identifying the fertile days of the cycle and in predicting days within the fertile interval that have a high pregnancy rate. Our data provide the first direct evidence that cervical secretions are associated with higher fecundability within the fertile window.

Algorithms↗

PubMed1989

Trials, tribulations, and triumphs of the EM algorithm in pedigree analysis.

The EM algorithm is an iterative method for finding maximum-likelihood estimates. Its advantages often include numerical stability, simplicity of computer implementation, and natural incorporation of parameter constraints. However, the EM algorithm must be tailored to each specific problem. Smith (1957) and Ott (1977, 1979) have accomplished this for a variety of problems in human pedigree analysis. The present paper clarifies their theory by presenting it from a modern perspective. Five practical numerical examples are also given in an attempt to assess the value of the EM algorithm in realistic genetic modelling. These examples deal with racial admixture, linkage homogeneity, classical segregation analysis, a Mendelian latent trait model for schizophrenia, and a heterozygote detection assay for Ataxia-telangiectasia. Comparison with a quasi-Newton method of optimization reveals that the EM algorithm generally converges more slowly, but also more stably.

Algorithms↗

PubMed2000

Prediction of common secondary structures of RNAs: a genetic algorithm approach.

In this study we apply a genetic algorithm to a set of RNA sequences to find common RNA secondary structures. Our method is a three-step procedure. At the first stage of the procedure for each sequence, a genetic algorithm is used to optimize the structures in a population to a certain degree of stability. In this step, the free energy of a structure is the fitness criterion for the algorithm. Next, for each structure, we define a measure of structural conservation with respect to those in other sequences. We use this measure in a genetic algorithm to improve the structural similarity among sequences for the structures in the population of a sequence. Finally, we select those structures satisfying certain conditions of structural stability and similarity as predicted common structures for a set of RNA sequences. We have obtained satisfactory results from a set of tRNA, 5S rRNA, rev response elements (RRE) of HIV-1 and RRE of HIV-2/SIV, respectively.

Algorithms↗

PubMed2002

BALSA: Bayesian algorithm for local sequence alignment.

The Smith-Waterman algorithm yields a single alignment, which, albeit optimal, can be strongly affected by the choice of the scoring matrix and the gap penalties. Additionally, the scores obtained are dependent upon the lengths of the aligned sequences, requiring a post-analysis conversion. To overcome some of these shortcomings, we developed a Bayesian algorithm for local sequence alignment (BALSA), that takes into account the uncertainty associated with all unknown variables by incorporating in its forward sums a series of scoring matrices, gap parameters and all possible alignments. The algorithm can return both the joint and the marginal optimal alignments, samples of alignments drawn from the posterior distribution and the posterior probabilities of gap penalties and scoring matrices. Furthermore, it automatically adjusts for variations in sequence lengths. BALSA was compared with SSEARCH, to date the best performing dynamic programming algorithm in the detection of structural neighbors. Using the SCOP databases PDB40D-B and PDB90D-B, BALSA detected 19.8 and 41.3% of remote homologs whereas SSEARCH detected 18.4 and 38% at an error rate of 1% errors per query over the databases, respectively.

Algorithms↗

PubMed2005

Using multiple alignments to improve seeded local alignment algorithms.

Multiple alignments among genomes are becoming increasingly prevalent. This trend motivates the development of tools for efficient homology search between a query sequence and a database of multiple alignments. In this paper, we present an algorithm that uses the information implicit in a multiple alignment to dynamically build an index that is weighted most heavily towards the promising regions of the multiple alignment. We have implemented Typhon, a local alignment tool that incorporates our indexing algorithm, which our test results show to be more sensitive than algorithms that index only a sequence. This suggests that when applied on a whole-genome scale, Typhon should provide improved homology searches in time comparable to existing algorithms.

Algorithms↗

PubMed2006

Algorithm for automatic genotype calling of single nucleotide polymorphisms using the full course of TaqMan real-time data.

Single nucleotide polymorphisms (SNPs) are often determined using TaqMan real-time PCR assays (Applied Biosystems) and commercial software that assigns genotypes based on reporter probe signals at the end of amplification. Limitations to the large-scale application of this approach include the need for positive controls or operator intervention to set signal thresholds when one allele is rare. In the interest of optimizing real-time PCR genotyping, we developed an algorithm for automatic genotype calling based on the full course of real-time PCR data. Best cycle genotyping algorithm (BCGA), written in the open source language R, is based on the assumptions that classification depends on the time (cycle) of amplification and that it is possible to identify a best discriminating cycle for each SNP assay. The algorithm is unique in that it classifies samples according to the behavior of blanks (no DNA samples), which cluster with heterozygous samples. This method of classification eliminates the need for positive controls and permits accurate genotyping even in the absence of a genotype class, for example when one allele is rare. Here, we describe the algorithm and test its validity, compared to the standard end-point method and to DNA sequencing.

Algorithms↗

PubMed2006

AccuTyping: new algorithms for automated analysis of data from high-throughput genotyping with oligonucleotide microarrays.

Microarray-based analysis of single nucleotide polymorphisms (SNPs) has many applications in large-scale genetic studies. To minimize the influence of experimental variation, microarray data usually need to be processed in different aspects including background subtraction, normalization and low-signal filtering before genotype determination. Although many algorithms are sophisticated for these purposes, biases are still present. In the present paper, new algorithms for SNP microarray data analysis and the software, AccuTyping, developed based on these algorithms are described. The algorithms take advantage of a large number of SNPs included in each assay, and the fact that the top and bottom 20% of SNPs can be safely treated as homozygous after sorting based on their ratios between the signal intensities. These SNPs are then used as controls for color channel normalization and background subtraction. Genotype calls are made based on the logarithms of signal intensity ratios using two cutoff values, which were determined after training the program with a dataset of approximately 160,000 genotypes and validated by non-microarray methods. AccuTyping was used to determine >300,000 genotypes of DNA and sperm samples. The accuracy was shown to be >99%. AccuTyping can be downloaded from http://www2.umdnj.edu/lilabweb/publications/AccuTyping.html.

Algorithms↗

PubMed1995

Pre-hospital triage of patients with suspected myocardial infarction. Evaluation of previously developed algorithms and new proposals.

OBJECTIVE: To evaluate previously developed algorithms for the improvement of pre-hospital triage of patients with suspected acute cardiac disease. DESIGN: Prospective study. SUBJECTS: Patients with symptoms of possible cardiac origin, who were seen by a general practitioner and subsequently referred to hospital in the municipality of Rotterdam. METHODS: Prior to hospital admission, patients with suspected acute coronary disease recorded their symptoms by standardized questionnaire and a computerized ECG was made. All patients were hospitalized and a final diagnosis was established. Algorithms proposed by other investigators to distinguish patients with, from those without, acute cardiac disease were tested. MAIN OUTCOME: Identification of patients whose likelihood for acute cardiac pathology was low (stable angina, atypical chest pain, other pathology) or high (myocardial infarction, unstable angina). RESULTS: A total of 1005 patients were studied. Forty-two percent had myocardial infarction or unstable angina pectoris. Evaluation of previously developed algorithms showed that their diagnostic accuracy was poor in the pre-hospital setting. In a separate multivariate analysis, six characteristics from the clinical history and an electrocardiogram appeared to be independently and significantly associated with acute cardiac pathology. The presence of an abnormal ECG proved to be the most important predictor. CONCLUSIONS: The hospital-based algorithms were unsuitable as a predictor for pre-hospital acute cardiac pathology. A new practical hospital admission model was developed, based on six clinical predictors, including analysis of an electrocardiogram. Following appropriate validation, this out-of-hospital protocol may lead to better triage decisions by the general practitioner.

Adult↗

PubMed2000

A fast algorithm for joint reconstruction of ancestral amino acid sequences.

A dynamic programming algorithm is developed for maximum-likelihood reconstruction of the set of all ancestral amino acid sequences in a phylogenetic tree. To date, exhaustive algorithms that find the most likely set of ancestral states (joint reconstruction) have running times that scale exponentially with the number of sequences and are thus limited to very few taxa. The time requirement of our new algorithm scales linearly with the number of sequences and is therefore applicable to practically any number of taxa. A detailed description of the new algorithm and an example of its application to cytochrome b sequences are provided.

Algorithms↗

PubMed2004

The Texas medication algorithm project: clinical results for schizophrenia.

In the Texas Medication Algorithm Project (TMAP), patients were given algorithm-guided treatment (ALGO) or treatment as usual (TAU). The ALGO intervention included a clinical coordinator to assist the physicians and administer a patient and family education program. The primary comparison in the schizophrenia module of TMAP was between patients seen in clinics in which ALGO was used (n = 165) and patients seen in clinics in which no algorithms were used (n = 144). A third group of patients, seen in clinics using an algorithm for bipolar or major depressive disorder but not for schizophrenia, was also studied (n = 156). The ALGO group had modestly greater improvement in symptoms (Brief Psychiatric Rating Scale) during the first quarter of treatment. The TAU group caught up by the end of 12 months. Cognitive functions were more improved in ALGO than in TAU at 3 months, and this difference was greater at 9 months (the final cognitive assessment). In secondary comparisons of ALGO with the second TAU group, the greater improvement in cognitive functioning was again noted, but the initial symptom difference was not significant.

Adolescent↗

PubMed1994

An algorithm for automatically generating protein topology cartoons.

An algorithm is described for automatically generating protein topology cartoons. This algorithm optimally places circles and triangles depicting alpha-helices and beta-strands respectively giving a pictorial topological summary of any protein structure. beta-Sheets, sandwiches and barrels are automatically identified and represented using special templates. The output from this algorithm may be controlled by adjustment of variable weights during the optimization step giving a preferred result. The rules for generating protein toplogy cartoons, including consideration of the handedness of local structure motifs, are discussed. The design of this algorithm is completely general and is easily adapted to include further rules that dictate the generation of the cartoons.

Algorithms↗

PubMed2005

A comparison of fitting growth models with a genetic algorithm and nonlinear regression.

A genetic algorithm (GA), an optimization procedure based on the theory of evolution, was compared with nonlinear regression for the ability of the 2 algorithms to fit the coefficients of poultry growth models. It was hypothesized that the nonlinear approach of using GA to define the parameters of growth equations would better fit the growth equations than the use of nonlinear regression. Two sets of growth data from the literature, consisting of male broiler BW grown for 168 and 170 d, were used in the study. The growth data were fit to 2 forms of the logistic model, the Gompertz, the Gompertz-Laird, and the saturated kinetic models using the SAS nonlinear algorithm (NLIN) procedure and a GA. There were no statistical differences for the comparison of the residuals (the difference between observed and predicted BWs) of growth models fit by a GA or nonlinear regression. The plotted residuals for the nonlinear regression and GA-determined growth values confirmed observations of others that the residuals have oscillations resembling sine waves that are not represented by the growth models. It was found that GA could successfully determine the coefficients of growth equations. A disadvantage of slowness in converging to the solution was found for the GA. The advantage of GA over traditional nonlinear regression is that only ranges need be specified for the parameters of the growth equations, whereas estimates of the coefficients need to be determined, and in some programs the derivatives of the growth equations need to be identified. Depending on the goal of the research, solving multivariable complex functions with an algorithm that considers several solutions at the same time in an evolutionary mode can be considered an advantage especially where there is a chance for the solution to converge on a local optimum when a global optimum is desired. It was concluded that the fitting of the growth equations was not so much a problem with the fitting methodology as it is with the form of the equation.

Algorithms↗