IIBR Informatics: An Efficient Pangenomics Graph Aligner

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

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.