Leveraging k-mer sketching statistics to enhance metagenomic methods and alignment algorithms

利用 k-mer 草图统计来增强宏基因组方法和比对算法

基本信息

批准号：
10675449
负责人：
Antonio Blanca Pimentel
金额：
$ 44.35万
依托单位：
PENNSYLVANIA STATE UNIVERSITY, THE
依托单位国家：
美国
项目类别：
财政年份：
2022
资助国家：
美国
起止时间：
2022-08-02 至 2027-05-31
项目状态：
未结题

项目摘要

Project Summary In the face of increasing data sizes, sketching techniques such as MinHash sketching and its winnowed version have been among the most effective in facilitating scalabile analysis. Frequently though, bioinformatic algorithms using these techniques do not account for the randomness inherent in both the sketching process and in the mutation processes that generate the data (e.g. sequencing errors or evolutionary mutations). This project directly addresses this limitation by laying the statistical foundations for how these sketching approaches interact with mutation processes and k-mer based techniques, resulting in new algorithms for important biomedical problems. Aim 1 derives, for the first time, confidence and prediction intervals for frequently utilized sketching-based bioinformatics quantities that until now existed only as point estimates.To do so, it relies on sophisticated techniques from probability theory. The mathematical foundations laid by Aim 1 will not only help us achieve the biological aims of this proposal, but will also serve as a basis for quantifying the performance of future sketching-based bioinformatics algorithms. Aim 2 will then use these results to develop the first metagenomic taxonomic profiling algorithm that accounts for the uncertainty present when predicting the presence and relative abundance of microorganisms in a sample. This will resolve a long-standing issue in this field by providing researchers an informed way to filter their noisy data without sacrificing sensitivity, thereby facilitating biomedical discoveries (e.g. novel CRISPR systems). In addition, this aim will result in the first scalable method to quickly estimate the fraction of a metagenomic sample that is not described by current reference databases, thus illuminating which datasets contain the highest quantity of novel genetic material and hence possibility for biological discovery (e.g. novel antibiotics). Aim 2 will be achieved using techniques from compressive sensing as well as probability theory. Aim 3 will both use and extend the results of Aim 1 to quantifiably improve one of the most fundamental tools in a computational biologist’s toolkit: sequence alignment. This will equip modern sequence aligners with much needed significance scores and confidence intervals, as well as allow for the automatic selection of parameter settings to achieve a desired precision or recall. Due to their ubiquity in biomedical research, even a small improvement in the accuracy and features of an aligner will have tremendous impact. Aim 3 will be achieved using techniques from probabilistic algorithms. Finally, the long-term objective of this proposal is to provide researchers a toolkit that enables the development of scalable k-mer-based sketching algorithms without sacrificing their ability to quantify statistical significance.

项目概要面对不断增加的数据量，诸如 MinHash 草图及其筛选之类的草图技术不过，该版本通常是促进可扩展分析的最有效版本之一。使用这些技术的算法没有考虑草图绘制过程中固有的随机性以及生成数据的突变过程（例如测序错误或进化突变）。该项目通过为这些草图如何绘制奠定统计基础，直接解决了这一限制方法与突变过程和基于 k 聚体的技术相互作用，从而产生新的算法目标 1 首次推导了重要的生物医学问题的置信度和预测区间。经常使用基于草图的生物信息学数量，到目前为止这些数量仅作为点估计存在。要做到这一点，它依赖于目标 1 奠定的数学基础的复杂技术。不仅有助于我们实现该提案的生物学目标，而且还将作为量化的基础未来基于草图的生物信息学算法的性能将使用这些结果。开发第一个宏基因组分类分析算法，该算法可以解释当预测样品中微生物的存在和相对丰度这将解决一个问题。通过为研究人员提供一种明智的方法来过滤噪声数据，而无需牺牲敏感性，从而促进生物医学发现（例如新型 CRISPR 系统）。目标将是第一个可扩展的方法来快速估计宏基因组样本中不存在的部分由当前参考数据库描述，从而阐明哪些数据集包含最高数量的新的遗传物质以及生物发现的可能性（例如新的抗生素）。目标 3 将使用压缩传感技术和概率论来实现。扩展目标 1 的结果，以量化地改进计算中最基本的工具之一生物学家的工具包：序列比对，这将为现代序列比对仪配备急需的功能。显着性分数和置信区间，以及允许自动选择参数设置由于它们在生物医学研究中的普遍存在，即使是很小的改进。对准器的精度和功能将对目标 3 的实现产生巨大影响。最后，该提案的长期目标是提供概率算法的技术。研究人员开发了一个工具包，可以开发可扩展的基于 k-mer 的草图算法，而无需牺牲他们量化统计显着性的能力。