What do Eulerian and Hamiltonian cycles have to do with genome assembly?
What do Eulerian and Hamiltonian cycles have to do with genome assembly?
复制标题
DOI：
10.1371/journal.pcbi.1008928
复制
发表时间：
2021-05
影响因子：
4.3
通讯作者：
Pop M
中科院分区：
文献类型：
--
作者：
Medvedev P;Pop M
许多学生被教导基因组组装使用的二分法之间的复杂性找到欧拉和汉密尔顿循环（容易与困难，分别）。这种二分法有时被用来激励德布鲁因图在实践中的使用。在本文中，我们解释说，虽然德布鲁因图确实是非常有用的，原因无关的复杂性的哈密顿和欧拉循环问题。我们给出两个参数。第一个是基因组重建从来都不是唯一的，因此用于寻找欧拉或哈密顿循环的算法不是实践中使用的任何组装算法的一部分。第二个是，即使需要任意的基因组重建，也可以在欧拉和汉密尔顿范式中的线性时间内完成。
Many students are taught about genome assembly using the dichotomy between the complexity of finding Eulerian and Hamiltonian cycles (easy versus hard, respectively). This dichotomy is sometimes used to motivate the use of de Bruijn graphs in practice. In this paper, we explain that while de Bruijn graphs have indeed been very useful, the reason has nothing to do with the complexity of the Hamiltonian and Eulerian cycle problems. We give 2 arguments. The first is that a genome reconstruction is never unique and hence an algorithm for finding Eulerian or Hamiltonian cycles is not part of any assembly algorithm used in practice. The second is that even if an arbitrary genome reconstruction was desired, one could do so in linear time in both the Eulerian and Hamiltonian paradigms.
登录
查看更多内容
影响因子：
9.5
作者：
Medvedev, Paul
通讯作者：
Medvedev, Paul
影响因子：
3
作者：
Kingsford C;Schatz MC;Pop M
通讯作者：
Pop M
影响因子：
1.7
作者：
Tomescu, Alexandru I.;Medvedev, Paul
通讯作者：
Medvedev, Paul
影响因子：
3
作者：
Bresler, Guy;Bresler, Ma'ayan;Tse, David
通讯作者：
Tse, David
DOI：
10.1007/978-1-84800-998-1_1
发表时间：
2009-01-01
期刊：
DIGRAPHS: THEORY, ALGORITHMS AND APPLICATIONS, SECOND EDITION
影响因子：
--
作者：
Bang-Jensen, Jorgen;Gutin, Gregory
通讯作者：
Gutin, Gregory