From: MUSCLE: a multiple sequence alignment method with reduced time and space complexity
Step | O(Space) | O(Time) |
---|---|---|
K-mer distance matrix | N^{2} + L | N ^{2} L |
UPGMA | N ^{2} | N ^{2} |
Progressive (one iteration) | L_{P}^{2} = NL + L^{2} | L_{P}^{2} = N^{2} + L^{2} |
Progressive (root alignment) | NL_{P} = N^{2} + NL | NL_{P} log N = N^{2} log N + NL log N |
Progressive (N iterations + root) | N^{2} + NL + L^{2} | N^{3} + NL^{2} |
Refinement (one edge) | NL_{P} + L_{P}^{2} = N^{2} + L^{2} | N^{2}L_{P} + L_{P}^{2} = N^{3}+ L^{2} |
Refinement (N edges) | N^{2} + L^{2} | N ^{4} + NL ^{2} |
TOTAL | N^{2} + L^{2} | N^{4} + NL^{2} |