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
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.
9769309
Bioinformatic searches using a single-chip shared-memory multiprocessor
A single-chip shared-memory multiprocessor architecture is introduced which is particularly well suited to common bioinformatic computing tasks. The architecture uses asynchronous bus interfaces to create an integrated circuit design methodology allowing for scaling of the multiprocessor with very little design effort. A key aspect of this design methodology is that it is not necessary to expend significant design resources and chip area on the clock tree. An analysis of the Smith-Waterman alignment algorithm running on this architecture shows that the performance penalty due to increased bus latency compared to a fully synchronous architecture is negligible.
1570646
Covariance Searches for ncRNA Gene Finding
The use of covariance models for non-coding RNA gene finding is extremely powerful and also extremely computationally demanding. A major reason for the high computational burden of this algorithm is that the search proceeds through every possible start position in the database and every possible sequence length between zero and a user-defined maximum length at every one of these start positions. Furthermore, for every start position and sequence length, all possible combinations of insertions and deletions leading to the given sequence length are searched. It has been previously shown that a large portion of this search space is nowhere near any database match observed in practice and that the search space can be limited significantly with little change in expected search results. In this work a different approach is taken in which the space of starting positions, sequence lengths, and insertion/deletion patterns is searched using a genetic algorithm
9066025
Truncated Profile Hidden Markov Models
The profile hidden Markov model (HMM) is a powerful method for remote homolog database search. However, evaluating the score of each database sequence against a profile HMM is computationally demanding. The computation time required for score evaluation is proportional to the number of states in the profile HMM. This paper examines whether the number of states can be truncated without reducing the ability of the HMM to find proteins containing members of a protein domain family. A genetic algorithm (GA) is presented which finds a good truncation of the HMM states. The results of using truncation on searches of the yeast, E. coli, and pig genomes for several different protein domain families is shown.
6383347
A Scalable Coprocessor for Bioinformatic Sequence Alignments
A hardware coprocessor for the rapid calculation of bioinformatic sequence alignments is presented. The coprocessor uses a globally-asynchronous locally-synchronous (GALS) design style which makes the coprocessor much easier to scale as CMOS feature sizes decrease. The coprocessor is intended to be implemented on a single integrated circuit along with a simple 32-bit RISC processor and memory system. The specific sequence alignment algorithm implemented is that of Smith and Waterman, but the general design strategy could be extended to other bioinformatic sequence alignment algorithms.
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.