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

基因组学研究生物体DNA和RNA序列的结构、功能和进化，现在对农业、环境、医学和生物学等生命科学的各个方面都产生了重大影响。测序技术的快速发展是基因组学研究发展的重要原因之一。新一代测序技术（NGS）大大降低了DNA和RNA测序的成本，极大地促进了基因组学在生命科学各个方面的应用。最近，我们看到PacBio和Oxford Nanopore等公司推出了第三代长读单分子测序（SMS）技术。与短序列（100-500 bp） NGS不同，短序列具有较长的序列长度（2000 -50,000 bp）、无偏测序、不同类型和频率的随机错误以及检测DNA碱基的附加修饰（称为表观遗传修饰信息）等显著特征。这些特征使得SMS读取在许多基因组学研究中非常有用，例如从头基因组组装（没有可用的指导框架）、甲基化检测、基因异构体检测（识别基因不同等位基因的小序列变化）和结构变异检测（基因组织中的大重排）。本项目将开发高效的算法和工具，以提高短信读取的有效性、有用性和适用性。该项目的成功完成将极大地改变基因组学研究。这些新工具将使生物学家能够使用SMS对大型基因组进行基因组学研究，例如从头组装和全局甲基化检测。这些工具将大大降低分析成本，增加生物学家的数据效用，使他们能够推进他们的研究。该项目产生的所有算法、工具和演示将通过我们的项目网站和GitHub公开提供给教育工作者、研究人员和学生。该项目将有助于培养计算机科学专业的学生，包括女性和少数族裔学生，了解生物信息学问题和算法设计。虽然SMS现已广泛用于小型细菌和古细菌基因组的基因组学研究，但计算成本和高数据量目前阻碍了其在中大型基因组研究中的应用。该项目的总体目标是开发快速算法和工具，以调查三个SMS应用程序中的问题补救措施：配对和参考校准、错误纠正和碱基修改检测。首先，我们将通过设计和集成快速k-mer匹配、线性位置链和基于单指令多数据（single - instruction -多数据）的带状Smith-Waterman-Gotoh算法，开发一种比现有工具快至少5倍的SMS基因组配对和参考基因组比对工具。然后，我们将开发一种基于线性空间和线性时间的读取比对图（RAG）方法，以及一种基于多读取比对图（MRAG）的方法，对Oxford Nanopore技术数据输出进行有效的校正处理。在此基础上，我们设计了一个优化的并行化Spark管道，用于基于短信读段的碱基修改检测，以及一种基于神经网络的两步分类方法，用于有效检测短信读段中的碱基修改。这项研究将大大推进最先进的算法和工具的短信读取。项目页面将从https://people.cs.clemson.edu/~luofeng/research.html链接。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.