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

光学映射是一种实验室技术，用于从染色的DNA分子中构建有序的高分辨率光学映射。这种类型的数据之所以受欢迎，是因为数据的商业生产在质量、成本和吞吐量方面都有所提高。例如，生物纳米基因组公司在2015年发布了名为Irys系统的新一代光学测绘技术，该系统已被用于发现人类基因组中的二倍体变异。然而，被称为Rmap的原始光学图谱数据本身并不有用，必须首先组装成全基因组的光学图谱；这是一个计算过程，几乎没有非专有的解决方案。光学图谱组装问题旨在将Rmap数据粘合到基因组范围的光学图谱中，这与旨在从短序列读取中构建与感兴趣的基因组相对应的连续序列的基因组组装有一些相似之处。尽管存在这种相似性，但有一些显著的差异阻碍了基因组组装器对后一个问题的直接应用。这项拟议工作的主要目标是通过探索和适应基因组组装算法和方法来构建可扩展和高效的光学地图组装器。这一研究目标将通过一项教育计划得到加强，该计划旨在通过为女研究生和高中生创造研究机会，扩大对计算机科学的参与。该计划将重新开发现有的生物信息学研究生课程，以便：(1)可以与生物系交叉列出，从而增加女学生的入学人数；(2)将以项目为基础，从而在女学生之间建立相互支持的关系。该团队将对重新开发的课程以及其他计算机科学研究生课程的研究生进行全面调查，以确定这些变化是否有影响。我们计划将我们的发现传播到其他机构。由于基因组中的重复区域，即使具有显著的高覆盖率和不同的插入大小，基因组组装和结构变异检测也是仅使用短读数据的微不足道的计算过程。光学图谱是一种这样的数据类型，它是指定一个或多个短核苷酸序列出现位置的有序全基因组高分辨率限制性图谱。由图像处理识别的原始光学映射数据是片段长度的有序序列。该系统产生的(未组装的)光学作图数据被称为Rmap，并与标准基因组测序中的序列读取同义词。光学测绘之所以流行，是因为(1)自动生成数据的能力；以及(2)它在几个大型测序项目中的使用-包括山羊、虎皮鹦鹉和毛虫的测序项目。随着这种流行，对分析光学测绘数据的手段的需求也越来越大。这项拟议工作的目标是建立一个对不同大小的基因组有效的光学图谱组装器，它将接受一组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.