Cactus
基于祖先引导的全基因组比对和泛基因组图构建方法，使用 progressive cactus 算法处理多物种间的共线性关系。该方法可构建大规模的全基因组比对和泛基因组 参考图。
| Property | Value |
|---|---|
| Purpose | 多物种全基因组比对和泛基因组构建 |
| Time Complexity | O(n^2 * k) |
| Space Complexity | O(n * k) |
| Year | 2011 |
| Difficulty | Advanced |
| Languages | C, Python |
| Category | Graph Genomics |
Complexity Analysis
- Time Complexity:
O(n^2 * k) - Space Complexity:
O(n * k)
Performance Insight: The time complexity of this algorithm is polynomial.
Note: Complexity analysis is based on theoretical models. Actual runtime is affected by input scale, hardware, and implementation optimizations. Benchmark for your specific workload.
Literature & Implementation
Related Tools
Minigraph · PGGB · Mauve