1 Notation

n Number of candidate sgRNAs

n_h Number of hits in cache

n_m Number of misses in cache

n_t System will only output n_t results

m Number of possible-o_target sgRNAs

l Length of sgRNA

t_cd Time cost on connecting database

t_rd Approximate time cost on one database operation

2 Analysis

1. System will connect to Database, which costs t_cd.

2. Retrieve data from database, which costs t_rd* (n + m).

3. System calculate each n candidate sgRNAs' scores. For n_h sgRNAs which has already calculated before, system will cost only O(n_h). For n_m others, system will calculate the scores. According to our algorithm, those sgRNAs will compare every m possible- o_target sgRNAs. In each comparison, algorithm compare all l nucleobase, make a little adds and multiplies, package result to strings and save strings to database. All n_m calculation will cost n_m* (m*l + t_rd).

4. System will sort all n result, which cost O(n log2 n).

5. Output result costs O(n_t).

3 Run Time

t_cd + t_rd* (n + m) + O(n_h) + n_m* (m* l + t_rd) + O(n log₂ n) + O(n_t)

In order to confirm our software is consistent with the experimental results, we use the experimental data on the MLE Cleavage with the different mismatches, and we compare our scoring results to corresponding to the experimental data, in addition find the correlation coefficient of them.

(A)Single mismatch

First, we use aggregate data from single-mismatch guide RNAs for 15 EMX1 targets in literature [1] (It’s relation figure is figure 2C, heat map for relative SpCas9 cleavage efficiency for each possible RNA: DNA base pair).

Heat map for relative SpCas9 cleavage efficiency for each possible RNA:DNA base pair

We use this set of data to determine the relationship between our software score with the MLE Cleavage for single mismatch position. MATLAB program is shown below:

	data=load('E:\matlab\work\igem_data.mat');
	[m n]=size(data.dataigem);
	for i=1:n
	    ave(i)=mean(data.dataigem(:,i));
	end
	M=[0,0,0.014,0,0,0.395,0.317,0,0.389,0.079,0.445,0.508,0.613,0.851,0.732,0.828,0.615,0.804,0.685,0.583];
	for j=2:20
	S(j-1)=(4*exp(1-M(j)))/((4*j+19)/19);
	end
	x=19:-1:1;
	figure(1);%title('Single mismatch,correlation coefficient=0.8840');

	subplot(1,2,1);
	stem(x,ave);
	title('The relaition between the single mismatch location and cleavage activity ');
	xlabel('location/nt');ylabel('cleavage activity');
	subplot(1,2,2);
	stem(x,S,'g');
	title('The figure of the single mismatch location and mismatch score  ');
	xlabel('location/nt');ylabel('score');

	figure(2);
	plot(x,ave,'b',x,S,'r');
	legend('mismatch cleavage activity','mismatch score');
	title('The contrast figure of the single mismatch cleavage activity and mismatch score  ');
	xlabel('location/nt');ylabel('amplitude');
	p=polyfit(ave,S,1)
	y=p(1)*ave+p(2);%Fitting equation of the straight line
	figure(3);
	plot(ave,S,'b',ave,y,'r');
	title('The relation of the single mismatch location and mismatch score  ');
	xlabel('Mismatch cleavage activity');ylabel('Mismatch score');
	legend('Relation curve','Fitting straight line');

	R=corrcoef(ave,S)%find the correlation coefficient

The result and figures are:

Therefore, the correlation coefficient between the single mismatch cleavage activity and CRISPR-X mismatch score is 0.8840. And the fitting equation of the straight line is: Y=0.1872*X+0.0987. (X stands for mismatch score).

(B) Multiple mismatches

We next explored the effect between multiple base mismatches on SpCas9 target activity and our mismatch score. We use data of sets of guide RNAs that contained varying combinations of mismatches to investigate the effect of mismatch number, position and spacing on SpCas9 target cleavage activity for four targets within the EMX1 gene. [1]

SpCas9 target cleavage activity for multiple mismatches [1]

