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

该项目将研究超深度测序数据分析带来的计算挑战（即，覆盖率1000 x或更高），特别是在从头基因组组装的情况下。随着测序成本的持续降低，超深度测序数据将变得更加普遍，但从头基因组组装的问题仍然具有计算挑战性，特别是对于大型重复基因组。 由于H.在1995年的流感病毒中，组装问题的特征在于有限的测序覆盖深度，这主要是由于产生数据的高成本。 该项目将首次调查相反的问题，即处理过度测序深度的挑战。 可移植物将包括用于基因组组装的新型软件工具，这将使全世界的研究人员和公众受益，并可能导致新的国际和工业合作。该项目将直接支持两名研究生在一个高度跨学科的环境，建立在计算机科学和农业科学的UCR的优势。本科生将有机会通过UCR的本科生研究经验（REU）网站参与研究，与附近的社区学院合作，以及新的美国教育部Title 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