关键词:
overlap graphs
de Bruijn graphs
genome assembly
long reads
string graphs
摘要:
Background:De novo genome assembly relies on two kinds of graphs:de Bruijn graphs and overlap *** graphs are the basis for the Celera assembler,while de Bruijn graphs have become the dominant technical device in the last *** two kinds of graphs are collectively called assembly ***:In this review,we discuss the most recent advances in the problem of constructing,representing and navigating assembly graphs,focusing on very large *** will also explore some computational techniques,such as the Bloom filter,to compactly store graphs while keeping all functionalities ***:We complete our analysis with a discussion on the algorithmic issues of assembling from long reads(eg.,PacBio and Oxford Nanopore).Finally,we present some of the most relevant open problems in this field.