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

A New Approach for De Bruijn Graph Construction in De Novo Genome Assembling Fragment assembly is a current fundamental problem in bioinformatics. In the absence of a reference genome sequence that could guide the whole process, a de Bruijn Graph data structure has been considered to improve the computational processing. Notably, we need to count on a broad set of  k mers, biological sequences substrings. However, the construction of a de Bruijn Graph has a high computational cost, primarily due to main memory consumption. Some approaches use external memory processing to achieve feasibility. These solutions generate all  k mers with high redundancy, increasing the number of managed data and, consequently, the number of IO operations. This work proposes a new approach for de Bruijn Graph construction that does not need to generate all  k mers. The solution enables to reduce computational requirements and execution feasibility.