Genomic Compression: From Information Theory to Parallel Algorithms

基因组压缩：从信息论到并行算法

基本信息

批准号：
9259954
负责人：
Olgica Milenkovic
金额：
$ 30.35万
依托单位：
UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN
依托单位国家：
美国
项目类别：
财政年份：
2015
资助国家：
美国
起止时间：
2015-06-01 至 2019-05-31
项目状态：
已结题

来源：
https://reporter.nih.gov/project-details/9259954
关键词：
Address Algorithms Archives Area Arithmetic Big Data Biological Biomedical Research Categories Chromosomes Code Computer software DNA sequencing Data Data Compression Databases Detection Dimensions Disease Ensure Evaluation Future Genome Genomics Goals Government Growth Health Care Research Imagery Individual Information Theory Knowledge Measurement Medical Research Methods Mining Modeling Modernization Nucleotides Outcome Outcomes Research Performance Positioning Attribute Process Property Psychological Techniques Research Scheme Side Sorting - Cell Movement Speed Statistical Data Interpretation Techniques The Cancer Genome Atlas Time Trees United States National Institutes of Health Weight base cancer genome clinical practice computing resources cost crowdsourcing data access data format design disease-causing mutation experience functional genomics genomic data improved indexing novel novel strategies operation parallel computer personalized medicine programs public health relevance signal processing statistics theories whole genome

项目摘要

DESCRIPTION (provided by applicant): One of the highest priorities of modern healthcare research and practice is to identify genomic changes and markers that predispose individuals to debilitating diseases or make them more responsive to certain therapies and emerging treatments. Timely discovery and knowledge mining in this area of medical research is largely enabled by massive DNA sequencing and functional genomic data, the volumes of which are expected to experience drastic growth in the near future. It is therefore of paramount importance to develop efficient, accurate, and low-latency data compression and decompression techniques that will allow for fast exchange, dissemination, random access, visualization and search of diversely formatted genomic information. The use of specialized compression methods for biological data will ensure unprecedented growth of NIH databases and their utility, new uses of crowd-sourced computing in medical research, and large scale dissemination of experimental results. Specific aims of the proposal include developing parallel, task-oriented algorithms for a reference-based and reference-free compression of reads and whole genomes; b) lossy compression of quality scores; and c) compression of functional genomic data. Although the three data categories have different statistical properties and formats, they may be compressed using similar combinations of pre-processing, statistical coding, and parallel algorithms. Furthermore, some of the universal features of the developed compression techniques will make it possible to successfully apply them on other emerging genomic data formats. The long-term objectives of the proposed research program are two-fold. The first objective is to perform fundamental analytical studies of lossless and certain restricted forms of lossy compression and dimensionality reduction methods for genomic and functional genomic data, using information-theoretic techniques. The second objective is to develop a new suite of parallel algorithms for SAM, FASTQ and Wig track data compression. The developed algorithms are expected to include suitably combined, modified and extended classical compression methods (e.g., arithmetic, Huffman, and Lempel-Ziv coding), as well as novel solutions based on context-mixing and context-tree weighting with biological side-information. Immediate goals of the project include using CUDA, as well as classical parallel computing platforms, to implement current compression algorithms in order to reduce the latency of the compression and decompression process. Novel components of the parallel implementations will include extensive use of state-of-the-art hashing, indexing, and stringing methods. SAM, FASTQ and Wig data ¿les are ubiquitous in genomic research. Hence, a research program resulting in high-performance software suites for compression of these and other genomic information formats will enable management, transfer and access to massive data crucial for the operation of governmental and NIH sponsored projects such as ENCODE, TCGA, ClinVar, Genome 10K, the Million Cancer Genome Warehouse, and ADAM.

描述（由适用提供）：现代医疗保健研究和实践的最高优先事项之一是确定使人容易使人衰弱的基因组变化和标记，或者使它们对某些疗法和新兴治疗的反应更大。大量的DNA测序和功能性基因组数据在很大程度上可以实现及时的发现和知识挖掘，其大量数据有望体验到剧烈的重要性，因此对于发展有效，准确和低延迟数据的压缩和减压技术至关重要，允许快速交流，随机访问，可访问，可视化，多样性地形成多样化的多样性。使用专门的压缩方法在生物学数据中将确保NIH数据库的前所未有的增长及其效用，在医学研究中的新用途以及对实验结果的大规模传播。该提案的具体目的包括开发平行于任务的算法，用于基于参考的读取和整个基因组的无参考和无参考的压缩； b）质量得分的损失压缩； c）功能基因组数据的压缩。尽管这三个数据类别具有不同的统计属性和格式，但可以使用类似的预处理，统计编码和并行算法来压缩它们。此外，开发的压缩技术的某些通用特征将使成功将它们应用于其他新兴的基因组数据格式成为可能。拟议的研究计划的长期目标是两个方面。第一个目标是使用信息理论技术对无损和某些限制形式的损耗压缩和降低方法进行基本分析研究。第二个目标是为SAM，FASTQ和WIG跟踪数据压缩开发新的并行算法套件。预计开发的算法将包括适当的合并，修改和扩展的经典压缩方法（例如，算术，霍夫曼和LEMPEL-ZIV编码），以及基于上下文混合和具有生物侧面信息的上下文树的加权的新颖解决方案。该项目的直接目标包括使用CUDA以及经典的并行计算平台来实现当前的压缩算法，以减少压缩和减压过程的延迟。并行实现的新组件将包括广泛使用最先进的哈希，索引和串起方法。 SAM，FASTQ和假发数据„ LE在基因组研究中无处不在。因此，一项研究计划，导致高性能软件套件以压缩这些和其他基因组信息格式，将使管理，转移并访问大规模数据，对于政府和NIH赞助的项目的运行至关重要，例如编码，TCGA，TCGA，Clinvar，Genome 10K，基因组10K，Million Cancer Genome Warehouse和Adam。