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.

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

项目成果

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

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

• DOI: 10.1007/978-3-319-94776-1_51
• 发表时间: 2018-01
• 期刊: International Computing and Combinatorics Conference
• 作者: Abedin, Paniz;Ganguly, Arnab and;Nekrich, Yakov;Sadakane, Kunihiko;Shah, Rahul;Thankachan, Sharma V
• 通讯作者: Thankachan, Sharma V

On the Complexity of BWT-Runs Minimization via Alphabet Reordering

通过字母重新排序来最小化 BWT 运行的复杂性

• DOI: 10.4230/lipics.esa.2020.15
• 发表时间: 2020-01
• 期刊: ESA 2020
• 作者: W. Bentley, Jason;Daniel, Gibney;V. Thankachan, Sharma
• 通讯作者: V. Thankachan, Sharma

On the Hardness and Inapproximability of Recognizing Wheeler Graphs

论惠勒图识别的困难性和不可逼近性

• DOI: 10.4230/lipics.esa.2019.51
• 发表时间: 2019-01
• 期刊: 27th Annual European Symposium on Algorithms (ESA
• 作者: Gibney, Daniel;Thankachan, Sharma V.
• 通讯作者: Thankachan, Sharma V.

Faster Computation of Genome Mappability with one Mismatch

更快地计算一种不匹配的基因组可图性

• DOI: 10.1109/iccabs.2018.8541897
• 发表时间: 2018-10
• 期刊: 2018 IEEE 8th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS
• 作者: Hooshmand, Sahar;Abedin, Paniz;Gibney, Daniel;Aluru, Srinivas;Thankachan, Sharma V.
• 通讯作者: Thankachan, Sharma V.

An Ultra-Fast and Parallelizable Algorithm for Finding $k$-Mismatch Shortest Unique Substrings

一种用于查找$k$-不匹配最短唯一子串的超快速且可并行的算法

• DOI: 10.1109/tcbb.2020.2968531
• 发表时间: 2021-01
• 期刊: IEEE/ACM Transactions on Computational Biology and Bioinformatics
• 作者: Allen, Daniel R.;Thankachan, Sharma V.;Xu, Bojian
• 通讯作者: Xu, Bojian