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

职业：泛基因组数据建模、索引和查询的算法方面

基本信息

批准号：
2146003
负责人：
Sharma Thankachan
金额：
$ 59.53万
依托单位：
The University of Central Florida Board of Trustees
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-02-01 至 2023-02-28
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2146003&HistoricalAwards=false
关键词：
CAREER Algorithmic Aspects Pan genomic

项目摘要

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.

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

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Feasibility of flow decomposition with subpath constraints in linear time

线性时间内子路径约束流分解的可行性

DOI：
发表时间：
2022
期刊：
Leibniz International Proceedings in Informatics
影响因子：
0
作者：
Gibney, Daniel;Thankachan;Sharma V;Aluru, S.
通讯作者：
Aluru, S.

Co-linear Chaining with Overlaps and Gap Costs

DOI：
10.1007/978-3-031-04749-7_15
发表时间：
2022-01-01
期刊：
Research in Computational Molecular Biology: 26th Annual International Conference, RECOMB 2022, Proceedings. Lecture Notes in Computer Science, Lecture Notes in Bioinformatics (13278)
影响因子：
0
作者：
Jain, Chirag;Gibney, Daniel;Thankachan, Sharma V.
通讯作者：
Thankachan, Sharma V.

Quantum Time Complexity and Algorithms for Pattern Matching on Labeled Graphs

标记图上模式匹配的量子时间复杂度和算法

DOI：
发表时间：
2022
期刊：
String Processing and Information Retrieval - 29th International Symposium (SPIRE
影响因子：
0
作者：
Darbari, Parisa;Gibney, Daniel;Thankachan, Sharma V.
通讯作者：
Thankachan, Sharma V.

The Complexity of Approximate Pattern Matching on de Bruijn Graphs