检索结果-内蒙古大学图书馆

Data structures and compression algorithms for high-throughput sequencing technologies

BMC BIOINFORMATICS 2010年第1期11卷 1-12页

作者： Daily, Kenny Rigor, Paul Christley, Scott Xie, Xiaohui Baldi, Pierre Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA Univ Calif Irvine Inst Genom & Bioinformat Irvine CA 92697 USA Univ Calif Irvine Dept Math Irvine CA 92697 USA Univ Calif Irvine Ctr Complex Biol Syst Irvine CA 92697 USA Univ Calif Irvine Dept Biol Chem Irvine CA 92697 USA

Background: High-throughput sequencing (HTS) technologies play important roles in the life sciences by allowing the rapid parallel sequencing of very large numbers of relatively short nucleotide sequences, in applications ranging from genome sequencing and resequencing to digital microarrays and ChIP-Seq experiments. As experiments scale up, HTS technologies create new bioinformatics challenges for the storage and sharing of HTS data. Results: We develop data structures and compression algorithms for HTS data. A processing stage maps short sequences to a reference genome or a large table of sequences. Then the integers representing the short sequence absolute or relative addresses, their length, and the substitutions they may contain are compressed and stored using various entropy coding algorithms, including both old and new fixed codes (e. g Golomb, Elias Gamma, MOV) and variable codes (e. g. Huffman). The general methodology is illustrated and applied to several HTS data sets. Results show that the information contained in HTS files can be compressed by a factor of 10 or more, depending on the statistical properties of the data sets and various other choices and constraints. Our algorithms fair well against general purpose compression programs such as gzip, bzip2 and 7zip;timing results show that our algorithms are consistently faster than the best general purpose compression programs. Conclusions: It is not likely that exactly one encoding strategy will be optimal for all types of HTS data. Different experimental conditions are going to generate various data distributions whereby one encoding strategy can be more effective than another. We have implemented some of our encoding algorithms into the software package GenCompress which is available upon request from the authors. With the advent of HTS technology and increasingly new experimental protocols for using the technology, sequence databases are expected to continue rising in size. The methodology we have pro

关键词： Reference Genome Encode Strategy compression algorithm Good compression Huffman Code

来源：评论

学校读者我要写书评

暂无评论

A Method for Estimating the Time Intervals between Transactions in Speech-compression algorithms

引用

AUTOMATIC DOCUMENTATION AND MATHEMATICAL LINGUISTICS 2017年第5期51卷 214-219页

作者： Larkin, E. V. Bogomolov, A. V. Privalov, A. N. Tula State Univ Tula 300012 Russia Mil Acad Gen Staff Armed Forces Russia Moscow 119571 Russia Tula State Pedag Univ Tula 300026 Russia

A method is described for estimating the time intervals between transactions in speech-compression algorithms based on a complex Markov process, each state of which is a 2-parallel Markov process that describes the "competition" between the source of the signal that fills the buffer and the receiver of the signal that empties the buffer. The complex Markov process is transformed into an ordinary process, whose states simulate the number of buffer cells that are filled at the current time. This makes it possible to obtain a dependence connecting the probability of failure, the amount of buffer memory, and the mathematical expectations of the times of filling and emptying the buffer.

关键词： speech compression compression algorithm audio data processing Markov process data buffering

来源：评论

学校读者我要写书评

暂无评论

Comparison of compression algorithms on Vehicle Communications System

Comparison of Compression Algorithms on Vehicle Communicatio...

引用

IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC)

作者： Shuai, Chunyan Li, Siqi Liu, Hongrui Kunming Univ Sci & Technol Fac Elect Power Engn Kunming Peoples R China

ISBN: (纸本)9781479919802

in order to improve the compression ratio, most of improved compression methods require more memory and CPU time. But these improvements are not suitable for embedded system with limited-resource, especially for vehicle communications system. In order to communicate realtimely by lower costs, the huge and short data are compressed before transmitting. This paper discusses several original lossless compression methods including their principles, features, advantages and disadvantages respectively. Experiments on the front vehicle system show that the L777, PPM and BWT are more suitable for the automobile communication data, and they have better compression ratios, simpler coding, lower CPU and memory costs.

关键词： lossless data compression compression algorithm vehicle communication encode decode

来源：评论

学校读者我要写书评

暂无评论

Analysis of the Effects of Soft Errors on compression algorithms Through Fault Injection Inside Program Variables 17

Analysis of the Effects of Soft Errors on Compression Algori...

引用

17th IEEE Latin-American Test Symposium (LATS)

作者： Avramenko, S. Reorda, M. Sonza Violante, M. Fey, G. Politecn Torino Turin Italy German Aerosp Ctr DLR Bremen Germany

ISBN: (纸本)9781509013319

