Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle.

ABSTRACT: This paper shows that the inverse chirp z-transform (ICZT), which generalizes the inverse fast Fourier transform (IFFT) off the unit circle in the complex plane, can also be used with chirp contours that perform partial or multiple revolutions on the unit circle. This is done as a special case of the ICZT, which in algorithmic form has the same computational complexity as the IFFT, i.e., O(n log n). Here we evaluate the ICZT algorithm for chirp contours on the unit circle and show that it is numerically accurate for large areas of the parameter space. The numerical error in this case depends on the polar angle between two adjacent contour points. More specifically, the error profile for a transform of size n is determined by the elements of the Farey sequence of order n - 1. Furthermore, this generalization allows the use of non-orthogonal frequency components, thus lifting one of the main restrictions of the IFFT.

SUBMITTER: Sukhoy V

PROVIDER: S-EPMC7078310 | biostudies-literature | 2020 Mar

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle.

Sukhoy Vladimir V Stoytchev Alexander A

Scientific reports 20200317 1

This paper shows that the inverse chirp z-transform (ICZT), which generalizes the inverse fast Fourier transform (IFFT) off the unit circle in the complex plane, can also be used with chirp contours that perform partial or multiple revolutions on the unit circle. This is done as a special case of the ICZT, which in algorithmic form has the same computational complexity as the IFFT, i.e., O(n log n). Here we evaluate the ICZT algorithm for chirp contours on the unit circle and show that it is num ...[more]

PMID: 32184432

Similar Datasets

Numerical and Experiment Analysis of Sapphire Sandwich-Structure Fabry-Perot Pressure Sensor through Fast Fourier Transform and Mean Square Error Demodulation Algorithm.

Project description:Pressure sensors prepared from sapphire exhibit excellent characteristics, including high-temperature resistance, high hardness, and resistance to electromagnetic interference. A Fast Fourier Transform and Mean Square Error (FFT-MSE) demodulation algorithm was employed to demodulate a sapphire sandwich-structure Fabry-Perot (F-P) pressure sensor. Through simulation analysis, the experimental results indicated that the demodulation error of the air cavity length in the range of 206 μm to 216 μm was less than 0.0008%. Compared to single demodulation methods and combined demodulation methods based on FFT or Minimum Mean Square Error (MMSE), the method proposed in this work reduced the demodulation error by more than three times and increased accuracy by more than six times. The algorithm was utilized to demodulate the sapphire sandwich-structure F-P pressure sensor, and the test results indicated that the fitting error of the sensor was less than 0.025% within the pressure range of 0 MPa to 10 MPa. The repeatability error was less than 0.066%, the zero-point deviation was 1.26%, and the maximum stability deviation was 0.0063% per 30 min. The algorithm effectively demodulated the actual cavity length variation in the sapphire sandwich-structure F-P pressure sensor, providing a solution for the performance evaluation of the sapphire sandwich-structure F-P pressure sensor.

| S-EPMC11313623 | biostudies-literature

Generalizing the inverse FFT off the unit circle.

Project description:This paper describes the first algorithm for computing the inverse chirp z-transform (ICZT) in O(n?log?n) time. This matches the computational complexity of the chirp z-transform (CZT) algorithm that was discovered 50 years ago. Despite multiple previous attempts, an efficient ICZT algorithm remained elusive until now. Because the ICZT can be viewed as a generalization of the inverse fast Fourier transform (IFFT) off the unit circle in the complex plane, it has numerous practical applications in a wide variety of disciplines. This generalization enables exponentially growing or exponentially decaying frequency components, which cannot be done with the IFFT. The ICZT algorithm was derived using the properties of structured matrices and its numerical accuracy was evaluated using automated tests. A modification of the CZT algorithm, which improves its numerical stability for a subset of the parameter space, is also described and evaluated.

| S-EPMC6783538 | biostudies-literature

Rigorous packing of unit squares into a circle.

Project description:This paper considers the task of finding the smallest circle into which one can pack a fixed number of non-overlapping unit squares that are free to rotate. Due to the rotation angles, the packing of unit squares into a container is considerably harder to solve than their circle packing counterparts. Therefore, optimal arrangements were so far proved to be optimal only for one or two unit squares. By a computer-assisted method based on interval arithmetic techniques, we solve the case of three squares and find rigorous enclosures for every optimal arrangement of this problem. We model the relation between the squares and the circle as a constraint satisfaction problem (CSP) and found every box that may contain a solution inside a given upper bound of the radius. Due to symmetries in the search domain, general purpose interval methods are far too slow to solve the CSP directly. To overcome this difficulty, we split the problem into a set of subproblems by systematically adding constraints to the center of each square. Our proof requires the solution of 6, 43 and 12 subproblems with 1, 2 and 3 unit squares respectively. In principle, the method proposed in this paper generalizes to any number of squares.