(a) Two concatenated mismatches

MATLAB program is shown below:

	data=load('E:\matlab\work\data2misc.mat');
	[m n]=size(data.data2misc);
	for i=1:n
	    ave(i)=mean(data.data2misc(:,i));
	end
	N=[19 20;17 18;15 16;13 14;11 12;9 10;7 8;5 6;3 4];
	M=[0,0,0.014,0,0,0.395,0.317,0,0.389,0.079,0.445,0.508,0.613,0.851,0.732,0.828,0.615,0.804,0.685,0.583];
	for j=1:n
	    d0(j)=mean(N(j,:));
	    S(j)=(exp(1-M(N(j,1)))+exp(1-M(N(j,2))))/((4*d0(j)+19)/19);
	end
	x=1:n;
	subplot(1,2,1);
	stem(x,ave);
	title('The two concatenated mismatches cleavage activity ');
	xlabel('The serial number');ylabel('cleavage activity');
	subplot(1,2,2);
	stem(x,S,'g');
	title('The two concatenated mismatches score  ');
	xlabel('The serial number');ylabel('score');
	p=polyfit(S,ave,1)
	y=p(1)*S+p(2);%Fitting equation of the straight line
	figure(2);
	plot(S,ave,'b',S,y,'r');
	title('The relation of the two concatenated mismatches cleavage activity and mismatch score  ');
	xlabel('Mismatch score');ylabel('Mismatch cleavage activity');
	legend('Relation curve','Fitting straight line');
	R=corrcoef(ave,S)

The result and figures are:

Therefore, the correlation coefficient between the two concatenated mismatches cleavage activity and CRISPR-X mismatch score is 0.8902. And the fitting equation of the straight line is: Y=0.0445*X-0.0103. (X stands for mismatch score).

(b) Two interspaced mismatches

MATLAB program is shown below:

	data=load('E:\matlab\work\data2misi.mat');
	[m n]=size(data.data2misi);
	for i=1:n
	    ave(i)=mean(data.data2misi(:,i));
	end
	N=[18 20;15 20;11 20;6 20;1 20;16 18;13 18;9 18;4 18;14 16;11 16;7 16;2 16];
	M=[0,0,0.014,0,0,0.395,0.317,0,0.389,0.079,0.445,0.508,0.613,0.851,0.732,0.828,0.615,0.804,0.685,0.583];
	for j=1:n
	    d0(j)=mean(N(j,:));
	    S(j)=(exp(1-M(N(j,1)))+exp(1-M(N(j,2))))/((4*d0(j)+19)/19);
	end
	x=1:n;
	subplot(1,2,1);
	stem(x,ave);
	title('The two interspaced mismatches cleavage activity ');
	xlabel('The serial number');ylabel('cleavage activity');
	subplot(1,2,2);
	stem(x,S,'g');
	title('The two interspaced mismatches score  ');
	xlabel('The serial number');ylabel('score');
	p=polyfit(S,ave,1)
	y=p(1)*S+p(2);%Fitting equation of the straight line
	figure(2);
	plot(S,ave,'b',S,y,'r');
	title('The relation of the two interspaced mismatches cleavage activity and mismatch score  ');
	xlabel('Mismatch score');ylabel('Mismatch cleavage activity');
	legend('Relation curve','Fitting straight line');
	R=corrcoef(ave,S)

The result and figures are:

Therefore, the correlation coefficient between the two interspaced mismatches cleavage activity and CRISPR-X mismatch score is 0.7688. And the fitting equation of the straight line is: Y=0.0866*X-0.0353. (X stands for mismatch score).

(c) Three concatenated mismatches

