CAREER: Algorithmic Aspects of Pan-genomic Data Modeling, Indexing and Querying

该奖项的全部或部分资金来自《2021年美国救援计划法案》(公法117-2)。该项目旨在解决以下问题：如何简洁地(并以具有生物学意义的方式)对泛基因组集合的组合信息进行建模，从而使对该表示的基因组分析既易于计算又准确？这是目前生物信息学研究的热点之一。泛基因组集合可以表示为高分多序列比对(MSA)数据、索引文本数据或更流行的基于图形的表示(泛基因组图)。这些模型的基本目标之一是高效地支持读映射查询。为此，这项研究将产生一类新的字符串/图形算法，用于分析与关键应用密切相关的泛基因组数据，这些应用可能对数据驱动的生物信息学的理论和实践产生持久影响。主要研究结果将通过同行评议的会议、期刊和研讨会教程进行传播。几篇博士和硕士论文也将从这项研究中衍生出来。调查员致力于确保妇女、来自代表性不足的少数群体的学生和本科生参与这项研究。该项目的新方面包括由不同的图形参数参数化的新的图形算法，以及索引(高度相似，可能是动态的)文本和图形的技术。串到图匹配的参数化和相关问题可能会为受限图类带来几个有效的、实用的解决方案。这些问题是由紧迫的应用程序很好地推动的，包括读取映射和(基于参考的)基因组组装。此外，一些基本的计算生物学问题，如多序列比对，将在泛基因组学的背景下重新讨论，以获得更快的近似和更好的启发式方法。另一个方向是更深入地研究流行的启发式算法，如共线链法。这里的目标是提供坚实的数学推理，解释为什么这些方法在实践中效果很好。这些研究目标与研究人员在字符串算法方面的背景以及将基础研究转化为实践的长期职业目标保持一致。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).This project aims to address the following question: How to model the combined information of a pan-genome collection succinctly (and in a biologically meaningful way) such that the genomic analysis on that representation is both easy-to-compute and accurate? This is one of the active lines of bioinformatics research currently. Pan-genome collections may be represented as high-scoring Multiple Sequence Alignment (MSA) data, indexed text data, or the more popular graph-based representations (pan-genome graphs). One of the fundamental objectives of these models is to support read mapping queries efficiently. To that end, this research will lead to a new class of string/graph algorithms for the analysis of pan-genomic data that are closely tied to critical applications that have the potential to make a lasting impact on the theory and practice of data-driven bioinformatics. The key findings will be disseminated through peer-reviewed conferences, journals, and workshop tutorials. Several Ph.D. and Master's theses will also evolve from this research. The investigator is committed to ensuring the participation of women, students from underrepresented minority groups, and undergraduates in this research. The novel aspects of this project include new graph algorithms parameterized by different graph parameters and techniques for indexing (highly similar, possibly dynamic) texts and graphs. The parameterization of the string-to-graph matching and related problems might lead to several efficient, practical solutions for restricted graph classes. Such problems are well motivated by pressing applications, including read-mapping and (reference-based) genome assembly. Additionally, some fundamental computational biology problems, like the Multiple Sequence Alignment, will be revisited in the context of pan-genomics for faster approximations and better heuristics. A deeper investigation on popular heuristics like co-linear chaining is another direction. The goal here is to provide solid mathematical reasoning on why such methods work well in practice. These research objectives align with the investigator's background in string algorithms and his long-term career goals of transforming foundational research into practice.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.