Overlap-Layout-Consensus (OLC)
经典的序列组装方法，通过三个步骤完成组装：计算读段间的重叠、构建布局图、生成一致序列。 该方法适合处理长读段数据，能够产生高质量的组装结果。
| Property | Value |
|---|---|
| Purpose | 长读段序列组装 |
| Time Complexity | O(n^2) |
| Space Complexity | O(n^2) |
| Year | 2010 |
| Category | Sequence Assembly |
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
Canu · Flye · Miniasm