IDBA：实用的迭代德布鲁因图从头组装器

### IDBA：实用的迭代德布鲁因图从头组装器 #### 1. 算法基础 IDBA 算法在每次迭代中，通常将 k 值增加 1（即 s = 1），这对于获得高质量的重叠群（contigs）至关重要。不过，为了在算法效率和重叠群质量之间取得平衡，也可以设置 s > 1，即在每次迭代步骤中将 k 值增加超过 1。 #### 2. 实现细节 - **内存使用**：IDBA 的内存使用仅约为其他现有工具的 20 - 30%。这是因为在过滤步骤中（算法 IDBA 的第 2 行），80% 的假阳性顶点被移除，并且 IDBA 使用紧凑的哈希表隐式表示德布鲁因图，每条边仅用一位表示。 - **运行时间**：尽管 IDBA 是从 Hkmin 逐步构建到 Hkmax，但运行时间并不与 kmax 和 kmin 之间的 k 值数量成正比。根据定理 1，Hk 中的重叠群也是 Hk + 1 中的重叠群，因此 IDBA 只需检查 Hk 中的分支是否能在 Hk + 1 中得到解决。由于每次迭代中由重叠群表示的读取被移除，每次迭代中的读取数量减少。实际上，在构建 Hkmin + 1 时，大约一半的读取被移除，IDBA 的运行速度比 Abyss 快得多，约为 Velvet 的三分之一。 #### 3. 实验结果 ##### 3.1 模拟数据 使用大肠杆菌（Escherichia coli）的基因组进行模拟实验，基因组长度为 5.6 M，读取随机均匀采样，覆盖率为 30x，错误率为 1%，读取长度为 75，插入距离为 250。 |算法|时间|内存|k|重叠群数量|N50|最大长度|假阳性重叠群（总长度）|覆盖率| | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | |Velvet|155s|1641M|35|1412|24772|127265|70(35589)|95.29%| |Edena|957s|678M|40|4672|5104|46908|650 (72019)|97.22%| |IDBA|371s|360M|25–50|1563|63218|217365|9(4654)|97.96%| |IDBA - pe|412s|360M|25–45|709|105579|217365|43 (164120)|93.94%| |Abyss|1114s|1749M|40|1390|22109|87118|66 (34998)|95.05%| |abyss - pe|1237s|1749M|40|484|59439|226626|186 (352437)|91.39%| |上限| - | - |50|1561|63218|217365|0 (0)|99.11%| 从表格数据可以看出，IDBA 产生的重叠群比其他算法长得多。在不使用配对信息时，IDBA 的 N50（63218）约为次优算法（Velvet 的 24772）的三倍，且与上限相同。IDBA 产生的错误重叠群数量最少，所有