Improving efficiency of a char array function

2017 1 8
2 个回答
回答已采纳
更新时间：2017 1 9
5 次查看（30 天）

0 个投票

I have built a function to be run 100000 times in a loop. Its input, "motifs", is a full 20x15 char array, containing only four types of characters, 'A', 'C', 'G', 'T'. I am wondering if my implementation, below, can be improved of if it is pretty much as fast as it gets:
% Find consensus string and score of a motifs array
function [score, count, consensus] = scoremotifs_2(motifs)
count = [ sum(motifs == 'A',1) ;
sum(motifs == 'C',1) ;
sum(motifs == 'G',1) ;
sum(motifs == 'T',1) ];
[count_max, consensus_num] = max(count);
consensus(consensus_num == 1) = 'A';
consensus(consensus_num == 2) = 'C';
consensus(consensus_num == 3) = 'G';
consensus(consensus_num == 4) = 'T';
score = sum(sum(motifs ~= consensus));

3 个评论
显示 1更早的评论 隐藏 1更早的评论

the cyclist
the cyclist 2017-1-8
It might be helpful to describe what the code is intended to do.
the cyclist
the cyclist 2017-1-8
编辑：the cyclist 2017-1-8
One thing to be aware of ...
It looks to me like your algorithm will be biased to overcount 'A' relative to the other elements, because in the case of a tied number of counts, consensus_num_ is going to choose the first index. (Similarly, 'C' will be more likely than 'G' and 'T', etc.)
Paolo Binetti
Paolo Binetti 2017-1-8
The code is intended for a random motif search algorithm within multiple sequences of DNA. Good on you for noticing the over-bias issue. It is OK for the particular problem I am solving.

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

the cyclist
the cyclist 2017-1-8
编辑：the cyclist 2017-1-8

1 个投票

This is starting to get a little obfuscated, but it's significantly faster:
list ='ACGT';
count = sum(motifs == reshape(list,[1 1 4]));
[count_max, consensus_num] = max(count,[],3);
consensus = list(consensus_num);
score = sum(sum(motifs ~= consensus));
The key algorithmic difference here is that I am able to compare against all four elements 'ACGT' in parallel, by permuting them into a third dimension.
You need R2016b or later in order for MATLAB to make the implicit dimension expansion to compare the 20x15x1 array against the 1x1x4 array. If you have an older version, you will explicitly need to use repmat.

2 个评论
显示 无 隐藏 无

the cyclist
the cyclist 2017-1-8
Also, because you are calling this function lots of time, you might want to do something like defining
list = 'ACGT';
plist = reshape(list,[1 1 4]);
in the calling function, and pass them in as argument, rather than needing to do that reshape every time. But I think that will be only a tiny speedup, if any.
Paolo Binetti
Paolo Binetti 2017-1-9
编辑：Paolo Binetti 2017-1-9
So, your first suggestion concerned a better way to compute "consensus":
list = 'ACGT';
consensus = list(consensus_num);
I find it more elegant and it is faster, but only slightly.
Then I realized that you do not strictly need "consensus" in order to compute "score". In fact it is faster to directly use "count" like this:
score = tk-sum(max(count)); % count is a 2D array
where "tk" is the number of lines times number of columns of "motifs", which can be fed as an input to the function. In addition, I also realized that I do not strictly need "consensus" as an output, so I removed its above computation altogether. The function then becomes:
function [score, count] = scoremotifs_3(motifs, tk)
count = [ sum(motifs == 'A',1) ;
sum(motifs == 'C',1) ;
sum(motifs == 'G',1) ;
sum(motifs == 'T',1) ];
score = tk-sum(max(count));
Now, about the "count" computation. Your suggestion to vectorize the comparison also worked, except that I have to reshape the resulting "count" from a 3D array to a 2D array, which is what I need as output. The function is therefore:
function [score, count] = scoremotifs_4(motifs, plist, k, tk)
count = sum(motifs == plist); count = reshape(count,k,4)';
score = tk-sum(max(count));
This already brings visible improvements. But then I wondered: since it's just two lines, why not write them directly in the main code rather than calling them as functions? I did that and the improvement was dramatic. In summary, I ended up replacing the whole function with just these two lines:
count = sum(motifs == plist); count = reshape(count,k,4)';
score = tk-sum(max(count));
Once again, for a beginner like me it is very instructive to learn that you can significantly improve even apparently simple pieces of code. Thank you.

请先登录，再进行评论。

更多回答（1 个）

the cyclist
the cyclist 2017-1-8

1 个投票

It's somewhat faster to calculate consensus like this:
list = 'ACGT';
consensus = list(consensus_num);

类别

在 帮助中心 和 File Exchange 中查找有关 Operators and Elementary Operations 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by