III: Small: Algorithms for Genome Assembly of Ultra-Deep Sequencing Data

该项目将研究超深度测序数据分析（即覆盖1000倍或更高）所带来的计算挑战，特别是在从头基因组组装的背景下。随着测序成本的不断降低，超深度测序数据将变得越来越普遍，但从头组装基因组的问题在计算上仍然具有挑战性，特别是对于大型、重复的基因组。自1995年流感嗜血杆菌测序以来，组装问题的特点是测序覆盖深度有限，这主要是由于产生数据的高成本。该项目将首次研究相反的问题，即处理过度深度测序的挑战。可交付成果将包括用于基因组组装的新型软件工具，这将使全世界的研究人员和公众受益，并可能导致新的国际和工业合作。该项目将在一个高度跨学科的环境中直接支持两名研究生，以UCR在计算机科学和农业科学方面的优势为基础。本科生将有机会通过UCR的本科生研究经验（REU）网站，与附近的社区学院合作，以及新的美国教育部标题V西班牙裔服务机构补助金（UCR是一个经过认证的HSI）参与研究。该研究计划在假设输入序列数据超深的情况下，针对从头组装问题进行研究。该研究将证明，当测序深度增加到一定阈值时，测序错误使基因组组装问题变得越来越难，并且随着数据越来越多，解决方案的质量也会下降。该项目将表明，像SPAdes、IDBA-ud和Velvet这样的现代新组装器无法利用超深度测序数据。该研究计划将使用分而治之的方法处理超深度测序数据。在这个提议的元汇编器中，输入数据将被划分为最佳大小的“切片”，并使用标准组装工具（例如，Velvet, SPAdes， IDBA, Ray）单独组装每个切片。对于从头组装器，将创建一组de Bruijn图，每个图都是根据切片的排序数据构建的。在这两种情况下，将使用单个集合/图之间的多数投票策略来生成高质量的共识集合。有关该项目的更新和其他信息将在http://www.cs.ucr.edu/~stelo/iis15.htm上提供

This project will investigate the computational challenges that will brought upon by the analysis of ultra-deep sequencing data (i.e., coverage 1000x or higher), specifically in the context of de novo genome assembly. As sequencing cost continues to decrease, ultra-deep sequencing data will become more common, but the problem of de novo genome assembly remains computationally challenging, in particular for large, repetitive genomes. Since the sequencing of H. influenzae in 1995, the assembly problem has been characterized by limited depth of sequencing coverage mostly due to the high cost of generating the data. This project will investigate for the first time the opposite problem, that is, the challenge of dealing with excessive depth of sequencing. Deliverables will include novel software tools for genome assembly which will benefit researchers and the public worldwide, and potentially lead to new international and industrial collaborations. This project will directly support two graduate students in a highly interdisciplinary environment, building on UCR's strengths in Computer Science and Agricultural Sciences. Undergraduates will have opportunities to participate in research through a Research Experiences for Undergraduates (REU) site at UCR, a collaboration with a nearby community college, and a new US Department of Education Title V Hispanic Serving Institution grant (UCR is an accredited HSI).The research plan is aimed at de novo assembly problem under the assumption that the input sequencing data is ultra-deep. The study will demonstrate that when the depth of sequencing increases over a certain threshold, sequencing errors make the genome assembly problem harder and harder, and as a consequence the quality of the solution degrades with more and more data. The project will show that modern de novo assemblers like SPAdes, IDBA-ud, and Velvet are unable take advantage of ultra-deep sequencing data. The research plan will deal with ultra-deep sequencing data using a divide-and-conquer approach. In this proposed meta-assembler, the input data will be partitioned into optimal-sized "slices" and a standard assembly tool (e.g., Velvet, SPAdes, IDBA, Ray) will be used to assemble each slice individually. For the de novo assembler, a set of de Bruijn graphs will be created, each one built form the sequencing data of a slice. In both cases, a majority voting strategy among the individual assemblies/graphs will be used to generate a high-quality consensus assembly.Updates and additional information about this project will be made available at http://www.cs.ucr.edu/~stelo/iis15.htm