AF: Medium: Collaborative Research: Sequential and Parallel Algorithms for Approximate Sequence Matching with Applications to Computational Biology

AF：媒介：协作研究：近似序列匹配的顺序和并行算法及其在计算生物学中的应用

基本信息

批准号：
1704552
负责人：
Srinivas Aluru
金额：
$ 52.5万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-07-01 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1704552&HistoricalAwards=false
关键词：
AF Medium Collaborative Research Sequential

项目摘要

Sequence matching problems are central to the field of genomics, both in analyzing naturally occurring sequences such as genomes and in analyzing data from sequencing instruments. Often, methods that can accommodate a small number of differences within the matching regions suffice in practice. Such methods, described as alignment-free or approximate sequence matching methods, have typically relied on heuristics. This project work is advancing the field by creating a mathematical framework and solving multiple approximate sequence matching problems with provably efficient run-time guarantees. Project work is also supporting the development of practical heuristics inspired and supported by the mathematical framework, development of parallel methods for solving large-scale problems on high performance parallel computers, and studying the impact of these methods on important applications. Project results are made available through open source software for use by practitioners. Results from this research will be incorporated into courses taught by the PIs, and disseminated more broadly through book chapters and tutorials and accompanying slides. The project will support research scientist and Ph.D. students in interdisciplinary training for launching them into productive careers focused on important problems of current relevance. Undergraduate participation is planned through course projects.Project work builds upon recent progress in alignment-free genome comparison methods, and exploits the controlled error characteristics of data generated by high-throughput sequencers, and the many bioinformatics applications enabled by them. Project objectives include developing a robust algorithmic framework for designing newer alignment-free methods based on approximate substring composition, and developing sequential and parallel algorithms for pairwise approximate sequence matching among large sequence data sets. The goal is to develop algorithms that are asymptotically superior to quadratic alignment-based approaches, and achieve good practical performance either directly or through further development of practical heuristic that rely on the underlying theory. The developed techniques will be further investigated in the context of important applications such as read error correction, genome mapping, and assembly. Though conducted in the context of computational biology, some of the methods are potentially applicable to other areas such as text processing and information retrieval. Broader research community will be impacted through release of software modules and project work in important application areas.

序列匹配问题是基因组学领域的核心，既在分析天然发生的序列（例如基因组）和分析测序仪器的数据中。通常，在实践中，可以适应匹配区域内少数差异的方法。这种方法（被描述为无对齐或近似序列匹配方法）通常依赖于启发式方法。这项项目工作正在通过创建数学框架并解决多个近似序列匹配问题和可证明有效的运行时保证，从而推进了该领域。项目工作还支持受到数学框架的启发和支持的实践启发式方法的发展，开发用于解决高性能并行计算机上的大规模问题的平行方法以及研究这些方法对重要应用的影响。项目结果可通过开源软件提供，供从业人员使用。这项研究的结果将纳入PIS教授的课程中，并通过书籍章节和教程以及随附的幻灯片进行更广泛的传播。该项目将支持研究科学家和博士学位。接受跨学科培训的学生将他们启动到生产力职业，重点是当前相关性的重要问题。本科参与是通过课程项目计划的。项目的工作基于无对齐基因组比较方法的最新进展，并利用了由高通量测序仪产生的数据的受控错误特征，以及许多由它们启用的生物信息信息应用程序。项目目标包括开发一个可靠的算法框架，用于设计基于近似基因组成组成的新的无对齐方法，并为大序列数据集中的成对近似序列匹配开发顺序和并行算法。目的是开发渐近地优于基于二次对准的方法的算法，并直接或通过进一步发展依赖基本理论的实用启发式式实践启发式，实现良好的实践绩效。将在重要应用的背景下进一步研究开发的技术，例如读取误差校正，基因组映射和组装。尽管在计算生物学的背景下进行，但其中一些方法可能适用于其他领域，例如文本处理和信息检索。更广泛的研究社区将通过发布软件模块和在重要应用领域的项目工作来影响更广泛的研究社区。

项目成果

期刊论文数量（20）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Complexity of Approximate Pattern Matching on de Bruijn Graphs

DOI：
10.1007/978-3-031-04749-7_16
发表时间：
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
作者：
Gibney, Daniel;Thankachan, Sharma V.;Aluru, Srinivas
通讯作者：
Aluru, Srinivas

On the Complexity of BWT-runs Minimization via Alphabet Reordering

DOI：
10.4230/lipics.esa.2020.15
发表时间：
2019-11
期刊：
影响因子：
0
作者：
Jason Bentley;Daniel Gibney;Sharma V. Thankachan
通讯作者：
Jason Bentley;Daniel Gibney;Sharma V. Thankachan

The Heaviest Induced Ancestors Problem Revisited

重温最重的诱发祖先问题

DOI：
10.4230/lipics.cpm.2018.20
发表时间：
2018
期刊：
{CPM} 2018
影响因子：
0
作者：
Abedin, P.;Hooshmand, S.;Ganguly, A.;Thankachan, S.V.
通讯作者：
Thankachan, S.V.

A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time

多对数时间内范围LCP查询的线性空间数据结构

DOI：
10.1007/978-3-319-94776
发表时间：
2018
期刊：
International Computing and Combinatorics Conference
影响因子：
0
作者：
Abedin, P.;Ganguly, A.;Hon, W. K.;Nekrich, Y.;Sadakane, K.;Shah, R.;Thankachan, S. V.
通讯作者：
Thankachan, S. V.

Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis