zbMATH — the first resource for mathematics

OMGS: optical map-based genome scaffolding. (English) Zbl 1412.92208
Cowen, Lenore J. (ed.), Research in computational molecular biology. 23rd annual international conference, RECOMB 2019, Washington, DC, USA, May 5–8, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11467, 190-207 (2019).
Summary: Due to the current limitations of sequencing technologies, de novo genome assembly is typically carried out in two stages, namely contig (sequence) assembly and scaffolding. While scaffolding is computationally easier than sequence assembly, the scaffolding problem can be challenging due to the high repetitive content of eukaryotic genomes, possible mis-joins in assembled contigs and inaccuracies in the linkage information. Genome scaffolding tools either use paired-end/mate-pair/linked/Hi-C reads or genome-wide maps (optical, physical or genetic) as linkage information. Optical maps (in particular Bionano Genomics maps) have been extensively used in many recent large-scale genome assembly projects (e.g., goat, apple, barley, maize, quinoa, sea bass, among others). However, the most commonly used scaffolding tools have a serious limitation: they can only deal with one optical map at a time, forcing users to alternate or iterate over multiple maps. In this paper, we introduce a novel scaffolding algorithm called OMGS that for the first time can take advantages of multiple optical maps. OMGS solves several optimization problems to generate scaffolds with optimal contiguity and correctness. Extensive experimental results demonstrate that our tool outperforms existing methods when multiple optical maps are available, and produces comparable scaffolds using a single optical map. OMGS can be obtained from https://github.com/ucrbioinfo/OMGS.
For the entire collection see [Zbl 1408.92004].
92D10 Genetics and epigenetics
90C27 Combinatorial optimization
Full Text: DOI