Browse
Submit Data
Databases
API
Help

Dataset Information

30 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

A Fast Hermite Transform.

ABSTRACT: We present algorithms for fast and stable approximation of the Hermite transform of a compactly supported function on the real line, attainable via an application of a fast algebraic algorithm for computing sums associated with a three-term relation. Trade-offs between approximation in bandlimit (in the Hermite sense) and size of the support region are addressed. Numerical experiments are presented that show the feasibility and utility of our approach. Generalizations to any family of orthogonal polynomials are outlined. Applications to various problems in tomographic reconstruction, including the determination of protein structure, are discussed.

SUBMITTER: Leibon G

PROVIDER: S-EPMC2630232 | biostudies-literature | 2008 Dec

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

A Fast Hermite Transform.

Leibon Gregory G Rockmore Daniel N DN Park Wooram W Taintor Robert R Chirikjian Gregory S GS

Theoretical computer science 20081201 2

We present algorithms for fast and stable approximation of the Hermite transform of a compactly supported function on the real line, attainable via an application of a fast algebraic algorithm for computing sums associated with a three-term relation. Trade-offs between approximation in bandlimit (in the Hermite sense) and size of the support region are addressed. Numerical experiments are presented that show the feasibility and utility of our approach. Generalizations to any family of orthogonal ...[more]

PMID: 20027202

Similar Datasets

Using the fast fourier transform in binding free energy calculations.

Project description:According to implicit ligand theory, the standard binding free energy is an exponential average of the binding potential of mean force (BPMF), an exponential average of the interaction energy between the unbound ligand ensemble and a rigid receptor. Here, we use the fast Fourier transform (FFT) to efficiently evaluate BPMFs by calculating interaction energies when rigid ligand configurations from the unbound ensemble are discretely translated across rigid receptor conformations. Results for standard binding free energies between T4 lysozyme and 141 small organic molecules are in good agreement with previous alchemical calculations based on (1) a flexible complex ( R?0.9 for 24 systems) and (2) flexible ligand with multiple rigid receptor configurations ( R?0.8 for 141 systems). While the FFT is routinely used for molecular docking, to our knowledge this is the first time that the algorithm has been used for rigorous binding free energy calculations. © 2017 Wiley Periodicals, Inc.

| S-EPMC5834390 | biostudies-literature

Fast and accurate short read alignment with Burrows-Wheeler transform.

Project description:The enormous amount of short reads generated by the new DNA sequencing technologies call for the development of fast and accurate read alignment programs. A first generation of hash table-based methods has been developed, including MAQ, which is accurate, feature rich and fast enough to align short reads from a single individual. However, MAQ does not support gapped alignment for single-end reads, which makes it unsuitable for alignment of longer reads where indels may occur frequently. The speed of MAQ is also a concern when the alignment is scaled up to the resequencing of hundreds of individuals.We implemented Burrows-Wheeler Alignment tool (BWA), a new read alignment package that is based on backward search with Burrows-Wheeler Transform (BWT), to efficiently align short sequencing reads against a large reference sequence such as the human genome, allowing mismatches and gaps. BWA supports both base space reads, e.g. from Illumina sequencing machines, and color space reads from AB SOLiD machines. Evaluations on both simulated and real data suggest that BWA is approximately 10-20x faster than MAQ, while achieving similar accuracy. In addition, BWA outputs alignment in the new standard SAM (Sequence Alignment/Map) format. Variant calling and other downstream analyses after the alignment can be achieved with the open source SAMtools software package.http://maq.sourceforge.net.

| S-EPMC2705234 | biostudies-literature

Computation of the normalized cross-correlation by fast Fourier transform.

Project description:The normalized cross-correlation (NCC), usually its 2D version, is routinely encountered in template matching algorithms, such as in facial recognition, motion-tracking, registration in medical imaging, etc. Its rapid computation becomes critical in time sensitive applications. Here I develop a scheme for the computation of NCC by fast Fourier transform that can favorably compare for speed efficiency with other existing techniques and may outperform some of them given an appropriate search scenario.

| S-EPMC6147431 | biostudies-literature

Fast and accurate long-read alignment with Burrows-Wheeler transform.

Project description:MotivationMany programs for aligning short sequencing reads to a reference genome have been developed in the last 2 years. Most of them are very efficient for short reads but inefficient or not applicable for reads >200 bp because the algorithms are heavily and specifically tuned for short queries with low sequencing error rate. However, some sequencing platforms already produce longer reads and others are expected to become available soon. For longer reads, hashing-based software such as BLAT and SSAHA2 remain the only choices. Nonetheless, these methods are substantially slower than short-read aligners in terms of aligned bases per unit time.ResultsWe designed and implemented a new algorithm, Burrows-Wheeler Aligner's Smith-Waterman Alignment (BWA-SW), to align long sequences up to 1 Mb against a large sequence database (e.g. the human genome) with a few gigabytes of memory. The algorithm is as accurate as SSAHA2, more accurate than BLAT, and is several to tens of times faster than both.Availabilityhttp://bio-bwa.sourceforge.net

| S-EPMC2828108 | biostudies-literature

Fast and Accurate Calculation of Protein Depth by Euclidean Distance Transform.

