{'fraction_non_alphanumeric': 0.020785219399538105, 'fraction_numerical': 0.012009237875288684, 'mean_word_length': 4.428571428571429, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Combining De Bruijn Graphs, Overlap Graphs and Microassembly for De Novo Genome Assembly

In this paper we present a method for de novo genome assembly that splits the process into three stages: quasicontigs assembly; contigs assembly from quasicontigs; contigs postprocessing with microassembly. We have carried out an experiment of assembling the E. Coli genome from an Illumina Genome Analyzer 160-fold coverage paired-end reads library SRR001665 with insert sizes of about 200 bp and got 247 contigs with an N50 size of 53720 and covering 98% of the reference genome. The first stage uses a de Bruijn graph built from all the input data. For each pair of reads a path connecting reads’ beginning k-mers is searched for, assuming that reads are directed inwards. For this we are searching for all paths connecting these k-mers with lengths bounded from up and down by a priori limits of insert sizes. This is done by a pair of simultaneous breadth-first searches starting from the k-mers. If all paths found have the same length and are similar to each other then we have a sequence likely to be in the genome. We call these sequences quasicontigs as they are far from being contigs but are greater than raw reads. For the second stage the previously assembled quasicontigs are used. In the beginning short ones are thrown out to get to a reasonable size of an input data, e.g. 10-fold coverage can be kept. Then contigs are assembled with the algorithm based on the overlap-layout-consensus approach. The third stage is similar to OLC and scaffolding. We are trying to order the contigs and fill the gaps between them. At first all of the paired-end reads are aligned to the contigs using Bowtie (reads in a pair are aligned independently). Then if both reads in a pair are aligned but to different contigs such reads are called bridging and the contigs are called bridged (see Figure). For every pair of bridged contigs we can infer their order from orientations of alignments of the bridging reads. After that all pairs of reads with at least one read aligned to one of these contigs are used to build a relatively small (thus, microassembly) de Bruijn graph.