ABI Innovation: Fast Algorithms and Tools for Single-Molecule Sequencing Reads

ABI 创新：单分子测序读取的快速算法和工具

• 批准号: 1759856
• 负责人: Feng Luo
• 金额: $ 89.89万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1759856&HistoricalAwards=false
• 关键词: ABI; Innovation; Fast; Algorithms; Tools

Genomics, which studies the structure, function and evolution of DNA and RNA sequences of organisms, now has significant impact on every aspect of life sciences, such as agriculture, environment, medicine and biology. The rapid advance of sequencing technologies is one of the most important reasons behind the evolution of genomics research. Next-generation sequencing (NGS), which has significantly lowered the cost for sequencing DNA and RNA, has remarkably increased the application of genomics in every aspect of life sciences. More recently, we have seen the emergence of third-generation long-read Single-Molecule Sequencing (SMS) technologies from companies like PacBio and Oxford Nanopore. Unlike short (100-500 bp) NGS reads, the SMS reads have the distinguishing characteristics of long read length (2,000-50,000 bp), unbiased sequencing, a different type and frequency of random errors, and detection of additional modifications to the DNA bases, called epigenetic modification information. These characteristics make SMS reads useful in many genomics investigations, such as de novo genome assemblies (where there is no guiding framework available), methylation detection, gene isoform detection (small sequence changes that identify different alleles of a gene) and structural variation detection (large rearrangements in the organization of the genes). This project will develop efficient algorithms and tools to improve the effectiveness, usefulness and applicability domain of SMS reads. The successful completion of this project will significantly transform genomics research. The new tools will enable biologists to perform genomics studies, such as de novo assembly and global methylation detection, on large genomes using SMS. The tools will significantly lower the cost of analysis and increase the utility of the data for biologists so that they can advance their research. All algorithms, tools and demonstrations resulting from this project will be made publicly available to educators, researchers and students through our project website and GitHub. This project will be useful to train computer science students, including women and minority students, on bioinformatics problems and algorithm design.Although SMS is now widely used in the genomics studies of small bacterial and archaeal genomes, the computational cost and high data volume currently prevent its use in the study of mid-to-large size genomes. The overall goal of this project is to develop fast algorithms and tools to investigate remedies for problems in three SMS applications: pairwise and reference alignment, error correction, and base modification detection. First, we will develop a tool for pairwise and reference genome alignments of SMS reads at least 5X faster than those currently available by designing and integrating fast k-mer matching, linear positional chaining and SIMD (Single-Instruction-Multiple-Data) based banded Smith-Waterman-Gotoh algorithms. Then, we will develop a linear space and linear time algorithm for reads alignment graph (RAG) based method, as well as a multiple reads alignment graph (MRAG) based method to efficiently correct processing for Oxford Nanopore technology data output. Furthermore, we will design an optimized and parallelized Spark pipeline for base modification detection using SMS reads, as well as a two-step classification method for effectively detecting base modification in SMS reads using neural networks. This research will substantially advance the state-of-the-art algorithms and tools for SMS reads. Project pages will be linked from https://people.cs.clemson.edu/~luofeng/research.html .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和RNA序列的结构、功能和进化，现已对农业、环境、医学和生物学等生命科学的方方面面产生重大影响。测序技术的快速发展是基因组研究演变的最重要原因之一。下一代测序(NGS)显著降低了DNA和RNA测序的成本，显著增加了基因组学在生命科学各个方面的应用。最近，我们看到了PacBio和牛津纳米孔等公司的第三代长读单分子测序(SMS)技术的出现。与短(100-500bp)NGS读取不同，SMS读取具有长读取长度(2000-5000bp)、无偏测序、不同类型和频率的随机错误以及检测到对DNA碱基的额外修饰(称为表观遗传修饰信息)的显著特征。这些特征使得SMS读数在许多基因组研究中是有用的，例如从头开始基因组组装(其中没有可用的指导框架)、甲基化检测、基因异构体检测(识别基因不同等位基因的小序列变化)和结构变异检测(基因组织中的大重排)。该项目将开发高效的算法和工具，以提高短信阅读的有效性、有用性和适用性领域。该项目的成功完成将极大地改变基因组学研究。这些新工具将使生物学家能够使用短信对大基因组进行基因组学研究，如从头组装和全球甲基化检测。这些工具将显著降低分析成本，并增加生物学家数据的实用性，以便他们能够推进他们的研究。这个项目产生的所有算法、工具和演示将通过我们的项目网站和GitHub向教育工作者、研究人员和学生公开。这个项目将有助于培训计算机科学专业的学生，包括女性和少数民族学生，关于生物信息学问题和算法设计的培训。尽管目前短消息系统已广泛应用于小细菌和古菌基因组的基因组研究，但其计算成本和高数据量目前阻碍了其在中大型基因组研究中的应用。这个项目的总体目标是开发快速算法和工具，以调查针对三个短信应用程序中的问题的补救措施：成对和参考比对、纠错和碱基修改检测。首先，我们将开发一个工具，通过设计和集成快速k-mer匹配、线性位置链和基于SIMD(单指令-多数据)的带式Smith-Waterman-Gotoh算法，使SMS读取的成对和参考基因组比对的速度至少比目前可用的快5倍。然后，我们将开发一种基于线性空间和线性时间算法的读数比对图(RAG)方法，以及一种基于多读数比对图(MRAG)的方法，以有效地纠正对牛津纳米孔技术数据输出的处理。此外，我们还将设计一种优化的并行化Spark流水线来检测短消息读取中的碱基修改，以及使用神经网络来有效地检测短消息读取中的碱基修改的两步分类方法。这项研究将极大地推进用于短信阅读的最先进的算法和工具。项目页面将从https://people.cs.clemson.edu/~luofeng/research.html链接。该奖项反映了国家科学基金会的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

NeuralPolish: a novel Nanopore polishing method based on alignment matrix construction and orthogonal Bi-GRU Networks

• DOI: 10.1093/bioinformatics/btab354
• 发表时间: 2021-05-11
• 期刊: BIOINFORMATICS
• 影响因子: 5.8
• 作者: Huang, Neng;Nie, Fan;Wang, Jianxin
• 通讯作者: Wang, Jianxin

Self-stabilizing algorithm for two disjoint minimal dominating sets

• DOI: 10.1016/j.ipl.2019.03.007
• 发表时间: 2019-07
• 期刊: Inf. Process. Lett.
• 作者: P. Srimani;J. Wang

Self-Stabilizing Master-Slave Token Circulation in Unoriented Cactus Graphs

无向仙人掌图中自稳定主从代币流通

• DOI: 10.1109/wi.2018.0-109
• 发表时间: 2018
• 期刊: 2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI
• 作者: Srimani, Pradip;Wang, James;Ding, Yihua
• 通讯作者: Ding, Yihua

BlockPolish: accurate polishing of long-read assembly via block divide-and-conquer

• DOI: 10.1093/bib/bbab405
• 发表时间: 2021-10
• 期刊: Briefings in bioinformatics
• 影响因子: 9.5
• 作者: Neng Huang;Fan Nie;Peng Ni;Xin Gao;F. Luo;Jianxin Wang

DeepSignal: detecting DNA methylation state from Nanopore sequencing reads using deep-learning

• DOI: 10.1093/bioinformatics/btz276
• 发表时间: 2019-11-15
• 期刊: BIOINFORMATICS
• 影响因子: 5.8
• 作者: Ni, Peng;Huang, Neng;Wang, Jianxin
• 通讯作者: Wang, Jianxin