43472650
Covariance-Model-Based RNA Gene Finding: Using Dynamic Programming versus Evolutionary Computing
This chapter compares the traditional dynamic programming RNA gene finding methodolgy with an alternative evolutionary computation approach. Both methods take a set of estimated covariance model parameters for a non-coding RNA family as given. The difference lies in how the score of a database position with respect to the covariance model is computed. Dynamic programming returns an exact score at the cost of very large computational resource usage. Presently, databases are prefiltered using non-structural algorithms such as BLAST in order to make dynamic programming search feasible. The evolutionary computing approach allows for faster approximate search, but uses the RNA secondary structure information in the covariance model from the start.
23808436
Homology search with binary and trinary scoring matrices
Protein homology search can be accelerated with the use of bit-parallel algorithms in conjunction with constraints on the values contained in the scoring matrices. Trinary scoring matrices (containing only the values -1, 0, and 1) allow for significant acceleration without significant reduction in the receiver operating characteristic (ROC) score of a Smith-Waterman search. Binary scoring matrices (containing the values 0 and 1) result in some reduction in ROC score, but result in even more acceleration. Binary scoring matrices and five-bit saturating scores can be used for fast prefilters to the Smith-Waterman algorithm.
14258567
Similarity Searches in Computer Security
The reuse of algorithms and hardware developed for searches of large molecular biologic databases is examined for detecting new variants of computer attacks before they can inflict damage. New attacks are viewed as evolutions of previous attacks, with associated mutations, insertions, and deletions from either machine code or text script sequences. Similarity searches are done between previous attacks and internet packet contents in real time. Single integrated circuits capable of comparing five-hundred-byte query sequences to nearly two million bytes of internet traffic per second are
38071731
A Fast Approximate Covariance-Model-Based Database Search Method for Non-coding RNA
A covariance-model-based search method for non-coding RNA genes is proposed which is much faster than dynamic programming, but which is shown to be very effective in experimental tests. The method incorporates secondary structure information in the entire first pass of the database, unlike the usual primary-sequence-only pre-filters applied when using dynamic programming. An iterative alignment refining algorithm which starts at an ungapped alignment and successively selects alignment breakpoints gives only an approximation to the optimal alignment, but appears to be sufficient for gene localization.
5739340
Searching for protein classification features
A genetic algorithm is used to search for a set of classification features for a protein superfamily which is as unique as possible to the superfamily. These features may then be used for very fast classification of a query sequence into a protein superfamily. The features are based on windows onto modified consensus sequences of multiple aligned members of a training set for the protein superfamily. The efficacy of the method is demonstrated using receiver operating characteristic (ROC) values and the performance of resulting algorithm is compared with other database search algorithms
14147758
RNA Gene Finding with Biased Mutation Operators
The use of genetic algorithms for non-coding RNA gene finding has previously been investigated and found to be a potentially viable method for accelerating covariance-model-based database search relative to full dynamic-programming methods. The mutation operators in previous work chose new alignment insertion and deletion locations uniformly over the length of the model consensus sequence. Since the covariance models are estimated from multiple known members of a non-coding RNA family, information is available as to the likelihood of insertions or deletions at the individual model positions. This information is implicit in the state-transition parameters of the estimated covariance models. In the current work, the use of mutation operators which are biased toward selection of insertions and deletions at model positions with low insertion or deletion penalties is examined in hopes of speeding up convergence. The performance of the biased and unbiased mutation operators is compared. Both biased and unbiased genetic algorithms are also compared to a steepest-descent algorithm, which is a comparison lacking in prior work
33128388
PULSAR: a personalized microcomputer-based system for keyword search and retrieval of literature information
(18) Kowalski, B. R.; Bender, C. F. “Pattern Recognition. 11. Linear and Nonlinear Methods for Displaying Chemical Data”. J. Am. Chem. Soc. (16) Everitt, B. S. “Unresolved Problems in Cluster Analysis”. Biometrics 1979. 35. 169-181. . . ., 1 (17) Williams, W. T.; Lance, G. N. “Hierarchical Classificatory Methods”. In “Statistical methods for Digital Computers”; Enslein, K., et al., Eids.; 1973, 95, 686-693. (19) Everitt, B. S.; “Graphical Techniques for Multivariate Data”; HeineWiley: New York, 1977; Va. 111. mann: 1978.
7832522
Towards mechanical solution of the Kahan Ellipse Problem 1
Tarski (1948) gave a quantifier elimination procedure for elementary algebra and geometry which, when implemented, was found to be impractical. Collins (1975) gave a different and far more efficient algorithm, which has revived interest in the feasibility of quantifier elimination as a means of solving nontrivial problems in elementary algebra and geometry. Collins' algorithm has recently been implemented (1981). Experience so far obtained with the software indicates that, while some worthwhile problems can now be solved, it is desirable to find methods for improving performance. In this paper we report on several such methods, that we have developed in the course of applying the Collins algorithm to the Kahan ellipse problem. These methods have yielded substantial performance improvements; in fact, they have made feasible computations relating to the Kahan problem that initially could not be carried out at all in our computing environment. We are pursuing the further development of these techniques, with the goal of eventually producing a solution to the Kahan problem using the Collins algorithm.