Collaborative Research: EAGER: Solving the bait learning problem for large-scale DNA enrichment

微生物组是指生物样品中的所有微生物，并且与许多生物活动和表型有关。例如，“肠道微生物群”通常指的是人类消化系统内发现的细菌，它被认为是无数表型和疾病的原因，包括肥胖、阿尔茨海默病、自闭症谱系障碍和各种癌症。同样，土壤微生物组也被认为与植物的耐旱性、开花时间和杀虫剂抗性有关。全面研究生物样本中的微生物是具有挑战性的，因为据估计，95%至99%的微生物不能在自然环境之外生存，因此不能在实验室环境中分离。幸运的是，霰弹枪宏基因组学可以解决这一挑战，因为它能够将样本中所有微生物对应的DNA作为输入，并产生与它们对应的DNA串（称为“序列读取”）。然后进一步分析这些测序读数以识别和研究微生物。然而，科学家们经常对研究有限数量的微生物感兴趣，而不是所有的微生物。例如，在研究呼吸道拭子中的微生物时，可能只有与COVID-19对应的序列读数才是感兴趣的。Shotgun宏基因组学将为拭子上发现的所有DNA产生序列读数。幸运的是，有一些实验室方法能够将测序限制在只有一组选定的DNA序列上，这被称为DNA富集。DNA富集产生并将一组短的合成DNA片段（称为“诱饵”）应用于生物样本，然后仅与选定的DNA部分结合。然后将未结合的DNA冲洗掉，只留下结合的DNA进行测序。因此，这一过程的第一步是信息学问题，即确定将丰富一组给定的DNA序列的诱饵。使信息学问题具有挑战性的两件事是诱饵的数量应该是最小的，诱饵不仅可以精确地结合到单个DNA序列上，而且可以结合到许多允许不匹配的序列上。这个项目将设计我们将结合信息学，机器学习和数据集成技术来创建创建诱饵的实用方法。虽然现有的启发式方法证明了DNA富集的效用，但仍然没有任何方法能够有效地为大型DNA数据库做到这一点。因此，这个项目的重点之一就是创建可伸缩的方法。为了实现这一目标，我们将开发解决两个不同信息学问题的方法：(1)诱饵最小化问题，旨在确定最小尺寸的诱饵集，以丰富整个DNA序列；(2)DNA序列最大化问题，旨在选择最大的DNA序列子集，可以使用限制大小的诱饵集进行富集。在这里，我们将把生物过程的信息整合到问题的表述中，并使用最先进的信息方法来解决问题。该项目将产生若干创新，这些创新将对信息学、数据科学和其他科学学科产生重大影响。这项工作的更广泛影响将包括促进我们的微生物知识和为佛罗里达大学从事工程日的女孩创建课程。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The microbiome refers to all micro-organisms within a biological sample and has been linked to numerous biological activities and phenotypes. For example, the “gut microbiome”, which commonly refers to the bacteria found within the digestive system in humans, has been attributed to countless phenotypes and diseases, including obesity, Alzheimer’s disease, autism spectrum disorder, and types of cancer. Similarly, the soil microbiome has been attributed to drought tolerance, flowering time, and pesticide resistance in plants. Comprehensively studying the micro-organisms in a biological sample is challenging as that it is estimated that between 95% and 99% of them cannot live outside their natural environments, and therefore, cannot be isolated in a laboratory environment. Fortunately, shotgun metagenomics can address this challenge since it is able to take as input the DNA corresponding to all the micro-organisms within a sample and produce the DNA strings (which are called “sequence reads”) corresponding to them. These sequencer reads are then further analyzed to identify and study the micro-organisms. However, frequently scientists are interested in studying a limited number of micro-organisms rather than all of them. For example, in the case of studying the micro-organisms from a respiratory swab, it may be the case that only the sequence reads corresponding to COVID-19 are of interest. Shotgun metagenomics will produce sequence reads for all DNA found on the swab. Fortunately, there are laboratory methods capable of restricting the sequencing to only a selected set of DNA sequences, which is referred to as DNA enrichment. DNA enrichment creates and applies a set of short, synthetic DNA fragments (called “baits”) to a biological sample which then bind to only selected portions of the DNA. The unbound DNA is then rinsed away, leaving only the bound DNA that is then sequenced. Hence, the first step of this process is the informatics problem of identifying the baits that will enrich for a given set of DNA sequences. Two things that make the informatics problem challenging is that the number of baits should be of minimum size, and the baits do not only bind exactly to a single DNA sequence, but they can bind to many sequences with some allowable mismatches. This project will devise we will combine techniques in informatics, machine learning and data integration techniques to create practical methods for creating baits. While existing heuristics demonstrated the utility of DNA enrichment, there still does not exist any methods that are able to do this efficiently for large DNA databases. Hence, one of the focuses of this project is to create scalable methods. To accomplish this, we will develop methods for solving two different informatics problems: (1) the Bait Minimization problem that aims to identify the set of baits of minimal size that enrich for the entire set of DNA sequences, and (2) the DNA Sequence Maximization problem which aims to select the largest subset of DNA sequences that can be enriched by using a bait set of restricted size. Here, we will integrate the information of the biological process into the problem formulations and solve the problems using state-of-the-art informatic approaches. This project will result in several innovations that will have major impact in informatics, data science and other scientific disciplines. The broader impact of this work will encompass the furtherance of our knowledge micro-organisms and the creation of curriculum for Girls Engaged in Engineering Days at the University of Florida.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.