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

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

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.