Data logging applications, such as those deployed in satellite launchers to acquire telemetry data, may require compression algorithms to cope with large amounts of data as well as limited storage and communication capabilities. When commercial-off-the-shelf hardware components are used to implement such applications, radiation-induced soft errors may occur, especially during the last stages of the launcher cruise, potentially affecting the algorithm execution. The purpose of this work is to analyze two compression algorithms using fault injection to evaluate their robustness against soft errors. The main contribution of the work is the analysis of the compression algorithm susceptibility by attacking their data structures (also referred as program variables) rather than the memory elements of the computing platform in charge of the algorithm execution. This approach is agnostic of the downstream implementation details. Instead, the intrinsic robustness of compression algorithms can be evaluated quickly, and system-level decisions can be taken before the computing platform is finalized.

关键词： Soft Errors compression algorithm Reliability High-level Fault Injection

来源：评论

学校读者我要写书评

暂无评论

ReCoil - an algorithm for compression of extremely large datasets of DNA data

引用

algorithmS FOR MOLECULAR BIOLOGY 2011年第1期6卷 23-23页

作者： Yanovsky, Vladimir Univ Toronto Dept Comp Sci Toronto ON Canada

The growing volume of generated DNA sequencing data makes the problem of its long term storage increasingly important. In this work we present ReCoil - an I/O efficient external memory algorithm designed for compression of very large collections of short reads DNA data. Typically each position of DNA sequence is covered by multiple reads of a short read dataset and our algorithm makes use of resulting redundancy to achieve high compression rate. While compression based on encoding mismatches between the dataset and a similar reference can yield high compression rate, good quality reference sequence may be unavailable. Instead, ReCoil's compression is based on encoding the differences between similar or overlapping reads. As such reads may appear at large distances from each other in the dataset and since random access memory is a limited resource, ReCoil is designed to work efficiently in external memory, leveraging high bandwidth of modern hard disk drives.

关键词： High Throughput Sequencing Random Access Memory compression algorithm compression Rate External Memory

来源：评论

学校读者我要写书评

暂无评论

Data compression and learning in time sequences analysis

引用

PHYSICA D-NONLINEAR PHENOMENA 2003年第1-2期180卷 92-107页

作者： Puglisi, A Benedetto, D Caglioti, E Loreto, V Vulpiani, A Univ Roma La Sapienza Dept Phys I-00185 Rome Italy INFM Ctr Stat Mech & Complex Rome Italy Univ Roma La Sapienza Dept Math I-00198 Rome Italy

