Time Complexity Analysis

The algorithms used in Biodesigner could be grouped into two categories: preprocessing part and executing part.

Preprocessing Part

The preprocessing part includes three algorithms. Here we assume there are n devices and each device contains at most m biobrickes.

The first one is to count the probabilities of two successive biobrickes, three successive biobrickes, four successive biobrickes and five successive biobrickes. Here successive biobrickes means the biobrickes are neighbors. Thus the number of two successive biobrickes, three successive biobrickes, four successive biobrickes and five successive biobrickes are n(m-1),  n(m-2), n(m-3), n(m-4), respectively. Hash tables are used to store these successive biobrickes. Therefore, the probabilities could be obtained by scanning the device chains four times. Thus, the time complexity of this algorithm is O(2n(m-1)+3n(m-2)+4n(m-3)+5n(m-3))=O(nm).   

The second one is to count the probabilities of the first biobrick of each device chain. This work could be done by scanning the first biobrick of each chain. Thus, the complexity of this algorithm is O(n).

The third one is to calculate the hamming distances of each paired biobrickes.  Since there are n device chains and each device contains at most m biobrickes. Therefore, there are at most nm biobrickes, which means there are at most nm*nm paired biobrickes. The calculation of hamming distances between two sequences with length l could be done in O(l) time. Thus, the complexity of this algorithm is O(l*nm*nm)=O(ln²m²).

Hence, the time complexity of preprocessing part is O(nm)+O(n)+O(ln²m²) =O(ln²m²).

Executing Part

The executing part contains two algorithms. Here we assume the given device chain contains at most m biobrickes.

The first one is to inquire the probabilities of two successive biobrickes, three successive biobrickes, four successive biobrickes and five successive biobrickes of a given device chain. Since all the data is stored in a hash table and the access of hash table needs O(1) time. Thus, the time complexity of this algorithm is O(m).

The second one is to store the given device chain. This work is done by store the two successive biobrickes, three successive biobrickes, four successive biobrickes and five successive biobrickes of the given device chain into the hash table. Thus, the time complexity of this algorithm is O(m).

Hence, the time complexity of executing part is O(m).

Note, we only need to execute the preprocessing part once. After the execution of preprocessing part, all the data is store in database. When using our software, users do not need to waste their time for the preprocessing part as it has been executed.

Experimental Results

In order to test the performance of our software, we collected about 3600 device chains from Registry of Standard Parts, and extracted the associate relationships among these chains. All these information are stored in our database.

Firstly, we tested the response time of different functions of our software. Table 1 shows the results of different query functions. The results are averaged from 10 independent runs. From the results, we can find that all the time is really short, less than 0.1 seconds.

Table 1 Response time for different functions

 

 

We also tested the response time of recommendation. Table 2 listed the results in terms of different number of given biobricks. Since our software recommend biobrick based on at most 4 biobricks’ information. Thus, the maximum number of given biobricks is 4. These times are really short, less than 0.4 seconds. Users could get the recommendation almost instantly. This could greatly reduce the time used for designing.

Table 2 Response time for recommending based on different number of biobricks

 

 

Secondly, we tested the performance of recommendation. 10 device chains were randomly selected for this test. Table 3 shows the results, where the recommendation ratio is the ratio of the number of correctly recommended biobricks over the length of device chains, and the correctly recommended biobricks means these biobricks are in recommended lists. The average recommendation ratio is 75.4%. This ratio actually is really high, since only 24.6% of biobricks are not in the recommended lists.