III: Small: Improving de novo Genome Assembly using Optical Maps

在地球上估计有870万个真核物种中，只有几千个物种被测序和组装。虽然测序成本持续下降，但重新组装序列的问题在计算上仍然具有挑战性，特别是对于大型、重复的基因组。市场上新的、具有成本效益的光学测绘技术正在创造机会，以改善组装邻接性和减少组装错误。尽管光学图谱在基因组组装管道中很重要，但有一套令人惊讶的自动化软件工具可以让用户利用它们。事实上，这些步骤中的一些仍然是手动进行的，繁琐且容易出错。该项目将开发创新的算法解决方案，以自动和准确地改进从头开始的基因组组装。交付成果将包括基因组组装的软件工具，这将使世界各地的研究人员和公众受益，并可能导致新的国际和行业合作。该项目将在一个高度跨学科的环境中直接支持两名研究生。本科生将有机会与附近的社区学院合作参与研究。在一年一度的Bourns科学和工程日等外展活动中，通过基于该项目的演示，将激励年轻人追求科学和技术事业。该项目的目标是提供用户友好的软件工具，使用户能够利用光学地图提高组装邻接性和减少组装错误。拟议的研究计划围绕以下问题阐述：如何利用一个或多个光学图谱(A)准确检测和分裂嵌合重叠群和嵌合分子，(B)准确创建支架基因组组合，(C)准确缝合多个(冗余)基因组组合，以及(D)设计、测试和部署用户友好的基因组浏览器，以直观地检查多个光学图谱。对于任务(A)，研究小组将利用多个从头基因组组合(使用相同测序数据的不同组装器或具有不同参数设置的相同组装器获得)和一个或多个光学图谱来校正嵌合重叠群和嵌合光学分子。组件和光学映射之间的对准冲突将被编码在加权图中。冲突图的每个连通分量的最小顶点覆盖将提供最简约的解决方案。同样，对于其他任务，方法是将这些问题的约束编码到加权图(例如，重叠或冲突图)中，将它们框架为组合优化问题，并提供高效的算法来计算最优全局解或近似保证。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Out of the estimated 8.7 million eukaryotic species on the planet, only a few thousands have been sequenced and assembled. While sequencing cost continues to decrease, the problem of de novo sequence assembly is still computationally challenging, in particular for large, repetitive genomes. New, cost-effective optical mapping technologies on the market are creating opportunities to improve assembly contiguity and to reduce assembly errors. Despite the importance of optical maps in the genome assembly pipeline, there is a surprisingly small set of automated software tools to allow users to take advantage of them. In fact, some of these steps are still carried out manually, which is tedious and error-prone. This project will develop innovative algorithmic solutions for automatically and accurately improve de novo genome assembly. Deliverables will include 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. Undergraduates will have opportunities to participate in research, in collaboration with a nearby community college. Young people will be inspired to pursue science and technology careers through demonstrations based on this project at outreach events such as the annual Bourns Science and Engineering Day.The goals of this project are aimed at providing user-friendly software tools to enable users to enhance assembly contiguity and reduce assembly errors using optical maps. The proposed research plan is articulated around the following questions: how to take advantage of one or more optical maps (A) to accurately detect and split chimeric contigs and chimeric molecules, (B) to accurately create scaffold genome assemblies, (C) to accurately stitch multiple (redundant) genome assemblies, and (D) to devise, test and deploy a user-friendly genome browser to visually inspect multiple optical maps. For task (A) the team will leverage multiple de novo genome assemblies (obtained using different assemblers on the same sequencing data or the same assembler with different parameter settings) and one or more optical maps to correct both chimeric contigs and chimeric optical molecules. Alignment conflicts between the assemblies and the optical maps will be encoded in a weighted graph. The minimum vertex cover of each connected component of the conflict graph will provide the most parsimonious solution. Similarly, the approach for other tasks is to encode the constraints of these problems in weighted graphs (e.g., overlap or conflict graphs), frame them as combinatorial optimization problems and provide efficient algorithms to compute optimal global solutions or approximation guarantees.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.