A Classification of de Bruijn Graph Approaches for De Novo Fragment Assembly

• Elvismary Molina de Armas PUC-Rio http://orcid.org/0000-0002-0606-5994
• Maristela Holanda UNB http://orcid.org/0000-0002-0883-2579
• Daniel de Oliveira UFF http://orcid.org/0000-0001-9346-7651
• Nalvo F. Almeida UFMS http://orcid.org/0000-0001-5615-1746
• Sérgio Lifschitz PUC-Rio http://orcid.org/0000-0003-3073-3734

Resumo

Research in bioinformatics has changed rapidly since the advent of next-generation sequencing (NGS). Despite the positive impact on cost reduction, assembling the generated reads remains a challenge. This paper presents in detail the main ideas related to de novo assembly, the technologies involved, and theoretical concepts about the de Bruijn graph structure. We also explain the existing approaches to minimize the memory requirements for de Bruijn graph construction. Finally, we propose a comparative view of several solutions, including the k-mers codification and the data structures used to represent and persist them.