MATLAB program is shown below:

	data=load('E:\matlab\work\data3misc.mat');
	[m n]=size(data.data3misc);
	for i=1:n
	    ave(i)=mean(data.data3misc(:,i));
	end
	N=[17 18 19;14 15 16;11 12 13;8 9 10;5 6 7;2 3 4];
	M=[0,0,0.014,0,0,0.395,0.317,0,0.389,0.079,0.445,0.508,0.613,0.851,0.732,0.828,0.615,0.804,0.685,0.583];
	for j=1:n
	    d0(j)=mean(N(j,:));
	    S(j)=4/9*(exp(1-M(N(j,1)))+exp(1-M(N(j,2)))+exp(1-M(N(j,3))))/((4*d0(j)+19)/19);
	end
	x=1:n;
	subplot(1,2,1);
	stem(x,ave);
	title('The three concatenated mismatches cleavage activity ');
	xlabel('The serial number');ylabel('cleavage activity');
	subplot(1,2,2);
	stem(x,S,'g');
	title('The three concatenated mismatches score  ');
	xlabel('The serial number');ylabel('score');
	p=polyfit(S,ave,1)
	y=p(1)*S+p(2);%Fitting equation of the straight line
	figure(2);
	plot(S,ave,'b',S,y,'r');
	title('The relation of the three concatenated mismatches cleavage activity and mismatch score  ');
	xlabel('Mismatch score');ylabel('Mismatch cleavage activity');
	legend('Relation curve','Fitting straight line');
	R=corrcoef(ave,S)

The result and figures are:

Therefore, the correlation coefficient between the three concatenated mismatches cleavage activity and CRISPR-X mismatch score is 0.8560. And the fitting equation of the straight line is: Y=0.0175*X-0.0082. (X stands for mismatch score).

(d) Three interspaced mismatches

MATLAB program is shown below:

	data=load('E:\matlab\work\data3misi.mat');
	[m n]=size(data.data3misi);
	for i=1:n
	    ave(i)=mean(data.data3misi(:,i));
	end
	N=[16 18 20;14 17 20;12 16 20;10 15 20;14 16 18;12 15 18;10 14 18;8 13 18];%The matrix element represents the position of the sgrna
	M=[0,0,0.014,0,0,0.395,0.317,0,0.389,0.079,0.445,0.508,0.613,0.851,0.732,0.828,0.615,0.804,0.685,0.583];%The weight of each position
	for j=1:n
	    d0(j)=mean(N(j,:));
	    S(j)=4/9*(exp(1-M(N(j,1)))+exp(1-M(N(j,2)))+exp(1-M(N(j,3))))/((4*d0(j)+19)/19);%Find the Smm
	end
	x=1:n;
	subplot(1,2,1);
	stem(x,ave);
	title('The three interspaced mismatches cleavage activity ');
	xlabel('The serial number');ylabel('cleavage activity');
	subplot(1,2,2);
	stem(x,S,'g');
	title('The three interspaced mismatches score  ');
	xlabel('The serial number');ylabel('score');
	p=polyfit(S,ave,1)
	y=p(1)*S+p(2);%Fitting equation of the straight line
	figure(2);
	plot(S,ave,'b',S,y,'r');
	title('The relation of the three interspaced mismatches cleavage activity and mismatch score  ');
	xlabel('Mismatch score');ylabel('Mismatch cleavage activity');
	legend('Relation curve','Fitting straight line');
	R=corrcoef(ave,S)%Find the the correlation coefficient

The result and figures are:

Therefore, the correlation coefficient between the three interspaced mismatches cleavage activity and CRISPR-X mismatch score is 0.6092. And the fitting equation of the straight line is: Y=0.0065*X-0.0018. (X stands for mismatch score).

In summary, the correlation coefficient of the above-mentioned five different conditions (single mismatch, two concatenated mismatches, two interspaced mismatches, three concatenated mismatches and three interspaced mismatches) respectively are: 0.8840, 0.8902, 0.7688, 0.8566, and 0.6092. The correlation coefficients are all over 0.6, and three correlation coefficients are over 0.85. In some extent, this result demonstrated the validity and availability of our scoring algorithm.

Reference:
• [1] DNA targeting specificity of RNA-guided Cas9 nucleases, Hsu et al, 2013