Motivated by the problem of the definition of a distance between two sequences of characters, we investigate the so-called learning process of a typical sequential data compression schemes. We focus on the problem of how a compression algorithm optimizes its features at the interface between two different sequences A and B while zipping the sequence A + B obtained by simply appending B after A. We show the existence of a scaling function (the "learning function") which rules the way in which the compression algorithm learns a sequence B after having compressed a sequence A. In particular it turns out that there exists a cross-over length for the sequence B, which depends on the relative entropy between A and B, below which the compression algorithm does not learn the sequence B (measuring in this way the cross-entropy between A and B) and above which it starts learning B, i.e. optimizing the compression using the specific features of B. We check the scaling on three main classes of systems: Bernoulli schemes, Markovian sequences and the symbolic dynamic generated by a nontrivial chaotic system (the Lozi map). As a last application of the method we present the results of a recognition experiment, namely recognize which dynamical systems produced a given time sequence. We finally point out the potentiality of these results for segmentation purposes, i.e. the identification of homogeneous sub-sequences in heterogeneous sequences (with applications in various fields from genetic to time-series analysis). (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： time sequence analysis compression algorithm characterization of complexity

来源：评论

学校读者我要写书评

暂无评论

Adaptive-Compi: Enhancing Mpi-Based Applications' Performance and Scalability by using Adaptive compression

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2011年第1期25卷 93-114页

作者： Filgueira, Rosa Singh, David E. Carretero, Jesus Calderon, Alejandro Garcia, Felix Univ Carlos III Madrid Dept Comp Sci Madrid Spain Univ Politecn Madrid Dept Comp Architecture E-28040 Madrid Spain

This paper presents an optimization of MPI communication, called Adaptive-CoMPI, based on runtime compression of MPI messages exchanged by applications. The technique developed can be used for any application, because its implementation is transparent for the user, and integrates different compression algorithms for both MPI collective and point-to-point primitives. Furthermore, compression is turned on and off and the most appropriate compression algorithms are selected at runtime, depending on the characteristics of each message, the network behavior, and compression algorithm behavior, following a runtime adaptive strategy. Our system can be optimized for a specific application, through a guided strategy, to reduce the runtime strategy overhead. Adaptive-CoMPI has been validated using several MPI benchmarks and real HPC applications. Results show that, in most cases, by using adaptive compression, communication time is reduced, enhancing application performance and scalability.

关键词： adaptive system cluster architecture compression algorithm heuristics MPI library parallel technique

来源：评论

学校读者我要写书评

暂无评论

Boosting forward-time population genetic simulators through genotype compression

引用

BMC BIOINFORMATICS 2013年第1期14卷 1-12页

作者： Ruths, Troy Nakhleh, Luay Rice Univ Dept Comp Sci Houston TX 77251 USA

Background: Forward-time population genetic simulations play a central role in deriving and testing evolutionary hypotheses. Such simulations may be data-intensive, depending on the settings to the various parameters controlling them. In particular, for certain settings, the data footprint may quickly exceed the memory of a single compute node. Results: We develop a novel and general method for addressing the memory issue inherent in forward-time simulations by compressing and decompressing, in real-time, active and ancestral genotypes, while carefully accounting for the time overhead. We propose a general graph data structure for compressing the genotype space explored during a simulation run, along with efficient algorithms for constructing and updating compressed genotypes which support both mutation and recombination. We tested the performance of our method in very large-scale simulations. Results show that our method not only scales well, but that it also overcomes memory issues that would cripple existing tools. Conclusions: As evolutionary analyses are being increasingly performed on genomes, pathways, and networks, particularly in the era of systems biology, scaling population genetic simulators to handle large-scale simulations is crucial. We believe our method offers a significant step in that direction. Further, the techniques we provide are generic and can be integrated with existing population genetic simulators to boost their performance in terms of memory usage.

关键词： Memory Usage compression algorithm compression Technique Lossless compression Data Request

来源：评论

学校读者我要写书评

暂无评论

An on-chip cache compression technique to reduce decompression overhead and design complexity

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2000年第15期46卷 1365-1382页

作者： Lee, JS Hong, WK Kim, SD Yonsei Univ Parallel Proc Syst Lab Dept Comp Sci Seodaemun Ku Seoul 120749 South Korea

This research explores a compressed memory hierarchy model which can increase both the effective memory space and bandwidth of each level of memory hierarchy. It is well known that decompression time causes a critical effect to the memory access time and variable-sized compressed blocks tend to increase the design complexity of the compressed memory systems. This paper proposes a selective compressed memory system (SCMS) incorporating the compressed cache architecture and its management method. To reduce or hide decompression overhead, this SCMS employs several effective techniques, including selective compression, parallel decompression and the use of a decompression buffer. In addition, fixed memory space allocation method is used to achieve efficient management of the compressed blocks. Trace-driven simulation shows that the SCMS approach can not only reduce the on-chip cache miss ratio and data traffic by about 35% and 53%, respectively, but also achieve a 20% reduction in average memory access time (AMAT) over conventional memory systems (CMS). Moreover, this approach can provide both lower memory traffic at a lower cost than CMS with some architectural enhancement. Most importantly, the SCMS is a more attractive approach for future computer systems because it offers high performance in cases of long DRAM latency and limited bus bandwidth. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： on-line data compression compression algorithm memory hierarchy compressed memory system cache architecture memory performance evaluation

来源：评论

学校读者我要写书评

暂无评论

Data compression Versus Signal Fidelity Tradeoff in Wired-OR Analog-to-Digital Compressive Arrays for Neural Recording

引用

IEEE TRANSACTIONS ON BIOMEDICAL CIRCUITS AND SYSTEMS 2023年第4期17卷 754-767页

作者： Yan, Pumiao Akhoundi, Arash Shah, Nishal P. Tandon, Pulkit Muratore, Dante G. Chichilnisky, E. J. Murmann, Boris Stanford Univ Dept Elect Engn Stanford CA 94305 USA Delft Univ Technol Microelect Dept NL-2628 CD Delft Netherlands Stanford Univ Dept Neurosurg Stanford CA 94305 USA Stanford Univ Dept Neurosurg & Ophthalmol Hansen Expt Phys Lab Stanford CA 94305 USA

Future high-density and high channel count neural interfaces that enable simultaneous recording of tens of thousands of neurons will provide a gateway to study, restore and augment neural functions. However, building such technology within the bit-rate limit and power budget of a fully implantable device is challenging. The wired-OR compressive readout architecture addresses the data deluge challenge of a high channel count neural interface using lossy compression at the analog-to-digital interface. In this article, we assess the suitability of wired-OR for several steps that are important for neuroengineering, including spike detection, spike assignment and waveform estimation. For various wiring configurations of wired-OR and assumptions about the quality of the underlying signal, we characterize the trade-off between compression ratio and task-specific signal fidelity metrics. Using data from 18 large-scale microelectrode array recordings in macaque retina ex vivo, we find that for an event SNR of 7-10, wired-OR correctly detects and assigns at least 80% of the spikes with at least 50x compression. The wired-OR approach also robustly encodes action potential waveform information, enabling downstream processing such as cell-type classification. Finally, we show that by applying an LZ77-based lossless compressor (gzip) to the output of the wired-OR architecture, 1000x compression can be achieved over the baseline recordings.

关键词： A/D conversion analog-to-digital compression brain-machine interfaces compression algorithm neural interfaces

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：