Fast genomic optical map assembly algorithm using binary representation

Abstract

Reducing the cost of sequencing genomes provided by next-generation sequencing technologies has greatly increased the number of genomic projects. As a result, there is a growing need for better assembly and assembly validation methods. One promising idea is to use heterogeneous data in assembly projects. Optical Mapping (OM) is beneficial in validating genomic assemblies, correction and scaffolding. Single raw OM read describes a DNA molecule's long fragment, up to 1Mbp. Raw OM data from the same genome could be assembled to create consensus maps that span an entire chromosome. The assembly process is computationally hard because of the large number of errors in input data. This work describes a new algorithm and computer program to assemble OM reads without a reference genome. In our algorithm, we explored binary representation for genome maps. We focused on the efficiency of data structures and algorithms and scale on parallel platforms. The algorithm consists of several steps, of which the most important are : (1) conversion of the restriction maps into binary strings, (2) detection of overlaps between restriction maps, (3) determining the layout of restriction maps set, (4) creation of consensus genomic maps. Our algorithm deals with optical mapping data with low error levels but fails with high-level error reads. We developed a software library, console application and module for Python language. The approach presented in this paper proved to be faster than a dynamic programming approach and performed well on error-free data. It could be used as a step of de novo assembly pipelines or to detect misassemblies. The software is freely available in a public repository under GNU LGPL v3 license (https://sourceforge.net/p/binary-genome-maps/code).