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

该项目将调查超深度测序数据(即覆盖率为1000倍或更高)的分析将带来的计算挑战，特别是在从头开始基因组组装的背景下。随着测序成本的不断降低，超深测序数据将变得越来越普遍，但从头组装基因组的问题在计算上仍然具有挑战性，特别是对于大的、重复的基因组。自从1995年对流感嗜血杆菌进行测序以来，组装问题的特点是测序覆盖的深度有限，这主要是因为生成数据的成本很高。这个项目将首次调查相反的问题，即处理过度深度的测序的挑战。可交付成果将包括用于基因组组装的新型软件工具，这些工具将使世界各地的研究人员和公众受益，并可能导致新的国际和行业合作。该项目将在UCR在计算机科学和农业科学方面的优势基础上，在高度跨学科的环境中直接支持两名研究生。本科生将有机会通过UCR的本科生研究体验(REU)网站，与附近的社区大学合作，以及新的美国教育部标题V拉美裔服务机构拨款(UCR是经认可的HSI)参与研究。研究计划旨在假设输入的排序数据超深入的情况下，重新组装问题。这项研究将证明，当测序深度增加到一定阈值以上时，测序错误会使基因组组装问题变得越来越困难，结果是随着数据的增加，解决方案的质量会下降。该项目将表明，现代的从头组装，如黑桃，IDBA-UD，和天鹅绒无法利用超深测序数据。该研究计划将使用分而治之的方法处理超深测序数据。在这个建议的元汇编器中，输入数据将被分割成大小最佳的“切片”，并将使用标准组装工具(例如，天鹅绒、黑桃、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