III: Small: Collaborative Research: A Scalable and Efficient Optical Map Assembler

光学制图是一种实验室技术，用于从染色的DNA分子构建有序的高分辨率光学图。由于数据的商业生产在质量、费用和吞吐量方面得到了改善，这种类型的数据的受欢迎程度得到了扩大。例如，BioNano Genomics在2015年发布了名为Irys System的新一代光学测绘技术，该技术已被用于发现人类基因组中的二倍体变异。然而，原始光学制图数据，称为rmap，本身并没有内在的用处，必须首先组装成全基因组光学图；一种很少有非专有解决方案的计算过程。光学图谱组装问题旨在将Rmap数据拼接成全基因组光学图谱，这与基因组组装有一些相似之处，后者旨在从短序列读取中构建与感兴趣的基因组相对应的连续序列。尽管存在这种相似性，但存在一些显著的差异，这些差异阻碍了基因组组装器对后一个问题的直接应用。本研究的主要目标是通过对基因组组装算法和方法的探索和适应，构建一个可扩展和高效的光学图谱组装器。这一研究目标将通过一项教育计划得到加强，该计划旨在通过为女研究生和高中高年级学生创造研究机会来扩大计算机科学的参与。该计划将重新发展现有的生物信息学研究生课程，以便：(1)可以与生物系交叉上市，从而增加女性入学率；(2)将以项目为基础，从而产生女学生之间的支持关系。研究小组将对修读新课程的研究生以及其他计算机科学研究生课程的学生进行全面调查，以确定这些改变是否有影响。我们计划将我们的发现传播给其他机构。即使具有非常高的覆盖率和各种插入大小，由于基因组中的重复区域，仅使用短读数据进行基因组组装和结构变异检测也是脆弱的计算过程。光学图谱就是这样一种类型的数据，它是一种有序的全基因组高分辨率限制图谱，指定一个或多个短核苷酸序列的发生位置。通过图像处理识别的原始光学映射数据是一个有序的片段长度序列。该系统产生的（未组装的）光学制图数据被称为rmap，与标准基因组测序中的序列读取是同义词。光学制图之所以受到欢迎，是因为(1)能够自动生成数据；(2)它在几个大型测序项目中的应用——包括山羊、虎皮鹦鹉和Ambler trichopoda的测序项目。随着这种普及，对光学测绘数据分析方法的需求日益增长。这项工作的目标是建立一个光学图谱组装器，它对各种大小的基因组都是有效的，它将接受一组rmap作为输入，并返回一个组装好的全基因组光学图谱。因此，我们将这个更大的目标划分为以下中间研究目标，我们计划依次解决这些目标：(1)开发Rmap纠错方法；(2)创建鲁棒对齐算法；(3)创建基因组宽光学图的简洁图形表示。我们的算法贡献不仅限于光学制图数据，还可以扩展到其他类型的数据，例如PacBio和遗传连锁图。我们将通过这些研究目标和我们的推广和教育计划积极参与知识转移。这些努力将重新开发生物信息学课程，以吸引更多的女学生和促进合作关系，并继续正在进行的高中外展计划。除了这些活动，我们还将调查重新开发课程的学生和其他研究生班的学生，看看这些变化是否有影响，并在暑期指导一名高中生研究员。

Optical mapping is a laboratory technique for constructing ordered high-resolution optical maps from stained molecules of DNA. The popularity of this type of data has amplified because the commercial production of the data has improved in terms of quality, expense, and throughput. For example, BioNano Genomics released a new generation of optical mapping technology called the Irys System in 2015, which has been used to uncover diploid variation in the human genome. However, the raw optical mapping data, called Rmaps, is not inherently useful by itself and must be first assembled into a genome-wide optical map; a computational process that has very few nonproprietary solutions. The optical map assembly problem that aims to stich together the Rmap data into a genome-wide optical map has some similarities to genome assembly that aims to build contiguous sequences corresponding to the genome of interest from short sequence reads. Although this similarity exists, there are some significant differences that have prevented the direct application of genome assemblers to this latter problem. The main objective of this proposed work is to build a scalable and efficient optical map assembler through the exploration and adaptation of genome assembly algorithms and methods. This research objective will be enhanced by an education plan that aims to broaden the participation in computer science by creating research opportunities for female graduate students, as well as, high school senior students. The plan is to redevelop the existing bioinformatics graduate course so that it: (1) can be cross-listed with the Department of Biology and thus, increase the female enrolment, and (2) will be project based and thus, produce supportive relationships between female students. The team will conduct comprehensive surveys of graduate students in the redeveloped course, as well as the other graduate courses in computer science, to determine whether the changes are impactful. We plan to disseminate our findings to other institutions.Even with significantly high coverage and various insert sizes, genome assembly and structural variation detection are tenuous computational processes using short read data alone due to repetitive regions in the genome. Optical maps, which are ordered genome-wide high-resolution restriction maps that specify the positions of occurrence of one or more short nucleotide sequences, are one such type of data. The raw optical mapping data identified by the image processing is an ordered sequence of fragment lengths. The (unassembled) optical mapping data produced by the system are referred to as Rmaps and are synonymous with sequence reads in standard genome sequencing. Optical mapping has gained popularity due to (1) the ability to automate the generation of the data; and (2) its use in several large sequencing projects---including the sequencing projects of goat, budgerigar, and Ambler trichopoda. With this popularity comes the growing need for means to analyze optical mapping data. The goal of this proposed work is to build an optical map assembler that is efficient for genomes of various sizes that will accept as input a set of Rmaps and return an assembled genome-wide optical map. Thus, we have divided this larger goal into the following intermediate research objectives that we plan to tackle in succession: (1) Develop a Rmap error correction method; (2) create a robust alignment algorithm; and (3) create a succinct graph representation of a genome wide optical map. Our algorithmic contributions are not limited to optical mapping data but can be extended to other type of data, e.g., PacBio and genetic linkage maps. We will actively engage in knowledge transfer through these research objectives and our outreach and education plan. These efforts will redevelop a bioinformatics course in order to attract a greater number of female students and foster collaborative relationships, and continue an ongoing high school outreach program. In addition to these activities, we will survey the students in the redeveloped course and other graduate classes to see whether the changes were impactful, and mentor a senior high school student researcher during the summers.