IIBR Informatics: An Efficient Pangenomics Graph Aligner

在过去的十年里，人们一直在努力对特定物种的大量个体的DNA进行测序和比较，结果不仅仅是一个参考基因组，而是一个特定物种的基因组群体。“1000个基因组计划”、“100K基因组计划”、“1001个拟南芥基因组计划”、“水稻基因组注释计划”、“鸟类10000个基因组（B10K）计划”等大量的公共数据已经公开。称为短读比对器的关键软件，将新测序的DNA片段与一个（或多个）参考基因组比对，以确定物种内的遗传变异。这种遗传变异的下游分析发现了复杂疾病和表型之间的因果关系。由于纯粹的计算限制，现有的短读比对器无法与大量参考基因组比对。因此，使用少量的基因组进行对齐可以减少记忆和时间限制。不幸的是，尽管同一物种的个体之间存在很大比例的遗传相似性，但差异也很重要，仅与特定物种的少数基因组对齐可能导致某些DNA片段不对齐或对齐不良。这反过来又使得在新测序的DNA片段和参考基因组之间寻找遗传变异更具挑战性。克服这一挑战的一种方法是开发用于短读对齐的新算法和数据结构，以减少计算资源。该项目通过开发基因组种群的新表示，并创建构建、存储和更新所需的算法和数据结构，实现了这一愿景。因此，整合到这个项目的目标是推进生物科学和模式物种的知识，以及思想，并进一步发展一个支持第一代大学毕业生的推广计划。这项工作的一个直接成果将是通过马琴佛罗里达机会学者项目为得不到充分服务的学生提供研究机会，这是一个旨在培养第一代大学学者的组织。短读比对者首先从一个或多个参考基因组建立一个索引，然后使用它来查找和扩展序列读取和参考基因组之间的匹配子序列。使用这些读取比对器索引数千个基因组的瓶颈是构建和存储索引所需的空间和时间。为了解决使用单一参考基因组的缺点，基于图的泛基因组比对者的概念已经被引入并在社区中广泛讨论。虽然这些方法已被证明比标准的基于序列的比对器的准确性有所提高，但它们的使用还没有得到充分的探索。阻碍实现泛基因组图对齐的挑战是可扩展性。该项目的目标是开发算法，允许从大量人群收集的数据集构建泛基因组参考。为了实现这一目标，将创建和实现新的方法来构建、压缩和更新包含种群中发现的变化的图。因此，这项工作将需要进一步的进步，其影响将超出所述的应用程序。更具体地说，我们不知道如何合并r-索引，如何使用亚线性空间表示引用的图模型，或者如何使用r-索引表示图。该项目将解决这些开放性问题，并更广泛地将两个研究领域联系起来：简洁数据结构和泛基因组学。接下来，该项目将最小化压缩和可变性之间的概念差距。由于高度压缩的数据结构无法在不重建的情况下进行更改，因此研究界一直在努力平衡压缩和可变性之间的关系。当试图将这些结构应用于定期更新新数据的生物数据集时，这会造成过度的限制。该项目将通过开发压缩的可变数据结构来实现我们的泛基因组学索引，从而在该领域取得重大进展。项目网站：www.christinaboucher.com/pangenomics-iibrThis该奖项反映了美国国家科学基金会的法定使命，并通过基金会的知识价值和更广泛的影响审查标准进行评估，认为值得支持。

In the past decade, there has been an effort to sequence and compare the DNA of a large number of individuals of a given species, resulting in not just a single reference genome but a population of genomes of a given species. Enormous public data now are available including the 1,000 Genome Project, the 100K Genome Project, the 1001 Arabidopsis Genomes project, the Rice Genome Annotation Project, and the Bird 10,000 Genomes (B10K) Project. Key software, called short read aligners, align newly sequenced DNA fragments to one (or more) reference genome(s) in order to identify genetic variation within the species. The downstream analysis of this genetic variation finds causal relationships between complex diseases and phenotypes. Existing short read aligners are unable to align to a large number of reference genome(s), due purely to computational constraints. Hence, using a small number of genome(s) to align to reduces the memory and time constraints. Unfortunately, although there is a large percentage genetic similarity between individuals of the same species, the differences are also important and aligning to only a small number of genomes of a given species can lead to some of the DNA fragments not aligning or aligning poorly. This, in turn, makes finding genetic variation between the newly sequenced DNA fragments and the reference genome(s) more challenging. One manner to overcome this challenge is to develop new algorithms and data structures for short read alignment that reduce the computational resources. This project realizes this vision by developing a novel representation of a population of genomes, and creating the algorithms and data structures needed to build, store and update it. Thus, integrated into this project is the goal of advancing biological science and knowledge of model species, and the ideas, and furthering the development of an outreach program that supports first-generation university graduates. An immediate outcome of the work will be research opportunities to under-served students through the Machen Florida Opportunity Scholars program, an organization that aims to foster the success of first-generation university scholars. Short read aligners first build an index from one or more reference genome(s) and subsequently use it to find and extend matched subsequences between sequence reads and the reference(s). The bottleneck of using these read aligners to index thousands of genomes is the space and time needed for construct and store the index. To address the shortcomings associated with using a single reference genome, the concept of graph-based pangenomics aligners has been introduced and widely discussed in the community. Although such methods have been shown to improve on the accuracy over standard sequence-based aligners, their use has not been fully explored. The challenge that prevents the realization a pangenomics graph alignment is that of scalability. The goal of the project is to the developing algorithms that allow for the construction of a pangenomic reference from datasets gathered from large populations. In order to achieve this goal, novel means to build, compress, and update a graph that encapsulates the variation found in the population will be created and implemented. Thus, this work will require further advancements that have impact beyond the stated application. More specifically, it is unknown how to merge the r-index, represent a graph-model of references using sub-linear space, or represent the graph using the r-index. This project will address these open problems, and more broadly, connect two areas of research: succinct data structures and pangenomics. Next, the project will minimize the conceptual gap between compression and mutability. The research community has struggled with the balance between compression and mutability since highly compressed data structures are not able to be altered without reconstruction. This poses unduly constraints when trying to apply these structures to biological datasets that routinely get updated with new data. This project will make significant developments in this area by developing compressed data structures that are mutable for our realization of our pangenomics index. Project website: www.christinaboucher.com/pangenomics-iibrThis 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.