| S-EPMC6394747 | biostudies-literature

Stress-field driven conformal lattice design using circle packing algorithm.

Project description:Reliable extreme lightweight is the pursuit in many high-end manufacturing areas. Aided by additive manufacturing (AM), lattice material has become a promising candidate for lightweight optimization. Configuration of lattice units at the material level and the distribution of lattice units at the structure level are the two main research directions recently. This paper proposes a generative strategy for lattice infilling optimization using organic strut-based lattices. A sphere packing algorithm driven by von Mises stress fields determines the lattice distribution density. Two typical configurations, Voronoi polygons and Delaunay triangles, are adopted to constitute the frames, respectively. Based on finite element analysis, a simplified truss model is utilized to evaluate the lattice distribution in terms of mechanical properties. Optimization parameters, including node number, mapping gradient, and the range of varying circle size, are investigated through the genetic algorithm (GA). Multiple feasible solutions are obtained for further solidification modelling. To avoid the stress concentration, the organic strut-based lattice units are created by the iso-surface modelling method. The effectiveness of the proposed generative approach is illustrated through a classical 3-point bending beam. The stiffness of the optimized structure, verified through experimental testing, has increased 80% over the one using the traditional uniform body center cubic (BCC) lattice distribution.

| S-EPMC10031376 | biostudies-literature

An efficient error correction algorithm using FM-index.

Project description:High-throughput sequencing offers higher throughput and lower cost for sequencing a genome. However, sequencing errors, including mismatches and indels, may be produced during sequencing. Because, errors may reduce the accuracy of subsequent de novo assembly, error correction is necessary prior to assembly. However, existing correction methods still face trade-offs among correction power, accuracy, and speed.We develop a novel overlap-based error correction algorithm using FM-index (called FMOE). FMOE first identifies overlapping reads by aligning a query read simultaneously against multiple reads compressed by FM-index. Subsequently, sequencing errors are corrected by k-mer voting from overlapping reads only. The experimental results indicate that FMOE has highest correction power with comparable accuracy and speed. Our algorithm performs better in long-read than short-read datasets when compared with others. The assembly results indicated different algorithms has its own strength and weakness, whereas FMOE is good for long or good-quality reads.FMOE is freely available at https://github.com/ythuang0522/FMOC .

| S-EPMC5704532 | biostudies-literature

Circle-to-circle amplification for precise and sensitive DNA analysis.

Project description:We present a tightly controlled process for strand-specific amplification of circularized DNA molecules. Tandem repeated complements of DNA circles are generated by rolling-circle replication, and converted to monomer circles of opposite polarity to that of the starting material. These circles are then subjected to one more round of rolling-circle replication and circularization, and the process can be further repeated. The method can be directed to produce single-stranded circular or linear monomers, or linear concatemers of the desired polarity. The reaction is not product inhibited, and can yield approximately 100-fold higher concentrations of monomer products than PCR. Each generation of the amplification process proceeds in a linear fashion, ensuring precise quantification. The procedure is suitable for parallel amplification of large numbers of DNA circles, because the few cycles and the robust reaction mechanism preserves the proportion of amplified molecules. We demonstrate the utility of the method for multiplexed genotyping of polymorphic loci and for quantitative DNA analysis.

| S-EPMC384784 | biostudies-literature

Numerical and Experimental Evaluation of Error Estimation for Two-Way Ranging Methods.

Project description:The Two-Way Ranging (TWR) method is commonly used for measuring the distance between two wireless transceiver nodes, especially when clock synchronization between the two nodes is not available. For modeling the time-of-flight (TOF) error between two wireless transceiver nodes in TWR, the existing error model, described in the IEEE 802.15.4-2011 standard, is solely based on clock drift. However, it is inadequate for in-depth comparative analysis between different TWR methods. In this paper, we propose a novel TOF Error Estimation Model (TEEM) for TWR methods. Using the proposed model, we evaluate the comparative analysis between different TWR methods. The analytical results were validated with both numerical simulation and experimental results. Moreover, we demonstrate the pitfalls of the symmetric double-sided TWR (SDS-TWR) method, which is the most highlighted TWR method in the literature because of its highly accurate performance on clock-drift error reduction when reply times are symmetric. We argue that alternative double-sided TWR (AltDS-TWR) outperforms SDS-TWR. The argument was verified with both numerical simulation and experimental evaluation results.

