Redundancy Treatment of NGS Contigs in Microbial Genome Finishing with Hashing-Based Approach

• Marcus Braga UFRA http://orcid.org/0000-0003-1621-4460
• Kenny Pinheiro UFPA http://orcid.org/0000-0003-3452-9271
• Fabrício Araújo UFPA http://orcid.org/0000-0001-8134-5964
• Fábio Miranda UFPA http://orcid.org/0000-0002-6823-5995
• Artur Silva UFPA http://orcid.org/0000-0002-4082-1132
• Rommel Ramos UFPA http://orcid.org/0000-0002-8032-1474

Resumo

Repetitive DNA sequences longer than reads’ length produce assembly gaps. In addition, repetition can cause complex and misassembled rearrangements that creates branches in assembler graphs. Algorithms must decide which way is the best. Incorrect decisions create false associations, called chimeric contigs. Reads coming from different copies of a repetitive region on genome may be wrongly assembled as a unique contig, a repetitive contig. Furthermore, the growth of hybrid assembling approaches using different sequencing platforms data, different fragment sizes or even data from distinct assemblers are responsible for significantly increasing in the amount of generated contigs and therefore subsequent redundancy on data. Thus, this work presents a hybrid computational method to detect and eliminate redundant contigs from microbial genome assemblies. It consists of two Hashing-Based techniques: a Bloom Filter to detect duplicated contigs and a LocalitySensitive Hashing (LSH) to remove similar contigs. The redundancy reduction facilitates downstream analysis and diminishes the required time to finishing and curate genomic assemblies. The hybrid assembly of GAGE-B dataset was performed with SPAdes (De Bruijn Graph) assembler and Fermi (OLC) assembler. The proposed pipeline was applied to the resulting contigs and the performance compared to other similar tools such as HSBLASTN, Simplifier and CD-HIT. Results are presented.

Palavras-chave: NGS contigs, Redundancy detection, Genome finishing, Bloom filter, LSH