Skip to main content
Figure 7 | BMC Bioinformatics

Figure 7

From: Automated hierarchical classification of protein domain subfamilies based on functionally-divergent residue signatures

Figure 7

Time complexity of Steps 2 and 3 of the amcBPPS program. (A) Plot of run times versus the number of aligned residues in the input multiple alignment. Shown are data points from Table 1 and the corresponding linear regression trend line (r = 0.95). Because this plot is shown using a logarithmic scale for both axes, the observed time complexity O(n) of the program can be estimated from the slope of the trend line: Since time t = c nk, it follows that logt = logc + k logn on a log-log plot. The slope of the trend line is k = 1.2 indicating an observed time complexity somewhat worse than linear. (B) Plot of run times versus the number of aligned residues times the number of nodes in the hierarchy created in Step 2. This plot results in a slightly better fit (r = 0.98). The slope of the trend line is k = 0.9 indicating an observed time complexity that is essentially linear.

Back to article page