Department of Computer Science, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA.
BMC Bioinformatics. 2010 Jan 12;11:21. doi: 10.1186/1471-2105-11-21.
De Bruijn graphs are a theoretical framework underlying several modern genome assembly programs, especially those that deal with very short reads. We describe an application of de Bruijn graphs to analyze the global repeat structure of prokaryotic genomes.
We provide the first survey of the repeat structure of a large number of genomes. The analysis gives an upper-bound on the performance of genome assemblers for de novo reconstruction of genomes across a wide range of read lengths. Further, we demonstrate that the majority of genes in prokaryotic genomes can be reconstructed uniquely using very short reads even if the genomes themselves cannot. The non-reconstructible genes are overwhelmingly related to mobile elements (transposons, IS elements, and prophages).
Our results improve upon previous studies on the feasibility of assembly with short reads and provide a comprehensive benchmark against which to compare the performance of the short-read assemblers currently being developed.
De Bruijn 图是几个现代基因组组装程序的理论基础，特别是那些处理非常短的读取的程序。我们描述了一种应用 De Bruijn 图来分析原核基因组全局重复结构的方法。
我们首次对大量基因组的重复结构进行了调查。该分析为基因组组装器在广泛的读取长度范围内从头重建基因组的性能提供了上限。此外，我们证明，即使基因组本身无法重建，使用非常短的读取也可以唯一地重建大多数原核基因组中的基因。无法重建的基因绝大多数与移动元件（转座子、IS 元件和噬菌体）有关。
我们的结果改进了以前关于使用短读取进行组装的可行性的研究，并提供了一个全面的基准，以比较当前正在开发的短读取组装器的性能。
