BLAST is the most popular bioinformatics tool and is used to run millions of queries each day. However, evaluating such queries is slow, taking typically minutes on modern workstations. Therefore, continuing evolution of BLAST--by improving its algorithms and optimizations--is essential to improve search times in the face of exponentially increasing collection sizes. We present an optimization to the first stage of the BLAST algorithm specifically designed for protein search. It produces the same results as NCBI-BLAST but in around 59% of the time on Intel-based platforms; we also present results for other popular architectures. Overall, this is a saving of around 15% of the total typical BLAST search time. Our approach uses a deterministic finite automaton (DFA), inspired by the original scheme used in the 1990 BLAST algorithm. The techniques are optimized for modern hardware, making careful use of cache-conscious approaches to improve speed. Our optimized DFA approach has been integrated into a new version of BLAST that is freely available for download at http://www.fsa-blast.org/.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1089/cmb.2006.13.965 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Shannon Entropy Computations in Navier-Stokes Flow Problems Using the Stochastic Finite Volume Method.
Entropy (Basel)
January 2025
Faculty of Civil Engineering, Architecture and Environmental Engineering, Lodz University of Technology, 90-924 Łódź, Poland.
The main aim of this study is to achieve the numerical solution for the Navier-Stokes equations for incompressible, non-turbulent, and subsonic fluid flows with some Gaussian physical uncertainties. The higher-order stochastic finite volume method (SFVM), implemented according to the iterative generalized stochastic perturbation technique and the Monte Carlo scheme, are engaged for this purpose. It is implemented with the aid of the polynomial bases for the pressure-velocity-temperature (PVT) solutions, for which the weighted least squares method (WLSM) algorithm is applicable.
View Article and Find Full Text PDFEnhancing Biomechanical Simulations Based on a Posteriori Error Estimates: The Potential of Dual-Weighted Residual-Driven Adaptive Mesh Refinement.
Int J Numer Method Biomed Eng
January 2025
Center of Mathematics, University of the Republic Uruguay, Montevideo, Uruguay.
The finite-element method (FEM) is a well-established procedure for computing approximate solutions to deterministic engineering problems described by partial differential equations. FEM produces discrete approximations of the solution with a discretisation error that can be quantified with a posteriori error estimates. The practical relevance of error estimates for biomechanics problems, especially for soft tissue where the response is governed by large strains, is rarely addressed.
View Article and Find Full Text PDFDeterministic patterns in single-cell transcriptomic data.
NPJ Syst Biol Appl
January 2025
School of Biological Sciences, University of Edinburgh, Edinburgh, UK.
We report the existence of deterministic patterns in statistical plots of single-cell transcriptomic data. We develop a theory showing that the patterns are neither artifacts introduced by the measurement process nor due to underlying biological mechanisms. Rather they naturally emerge from finite sample size effects.
View Article and Find Full Text PDFFractional and stochastic modeling of breast cancer progression with real data validation.
PLoS One
January 2025
Biology Department, Faculty of Science, Islamic University of Madinah, Madinah, Saudi Arabia.
This study presents a novel approach to modeling breast cancer dynamics, one of the most significant health threats to women worldwide. Utilizing a piecewise mathematical framework, we incorporate both deterministic and stochastic elements of cancer progression. The model is divided into three distinct phases: (1) initial growth, characterized by a constant-order Caputo proportional operator (CPC), (2) intermediate growth, modeled by a variable-order CPC, and (3) advanced stages, capturing stochastic fluctuations in cancer cell populations using a stochastic operator.
View Article and Find Full Text PDFEnumerating Finitary Processes.
Entropy (Basel)
December 2024
DPMMS, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK.
We show how to efficiently enumerate a class of finite-memory stochastic processes using the causal representation of ϵ-machines. We characterize ϵ-machines in the language of automata theory and adapt a recent algorithm for generating accessible deterministic finite automata, pruning this over-large class down to that of ϵ-machines. As an application, we exactly enumerate topological ϵ-machines up to eight states and six-letter alphabets.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!