Table 1 Complexity of CLUSTALW. Here we show the big-O asymptotic complexity of the elements of CLUSTALW as a function of L, the typical sequence length, and N, the number of sequences, retaining the highest-order terms in N with L fixed and vice versa.
From: MUSCLE: a multiple sequence alignment method with reduced time and space complexity
Step | O(Space) | O(Time) |
|---|---|---|
Distance matrix | N2 + L | N 2 L 2 |
Neighbor joining | N 2 | N 4 |
Progressive (one iteration) | NLP + LP = NL + L2 | NLP + LP2 = N2 + L2 |
Progressive (total) | NL + L2 | N3 + NL2 |
TOTAL | N2 + L2 | N4 + L2 |