III: Small: New algorithms for genome skimming and its applications

近年来，人为压力和其他自然原因造成了全球生态系统的严重破坏，包括生物多样性的丧失和外来动植物的入侵。一个特别的问题是，仅仅确定不同物种的种群数量是不够的；还必须确定一个物种内是否存在足够的遗传多样性来确保其生存。因此，有必要估计不同地区的遗传生物多样性，以决定哪里和哪些动植物最需要保护，并预测拟议的干预措施的结果。然而，目前用于计算生物多样性的算法，基于计算生物样本之间的遗传“距离”，计算量太大，速度太慢，无法大规模应用。该项目将通过开发计算生物多样性的新的、高效的算法来克服这个问题。因此，这项工作将提供必要的工具，以提高我们对生态系统的了解，并为管理动植物自然资源做出更好的决策。PIS取代了目前流行的分离和测序特定系统发育信息区的技术，提出了一种低通全基因组测序(基因组大纲)和无比对条形码的方法。为了实现这一方法，私人投资机构将开发算法和工具来识别给定文库中的所有基因组概要，将它们用于系统发育重建，并使用元条形码和基因组概要作为检查有机体种群的机制。拟议的活动将使人们能够以目前劳动力和基因组测序成本的一小部分来估计基因组生物多样性。该提案使用了许多创新和新颖的算法和统计技术，并首次系统研究了仅使用基因组的一小部分随机部分来计算基因组距离的可行性。该项目将通过提供一种简单、廉价的协议来测量生物多样性，比目前可以实现的更高的灵敏度，从而推动这一领域的发展。拟议的活动将允许以目前劳动力和基因组测序成本的一小部分来估计基因组生物多样性。该提案使用了许多创新和新颖的算法和统计技术，并首次系统研究了仅使用基因组的一小部分随机部分来计算基因组距离的可行性。如果成功，该项目将提供一种简单、廉价的协议，以比目前可以实现的更高的灵敏度测量生物多样性，从而推动这一领域的发展。研究人员在相关领域的先前研究有很强的历史，但在进化和系统发育重建以及计算种群基因组学方面具有互补的专业知识。它有三个目标：给出两个生物体的基因组概要，估计汉明距离并用它来搜索给定的文库；使用基因组概要进行系统发育重建；给出元条形码查询(生物体混合的基因组概要)，识别组成生物及其在样本中的相对丰度。这项裁决反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Anthropogenic pressure and other natural causes have resulted in severe disruption of the global ecosystems in recent years, including loss of biodiversity and invasion of non-native plants and animals. A particular problem is that it is not enough to simply determine the population of various species; it is also important to determine whether there exists enough genetic diversity within a species to ensure its survival. It is therefore necessary to estimate the genetic biodiversity of various areas in order to decide where and which plants and animals are in most need of protection, and to predict the outcome of proposed interventions. However, current algorithms for computing biodiversity, which are based on taking on computing the genetic "distance" between samples of organisms, are too computationally intensive and slow to be applied at large scale. This project will overcome the problem by developing new, highly efficient algorithms for computing biodiversity. As a result, this work will provide tools needed to improve our knowledge of ecosystems and make better decisions for managing plant and animal natural resources.In place of the currently popular technique of isolating and sequencing specific phylogenetically informative regions, the PIs propose a low-pass whole genome sequencing (genome skims) and alignment-free methods for barcoding. To enable this approach, the PIs will develop algorithms and tools to identify all genome-skims in a given library, use them for phylogenetic reconstruction and use meta-barcoding and genome-skims as a mechanism for examining populations of organisms. The proposed activities will allow the estimation of genomic bio-diversity for a fraction of the current costs of labor and genome sequencing. The proposal uses a number of innovative and novel algorithmic and statistical techniques and describes the first systematic study of the feasibility of computing the genomic distance using only a small, random fraction of the genome. The project will advance the field by providing a simple and inexpensive protocol for measuring biodiversity with higher sensitivity than is currently achievable.The proposed activities will allow the estimation of genomic bio-diversity for a fraction of the current costs of labor and genome sequencing. The proposal uses a number of innovative and novel algorithmic and statistical techniques and describes the first systematic study of the feasibility of computing the genomic distance using only a small, random fraction of the genome. If successful, the project will advance the field by providing a simple and inexpensive protocol for measuring biodiversity with higher sensitivity than is currently achievable. The investigators have a strong history of prior research in related fields, but have complementary expertise, in evolution and phylogenetic reconstruction and computational population genomics. There are three aims: given genome-skims of two organisms, estimate the hamming distance and use that to search a given library; use genome-skims for phylogenetic reconstruction; and given a meta-barcoding query (genome-skims of a mix of organisms), identify the constituent organisms and their relative abundance in the sample.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.