Project description:The depth of each atom/residue in a protein structure is a key attribution that has been widely used in protein structure modeling and function annotation. However, the accurate calculation of depth is time consuming. Here, we propose to use the Euclidean distance transform (EDT) to calculate the depth, which conveniently converts the protein structure to a 3D gray-scale image with each pixel labeling the minimum distance of the pixel to the surface of the molecule (i.e. the depth). We tested the proposed EDT method on a set of 261 non-redundant protein structures. The data show that the EDT method is 2.6 times faster than the widely used method by Chakravarty and Varadarajan. The depth value by EDT method is also highly accurate, which is almost identical to the depth calculated by exhaustive search (Pearson's correlation coefficient≈1). We believe the EDT-based depth calculation program can be used as an efficient tool to assist the studies of protein fold recognition and structure-based function annotation.

| S-EPMC4098708 | biostudies-literature

Calculation of Second Virial Coefficients of Atomistic Proteins Using Fast Fourier Transform.

Project description:The second virial coefficient, B2, measures a protein solution's deviation from ideal behavior. It is widely used to predict or explain solubility, crystallization condition, aggregation propensity, and critical temperature for liquid-liquid phase separation. B2 is determined by the interaction energy between two protein molecules and, specifically, by the integration of the Mayer f-function in the relative configurational space (translation and rotation) of the two molecules. Simple theoretical models, such as one attributed to Derjaguin, Landau, Verwey, and Overbeek (DLVO), can fit the dependence of B2 on salt concentrations. However, model parameters derived often are physically unrealistic and hardly transferable from protein to protein. Previous B2 calculations incorporating atomistic details were done with limited sampling in the configurational space, due to enormous computational cost. Our FMAP method, based on fast Fourier transform, can considerably accelerate such calculations, and here we adapt it to calculate B2 values for proteins represented at the atomic level in implicit solvent. After tuning of a single parameter in the energy function, FMAPB2 predicts well the B2 values for lysozyme and other proteins over wide ranges of solvent conditions (salt concentration, pH, and temperature). The method is available as a web server at http://pipe.rcc.fsu.edu/fmapb2 .

| S-EPMC7032052 | biostudies-literature

RAFFT: Efficient prediction of RNA folding pathways using the fast Fourier transform.

Project description:We propose a novel heuristic to predict RNA secondary structure formation pathways that has two components: (i) a folding algorithm and (ii) a kinetic ansatz. This heuristic is inspired by the kinetic partitioning mechanism, by which molecules follow alternative folding pathways to their native structure, some much faster than others. Similarly, our algorithm RAFFT starts by generating an ensemble of concurrent folding pathways ending in multiple metastable structures, which is in contrast with traditional thermodynamic approaches that find single structures with minimal free energies. When we constrained the algorithm to predict only 50 structures per sequence, near-native structures were found for RNA molecules of length ≤ 200 nucleotides. Our heuristic has been tested on the coronavirus frameshifting stimulation element (CFSE): an ensemble of 68 distinct structures allowed us to produce complete folding kinetic trajectories, whereas known methods require evaluating millions of sub-optimal structures to achieve this result. Thanks to the fast Fourier transform on which RAFFT (RNA folding Algorithm wih Fast Fourier Transform) is based, these computations are efficient, with complexity [Formula: see text].

| S-EPMC9455880 | biostudies-literature

Fast parallel algorithms for the x-ray transform and its adjoint.

Project description:Iterative reconstruction methods often offer better imaging quality and allow for reconstructions with lower imaging dose than classical methods in computed tomography. However, the computational speed is a major concern for these iterative methods, for which the x-ray transform and its adjoint are two most time-consuming components. The speed issue becomes even notable for the 3D imaging such as cone beam scans or helical scans, since the x-ray transform and its adjoint are frequently computed as there is usually not enough computer memory to save the corresponding system matrix. The purpose of this paper is to optimize the algorithm for computing the x-ray transform and its adjoint, and their parallel computation.The fast and highly parallelizable algorithms for the x-ray transform and its adjoint are proposed for the infinitely narrow beam in both 2D and 3D. The extension of these fast algorithms to the finite-size beam is proposed in 2D and discussed in 3D.The CPU and GPU codes are available at https://sites.google.com/site/fastxraytransform. The proposed algorithm is faster than Siddon's algorithm for computing the x-ray transform. In particular, the improvement for the parallel computation can be an order of magnitude.The authors have proposed fast and highly parallelizable algorithms for the x-ray transform and its adjoint, which are extendable for the finite-size beam. The proposed algorithms are suitable for parallel computing in the sense that the computational cost per parallel thread is O(1).

| S-EPMC3505201 | biostudies-other

Objective Morphological Quantification of Microscopic Images Using a Fast Fourier Transform (FFT) Analysis.

Project description:Quantification of immunohistochemistry (IHC) and immunofluorescence (IF) using image intensity depends on a number of variables. These variables add a subjective complexity in keeping a standard within and between laboratories. Fast Fourier Transformation (FFT) algorithms, however, allow for a rapid and objective quantification (via statistical analysis) using cell morphologies when the microscopic structures are oriented or aligned. Quantification of alignment is given in terms of a ratio of FFT intensity to the intensity of an orthogonal angle, giving a numerical value of the alignment of the microscopic structures. This allows for a more objective analysis than alternative approaches, which rely upon relative intensities.

| S-EPMC4849894 | biostudies-literature

Suppression law of quantum states in a 3D photonic fast Fourier transform chip.

Project description:The identification of phenomena able to pinpoint quantum interference is attracting large interest. Indeed, a generalization of the Hong-Ou-Mandel effect valid for any number of photons and optical modes would represent an important leap ahead both from a fundamental perspective and for practical applications, such as certification of photonic quantum devices, whose computational speedup is expected to depend critically on multi-particle interference. Quantum distinctive features have been predicted for many particles injected into multimode interferometers implementing the Fourier transform over the optical modes. Here we develop a scalable approach for the implementation of the fast Fourier transform algorithm using three-dimensional photonic integrated interferometers, fabricated via femtosecond laser writing technique. We observe the suppression law for a large number of output states with four- and eight-mode optical circuits: the experimental results demonstrate genuine quantum interference between the injected photons, thus offering a powerful tool for diagnostic of photonic platforms.

| S-EPMC4742850 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data