seqwish
从全对全比对结果构建无损变异图的工具，将比对中的所有对齐关系编码为 图结构。该方法是 PGGB 工作流的核心组件，保证不丢失任何序列和比对信息。
| Property | Value |
|---|---|
| Purpose | 从比对结果构建无损变异图 |
| Time Complexity | O(n^2) |
| Space Complexity | O(n^2) |
| Year | 2020 |
| Difficulty | Advanced |
| Languages | C++ |
| Category | Graph Genomics |
Complexity Analysis
- Time Complexity:
O(n^2) - Space Complexity:
O(n^2)
Performance Insight: The time complexity of this algorithm is quadratic (O(n²)), suitable for moderate data sizes; consider approximation algorithms for large inputs. High space complexity; consider Hirschberg-style space-optimized variants for very long sequences.
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
PGGB · odgi · Minigraph