Genomic Compression: From Information Theory to Parallel Algorithms

 描述(由申请人提供)：现代医疗研究和实践的最高优先事项之一是识别使个人易患衰弱疾病的基因组变化和标记，或使他们对某些疗法和新兴治疗更敏感。这一医学研究领域的及时发现和知识挖掘在很大程度上得益于大量的DNA测序和功能基因组数据，其数量预计将在不久的将来经历急剧增长。因此，开发高效、准确和低延迟的数据压缩和解压缩技术至关重要，这些技术将允许对不同格式的基因组信息进行快速交换、传播、随机访问、可视化和搜索。对生物数据使用专门的压缩方法将确保NIH数据库及其效用的前所未有的增长，确保医学研究中众包计算的新用途，以及实验结果的大规模传播。该提案的具体目标包括开发并行的、面向任务的算法，用于基于参考和无参考的读数和整个基因组的压缩；b)质量分数的有损压缩；以及c)功能基因组数据的压缩。尽管这三个数据类别具有不同的统计属性和格式，但可以使用类似的预处理、统计编码和并行算法的组合来压缩它们。此外，已开发的压缩技术的一些通用特征将使其有可能成功地应用于其他新兴的基因组数据格式。拟议的研究计划的长期目标有两个。第一个目标是利用信息论技术对基因组和功能基因组数据的无损和某些受限形式的有损压缩和降维方法进行基本的分析研究。第二个目标是开发一套新的并行算法，用于SAM、FASTQ和WIG航迹数据压缩。开发的算法预计将包括适当组合、修改和扩展的经典压缩方法(例如，算术、哈夫曼和Lempel-Ziv编码)，以及基于上下文混合和具有生物边信息的上下文树权重的新颖解决方案。该项目的近期目标包括使用CUDA以及经典的并行计算平台来实施当前的压缩算法，以减少压缩和解压缩过程的延迟。并行实现的新组件将包括广泛使用最先进的散列、索引和串方法。SAM、FASTQ和WIG数据在基因组研究中普遍存在。因此，研究计划将产生用于压缩这些和其他基因组信息格式的高性能软件套件，从而能够管理、传输和访问对政府和NIH赞助的项目(如ENCODE、TCGA、ClinVar、Genome 10K、百万癌症基因组仓库和ADAM)的运行至关重要的大量数据。

 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.