III: Small: Genome Assembly Using Sparse Sequence Information

III：小：使用稀疏序列信息进行基因组组装

• 批准号: 1117247
• 负责人: Mihai Pop
• 金额: $ 49.28万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117247&HistoricalAwards=false
• 关键词: III; Small; Genome; Assembly; Using

Rapid advances in DNA sequencing technologies are providing scientists with the ability to rapidly and cost-effectively decode the genomes of organisms. Current technologies, however, can only reconstruct a fragmented picture of a genome's chromosomes. Stitching the resulting fragments together into a complete genome currently requires costly and time-intensive laboratory experiments. The goal of this proposal is to develop new computational approaches that combine sequencing data with the data generated by modern high-throughput mapping technologies in order to enable the automated reconstruction of much larger genomic segments, up to whole chromosomes, than currently possible. The proposed research will be closely integrated with educational activities at the University of Maryland, College Park through the mentoring of undergraduate and graduate students and of a postdoctoral fellow. Despite tremendous advances over the past 20+ years, both in sequencing technologies, and in computational algorithms for genome assembly, the genomes of the majority of organisms cannot be completely reconstructed through fully-automated processes. The best sequencing technologies can only "read" up to a few 1000s of letters yet most organisms contain millions to billions of letters in their genomes. At the same time, genome assembly is a difficult computational problem and even the best assembly software can only generate fragmented reconstructions of the genomes being sequenced, primarily due to repetitive sequences found in the genomes of most organisms. The full completion of highly-repetitive genomes requires time- and labor-intensive processes that often last multiple years. High-throughput optical mapping technologies provide a promising source of information that could be used to disambiguate genomic repeats and automatically reconstruct much larger segments of an organism's genome than possible through the sole use of current sequencing data. Optical mapping data describe the relative placement of multiple genomic landmarks (e.g. restriction enzyme recognition sites) along large stretches of a genome, spanning hundreds of thousands of letters and even whole chromosomes. To date, however, there is no algorithmic framework that allows the incorporation of this rich source of information in the assembly process. Specifically, genome assembly can be formulated as a graph traversal problem, finding a path through a complex graph that satisfies the constraints imposed by the data provided to the assembler. Optical mapping data encode a new type of constraint on the possible traversals of a graph, potentially leading to a more complete reconstruction of genomes. The main goal of this proposal is to develop an algorithmic framework and associated software tools, that enable the use of optical mapping and optical sequencing data during the assembly process. It is important to note that constrained graph traversal problems are generally computationally intractable. We propose several heuristic traversals algorithms that can use optical mapping information and are likely to perform well in practice. In addition, computational analyses will be used to determine the combination of parameters for the mapping experiment that generate data that is most informative for the assembly process. These computational predictions will be validated in an experimental setting.In addition to the main research objective, this proposal will directly contribute to the education of future generations of scientists, both through the mentoring of graduate students and post-doctoral fellows, and through the continuation of a summer research internship for undergraduate and highschool students. The software developed in this proposal, as well as the scientific publications arising from this work, will be freely and broadly disseminated through open licensing.

DNA测序技术的快速发展为科学家提供了快速、经济高效地解码生物基因组的能力。然而，目前的技术只能重建基因组染色体的碎片化图像。目前，将产生的片段缝合在一起形成完整的基因组需要昂贵且耗时的实验室实验。这项提议的目标是开发新的计算方法，将测序数据与现代高通量绘图技术产生的数据相结合，以便能够自动重建比目前可能的大得多的基因组片段，甚至整个染色体。拟议的研究将通过指导本科生和研究生以及一名博士后研究员，与马里兰大学帕克学院的教育活动密切结合。尽管在过去的20多年里，在测序技术和基因组组装的计算算法方面都取得了巨大的进步，但大多数生物的基因组不能通过全自动过程完全重建。最好的测序技术只能“读取”几千个字母，然而大多数生物的基因组中包含数百万到数十亿个字母。与此同时，基因组组装是一个困难的计算问题，即使是最好的组装软件也只能生成正在测序的基因组的片断重建，这主要是由于在大多数生物的基因组中发现了重复序列。完全完成高度重复的基因组需要耗费时间和劳动的过程，通常持续数年。高通量光学测绘技术提供了一个很有希望的信息源，可以用来消除基因组重复序列的歧义，并自动重建比单独使用当前测序数据可能要大得多的生物基因组片段。光学作图数据描述了多个基因组标志物(如限制性内切酶识别位点)在跨越数十万个字母甚至整个染色体的大范围基因组上的相对位置。然而，到目前为止，还没有一个算法框架允许在组装过程中结合这种丰富的信息源。具体地说，基因组组装可以被描述为一个图遍历问题，找到一条通过复杂图的路径，该路径满足提供给组装者的数据施加的约束。光学映射数据编码了一种对图可能遍历的新型约束，潜在地导致了更完整的基因组重建。这项提议的主要目标是开发一个算法框架和相关软件工具，以便能够在组装过程中使用光学测绘和光学测序数据。值得注意的是，受约束的图遍历问题通常在计算上很难处理。我们提出了几种启发式遍历算法，这些算法可以利用光学映射信息，并且可能在实践中执行得很好。此外，将使用计算分析来确定映射实验的参数组合，以生成对组装过程最有用的数据。这些计算预测将在实验环境中得到验证。除了主要的研究目标外，这项建议将通过指导研究生和博士后研究员，以及通过继续为本科生和高中生进行暑期研究实习，直接为未来几代科学家的教育做出贡献。本提案中开发的软件以及这项工作产生的科学出版物将通过开放许可自由和广泛地传播。