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
• 项目状态: 未结题
• 来源: https://reporter.nih.gov/project-details/10675449
• 关键词: Address; Affect; Algorithms; Antibiotics; Area; Bioinformatics; Biological; Biomedical Research; Clustered Regularly Interspaced Short Palindromic Repeats; Communication; Communities; Computational Biology; Computational Technique; Confidence Intervals; Data; Data Set; Databases; Development; Dimensions; Endowment; Ensure; Foundations; Frequencies; Future; Generations; Genetic Materials; Goals; Mathematics; Measures; Metagenomics; Methods; Modernization; Molecular Evolution; Mutate; Mutation; Organism; Outcome; Output; Performance; Probability Theory; Process; Research Personnel; Sampling; Sequence Alignment; Sequence Read Archive; System; Taxonomy; Techniques; Testing; Time; Uncertainty; Variant; Work; cost; driving force; improved; innovation; insight; metagenome; microorganism; novel; statistics; theories; tool; Address; Affect; Algorithms; Antibiotics; Area; Bioinformatics; Biological; Biomedical Research; Clustered Regularly Interspaced Short Palindromic Repeats; Communication; Communities; Computational Biology; Computational Technique; Confidence Intervals; Data; Data Set; Databases; Development; Dimensions; Endowment; Ensure; Foundations; Frequencies; Future; Generations; Genetic Materials; Goals; Mathematics; Measures; Metagenomics; Methods; Modernization; Molecular Evolution; Mutate; Mutation; Organism; Outcome; Output; Performance; Probability Theory; Process; Research Personnel; Sampling; Sequence Alignment; Sequence Read Archive; System; Taxonomy; Techniques; Testing; Time; Uncertainty; Variant; Work; cost; driving force; improved; innovation; insight; metagenome; microorganism; novel; statistics; theories; tool

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素描及其wo 版本一直是支持Scalabile分析的最有效的版本之一。但是，经常是生物信息学 使用这些技术的算法不能说明两个草图过程中固有的随机性 在生成数据的突变过程中（例如测序误差或进化突变）。这 项目通过为这些素描奠定统计基础直接解决此限制 方法与突变过程和基于K-MER的技术相互作用，从而产生了新的算法 重要的生物医学问题。 AIM 1首次获得信心和预测间隔 经常利用基于草图的生物信息学数量，到目前为止仅作为点估计而存在。 这样做，它依赖于概率理论的复杂技术。 AIM 1奠定的数学基础 不仅将帮助我们实现该提案的生物学目标，而且还将作为量化的基础 未来基于草图的生物信息学算法的性能。 AIM 2然后将这些结果用于 开发第一个核能分类学分析算法，该算法解释了存在的不确定性 预测样品中微生物的存在和相对丰度。这将解决一个 在该领域的长期存在，通过为研究人员提供一种无知的噪音数据的知识方法 牺牲灵敏度，从而支持生物医学发现（例如新型CRISPR系统）。此外，这 AIM将导致第一种可扩展的方法快速估计不是宏基因组样品的分数 通过当前参考数据库描述，因此阐明了哪些数据集包含最高数量的数据集 新颖的遗传物质，因此可能是生物发现的可能性（例如，新型抗生素）。 AIM 2将是 AIM 3都将使用和 扩展AIM 1的结果以量化计算中最基本的工具之一 生物学家的工具包：序列对齐。这将配备现代序列对齐，并急需 显着性得分和置信区间，并允许自动选择参数设置 达到所需的精确或召回。由于它们在生物医学研究中的普遍性，即使是很小的改进 在准确性和特征中，对准器将产生巨大的影响。 AIM 3将使用 有问题算法的技术。最后，该提议的长期目标是提供 研究人员一种工具包，可以开发可扩展的基于K-MER的素描算法 牺牲他们量化统计意义的能力。