| S-EPMC6387385 | biostudies-literature

ECHO: a reference-free short-read error correction algorithm.

Project description:Developing accurate, scalable algorithms to improve data quality is an important computational challenge associated with recent advances in high-throughput sequencing technology. In this study, a novel error-correction algorithm, called ECHO, is introduced for correcting base-call errors in short-reads, without the need of a reference genome. Unlike most previous methods, ECHO does not require the user to specify parameters of which optimal values are typically unknown a priori. ECHO automatically sets the parameters in the assumed model and estimates error characteristics specific to each sequencing run, while maintaining a running time that is within the range of practical use. ECHO is based on a probabilistic model and is able to assign a quality score to each corrected base. Furthermore, it explicitly models heterozygosity in diploid genomes and provides a reference-free method for detecting bases that originated from heterozygous sites. On both real and simulated data, ECHO is able to improve the accuracy of previous error-correction methods by several folds to an order of magnitude, depending on the sequence coverage depth and the position in the read. The improvement is most pronounced toward the end of the read, where previous methods become noticeably less effective. Using a whole-genome yeast data set, it is demonstrated here that ECHO is capable of coping with nonuniform coverage. Also, it is shown that using ECHO to perform error correction as a preprocessing step considerably facilitates de novo assembly, particularly in the case of low-to-moderate sequence coverage depth.

| S-EPMC3129260 | biostudies-literature

HALC: High throughput algorithm for long read error correction.

Project description:BackgroundThe third generation PacBio SMRT long reads can effectively address the read length issue of the second generation sequencing technology, but contain approximately 15% sequencing errors. Several error correction algorithms have been designed to efficiently reduce the error rate to 1%, but they discard large amounts of uncorrected bases and thus lead to low throughput. This loss of bases could limit the completeness of downstream assemblies and the accuracy of analysis.ResultsHere, we introduce HALC, a high throughput algorithm for long read error correction. HALC aligns the long reads to short read contigs from the same species with a relatively low identity requirement so that a long read region can be aligned to at least one contig region, including its true genome region's repeats in the contigs sufficiently similar to it (similar repeat based alignment approach). It then constructs a contig graph and, for each long read, references the other long reads' alignments to find the most accurate alignment and correct it with the aligned contig regions (long read support based validation approach). Even though some long read regions without the true genome regions in the contigs are corrected with their repeats, this approach makes it possible to further refine these long read regions with the initial insufficient short reads and correct the uncorrected regions in between. In our performance tests on E. coli, A. thaliana and Maylandia zebra data sets, HALC was able to obtain 6.7-41.1% higher throughput than the existing algorithms while maintaining comparable accuracy. The HALC corrected long reads can thus result in 11.4-60.7% longer assembled contigs than the existing algorithms.ConclusionsThe HALC software can be downloaded for free from this site: https://github.com/lanl001/halc .

| S-EPMC5382505 | biostudies-literature

EC: an efficient error correction algorithm for short reads.

Project description:BackgroundIn highly parallel next-generation sequencing (NGS) techniques millions to billions of short reads are produced from a genomic sequence in a single run. Due to the limitation of the NGS technologies, there could be errors in the reads. The error rate of the reads can be reduced with trimming and by correcting the erroneous bases of the reads. It helps to achieve high quality data and the computational complexity of many biological applications will be greatly reduced if the reads are first corrected. We have developed a novel error correction algorithm called EC and compared it with four other state-of-the-art algorithms using both real and simulated sequencing reads.ResultsWe have done extensive and rigorous experiments that reveal that EC is indeed an effective, scalable, and efficient error correction tool. Real reads that we have employed in our performance evaluation are Illumina-generated short reads of various lengths. Six experimental datasets we have utilized are taken from sequence and read archive (SRA) at NCBI. The simulated reads are obtained by picking substrings from random positions of reference genomes. To introduce errors, some of the bases of the simulated reads are changed to other bases with some probabilities.ConclusionsError correction is a vital problem in biology especially for NGS data. In this paper we present a novel algorithm, called Error Corrector (EC), for correcting substitution errors in biological sequencing reads. We plan to investigate the possibility of employing the techniques introduced in this research paper to handle insertion and deletion errors also.Software availabilityThe implementation is freely available for non-commercial purposes. It can be downloaded from: http://engr.uconn.edu/~rajasek/EC.zip.

| S-EPMC4674864 | 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