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

University Of California-Riverside, Riverside CA

Investigators

Abstract

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.