AF: Small: Algorithmic Techniques for High-throughput Analysis of Long Reads

AF：小：长读长高通量分析的算法技术

基本信息

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

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816027&HistoricalAwards=false
关键词：
AF Small Algorithmic Techniques throughput

项目摘要

The field of DNA sequencing has rapidly evolved from Sanger sequencing (700-1000 base pairs, or bp, in length) to massively parallel high-throughput sequencing of short reads (100-200 bp) to the more recent advances in generating long ( 5,000 bp) and ultra-long ( 50,000 bp) reads. There is currently an urgent need to develop efficient algorithms for analyzing long-read datasets in the context of the myriad biological applications they enable. Long read technologies sustain high error rates but with more attractive error distribution characteristics that often permit probabilistic guarantees on the quality of results. This project will result in fundamental research advances in developing bioinformatics algorithms for long-read sequencing, along with distributable open-source software products to facilitate their immediate adoption by the life sciences community. The award will also support interdisciplinary training, and undergraduate participation in research.The project seeks to advance mapping, assembly, and biological applications of long-read sequencing through the design of provably efficient algorithms, formal characterization of the quality of results, development of methods that scale to larger datasets, and methods that are robust to changes brought about by continued developments in long read sequencing. Problems addressed include (i) split-read mapping of ultra-long reads to a reference genome, (ii) development of data structures based on bloom filters to achieve space optimization and perfect statistical sensitivity, (iii) algorithms for mapping long reads to a collection of reference genomes represented by compact graph-based structures, (iv) algorithms for partitioning long reads to facilitate identification of haplotypes in diploid assemblies, and (v) long-read inspired alignment free algorithms for genome-to-genome comparison, as well as important biological applications enabled by these. The research will emphasize utilization of real datasets, relevance to practically encountered problems and applications, and independent validation by collaborators and other experts.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.

DNA 测序领域已从桑格测序（长度为 700-1000 个碱基对或 bp）迅速发展到短读段（100-200 bp）的大规模并行高通量测序，再到生成长读段（5,000 个碱基对）的最新进展。 bp）和超长（50,000 bp）读取。目前迫切需要开发有效的算法来在其支持的无数生物应用的背景下分析长读数据集。长读技术维持高错误率，但具有更有吸引力的错误分布特征，通常可以对结果质量进行概率保证。该项目将在开发用于长读长测序的生物信息学算法方面取得基础研究进展，并提供可分发的开源软件产品，以促进其立即被生命科学界采用。该奖项还将支持跨学科培训和本科生参与研究。该项目旨在通过设计可证明有效的算法、结果质量的形式表征、方法的开发来推进长读长测序的绘图、组装和生物应用可以扩展到更大的数据集，以及对长读测序的持续发展所带来的变化具有鲁棒性的方法。解决的问题包括（i）超长读段到参考基因组的分割读段映射，（ii）开发基于布隆过滤器的数据结构以实现空间优化和完美的统计灵敏度，（iii）将长读段映射到参考基因组的算法由紧凑的基于图形的结构表示的参考基因组的集合，（iv）用于分割长读的算法，以促进二倍体组装中单倍型的识别，以及（v）用于基因组间比较的长读启发的免对齐算法作为由这些实现的重要生物应用。该研究将强调真实数据集的利用、与实际遇到的问题和应用的相关性，以及合作者和其他专家的独立验证。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查进行评估，被认为值得支持标准。

项目成果

期刊论文数量（14）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Accelerating Sequence Alignment to Graphs

DOI：
10.1109/ipdps.2019.00055
发表时间：
2019-01-01
期刊：
2019 IEEE 33RD INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2019)
影响因子：
0
作者：
Jain, Chirag;Misra, Sanchit;Aluru, Srinivas
通讯作者：
Aluru, Srinivas

A fast adaptive algorithm for computing whole-genome homology maps

DOI：
10.1093/bioinformatics/bty597
发表时间：
2018-09-01
期刊：
BIOINFORMATICS
影响因子：
5.8
作者：
Jain, Chirag;Koren, Sergey;Aluru, Srinivas
通讯作者：
Aluru, Srinivas

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 Sequence-to-Graph Alignment

DOI：
10.1089/cmb.2019.0066
发表时间：
2020-01-03
期刊：
JOURNAL OF COMPUTATIONAL BIOLOGY
影响因子：
1.7
作者：
Jain, Chirag;Zhang, Haowen;Aluru, Srinivas
通讯作者：
Aluru, Srinivas

Haplotype-aware variant selection for genome graphs

DOI：
10.1145/3535508.3545556
发表时间：
2022-08
期刊：
Proceedings of the 13th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics
影响因子：
0
作者：
Neda Tavakoli;Daniel Gibney;S. Aluru
通讯作者：
Neda Tavakoli;Daniel Gibney;S. Aluru