OMGS: Optical Mapbased Genome Scaffolding 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 misjoins in assembled contigs and inaccuracies in the linkage information. Genome scaffolding tools either use pairedendmatepairlinkedHiC reads or genomewide maps (optical, physical or genetic) as linkage information. Optical maps (in particular Bionano Genomics maps) have been extensively used in many recent largescale 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.comucrbioinfoOMGS.

SOF: An Efficient String Graph Construction Algorithm In contrast to genome assemblers that use de Bruijn graphs, those based on string graphs are able to losslessly retain information from sequence data. However, despite the advantages provided by a string graph framework in repeat detection and in maintaining read coherence, the high computational cost for constructing a string graph hinders its usability for genome assembly. Even though different algorithms have been proposed over the last decade for string graph construction, efficiency is still a challenge due to the demand for processing a large amount of sequence data generated by NextGeneration Sequencing technologies. In this paper, we provide a novel, linear time and alphabetsizeindependent algorithm SOF which uses the property of irreducible edges and transitive edges to efficiently construct a string graph from an overlap graph. Experimental results show that SOF is at least 2.3 times faster than the string graph construction algorithm provided in SGA (one of the most popular string graphbased assemblers), while maintaining almost the same memory footprint as SGA. Moreover, the implementation of SOF as a subprogram in the SGA assembly pipeline will allow a user easy access to the preprocessing and postprocessing steps for genome assembly provided in SGA. Implementation: https:github.comiqbalmorshedsof