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

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.