How to apply de Bruijn graphs to genome assembly.
How to apply de Bruijn graphs to genome assembly.
复制标题
DOI：
10.1038/nbt.2023
复制
发表时间：
2011-11-08
影响因子：
46.9
通讯作者：
Tesler G
中科院分区：
文献类型：
--
作者：
Compeau PE;Pevzner PA;Tesler G
下一代测序（NGS）算法思想的发展可以追溯到300年前的普鲁士城市柯尼斯堡（今俄罗斯加里宁格勒），在那里，七座桥梁将位于普雷格尔河两岸的城市四个部分和两个河岛连接起来（图1a）。康尼斯堡的居民喜欢在城市中漫步，他们想知道：是否有可能通过七座桥中的每一座都只走一次，然后回到出发地，参观城市的每一个部分？1735年，伟大的数学家莱昂哈德·欧拉（Leonhard Euler）在解决柯尼斯堡桥问题上取得了突破性的概念，他的第一个想法是将每个大陆块表示为一个点（称为节点），将每个桥表示为连接两个点的线段（称为边）。这就创建了一个图--一个由边连接的节点网络（图1b）。通过描述一个确定任意图是否包含欧拉圈（一条穿过图的路径，它只访问每一条边一次，然后返回到它开始的地方）的过程，欧拉不仅解决了柯尼斯堡桥问题，而且有效地启动了今天被称为图论的整个数学分支。
The development of algorithmic ideas for Next-Generation Sequencing (NGS) can be traced back three hundred years to the Prussian city of Königsberg (present-day Kaliningrad, Russia), where seven bridges joined the four parts of the city located on opposing banks of the Pregel River and two river islands (Fig. 1a). Königsberg’s residents enjoyed strolling through the city, and they wondered: is it possible to visit every part of the city by walking across each of the seven bridges exactly once and returning to one’s starting location? Remarkably, the conceptual breakthrough used in 1735 to solve this Bridges of Königsberg Problem by the great mathematician Leonhard Euler1 also enables the assembly of billions of short sequencing reads.Euler’s first insight was to represent each landmass as a point (called a node) and each bridge as a line segment (called an edge) connecting the appropriate two points. This creates a graph—a network of nodes connected by edges (Fig. 1b). By describing a procedure for determining whether an arbitrary graph contains an Eulerian cycle (a path through the graph that visits every edge exactly once and returns back where it started), Euler not only resolved the Bridges of Königsberg Problem but also effectively launched the entire branch of mathematics known today as graph theory2.
登录
查看更多内容
影响因子：
7
作者：
Chaisson, Mark J.;Pevzner, Pavel A.
通讯作者：
Pevzner, Pavel A.
影响因子：
7
作者：
Schatz, Michael C.;Delcher, Arthur L.;Salzberg, Steven L.
通讯作者：
Salzberg, Steven L.
DOI：
10.1089/cmb.1995.2.291
发表时间：
1995-01-01
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
Idury, R M;Waterman, M S
通讯作者：
Waterman, M S
影响因子：
56.9
作者：
FLEISCHMANN, RD;ADAMS, MD;VENTER, JC
通讯作者：
VENTER, JC
影响因子：
7
作者：
Li, Ruiqiang;Zhu, Hongmei;Wang, Jun
通讯作者：
Wang, Jun