求连续重复序列的算法
求连续重复序列的算法
提问于 2014-05-09 22:12:45
我在寻找一个在基因组序列中找到短串联重复序列的算法。
基本上，给出一个非常长的字符串，它只能由4个字符“ATCG”组成，我需要在2-5个字符之间找到彼此相邻的短重复。
例: TACATGAGATCATGATGATGATGATGGAGCTGTGAGATC会给ATGATGATG或ATG重复3次
该算法需要扩展到100万个字符的字符串，所以我试图尽可能接近线性运行时。
我目前的算法是:由于重复可以是2-5个字符，所以我逐个检查字符串字符，看看N个字符是否与N+Xth字符相同，X是2到5。对于每个X的计数器，在不匹配的情况下计数顺序匹配和重置，我们知道当X=计数器时是否有重复。然后可以手动检查后续的重复。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-05-09 23:14:48
您正在查看每个给您提供O(n)的字符，因为您比较每个字符的下一个(最多)五个字符，这就给出了一个常量的c。
var data = get_input();
var compare = { `A`, `T`, `G`, `A`, `T` } // or whatever
var MAX_LOOKAHEAD = compare.length
var n
var c
for(n = data_array.length; n < size; i++) { // Has runtime O(n)
for(c = 0; c < MAX_LOOKAHEAD; c++) { // Maximum O(c)
if( compare[c] != data[i+c] ) {
break;
} else {
report( "found match at position " + i )
}
}
}很容易看出这会运行O(n*c)时间。由于c非常小，所以可以忽略它--我认为不能去掉这个常量--这将导致O(n)的整个运行时。
好消息：
您可以通过并行化来加快速度。例如，您可以在k间隔期内将其分割开来，并让多个线程为您完成任务，为它们提供适当的开始和结束索引。这可能会给你一个线性加速。
如果这样做，请确保将这些交叉口视为特殊情况，因为如果间隔将匹配分成两部分，则可能会错过匹配。
例如n = 50000
4个线程的分区：(n/10000) - 1 = 4。第五个线程不会有太多的工作要做，因为它只是处理交叉，这就是为什么我们不需要考虑它的开销(在我们的例子中很小)。
1 10000 20000 40000 50000
|-------------------|-------------------|-------------------|-------------------|
| <- thread 1 -> | <- thread 2 -> | <- thread 3 -> | <- thread 4 -> |
|---| |---| |---|
|___________________|___________________|
|
thread 5这就是它的样子：
var data;
var compare = { `A`, `T`, `G`, `A`, `T` };
var MAX_LOOKAHEAD = compare.length;
thread_function(args[]) {
var from = args[0];
var to = args[1];
for(n = from ; n < to ; i++) {
for(c = 0; c < MAX_LOOKAHEAD; c++) {
if( compare[c] != data[i+c] ) {
break;
} else {
report( "found match at position " + i )
}
}
}
}
main() {
var data_size = 50000;
var thread_count = 4;
var interval_size = data_size / ( thread_count + 1) ;
var tid[]
// This loop starts the threads for us:
for( var i = 0; i < thread_count; i++ ) {
var args = { interval_size * i, (interval_size * i) + interval_size };
tid.add( create_thread( thread_function, args ) );
}
// And this handles the intersections:
for( var i = 1; i < thread_count - 1; i++ ) {
var args = { interval_size * i, (interval_size * i) + interval_size };
from = (interval_size * i) - compare.length + 1;
to = (interval_size * i) + compare.length - 1;
for(j = from; j < to ; j++) {
for(k = 0; k < MAX_LOOKAHEAD; k++) {
if( compare[k] != data[j+k] ) {
break;
} else {
report( "found match at position " + j )
}
}
}
}
wait_for_multiple_threads( tid );
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23574738
复制相关文章
相似问题
腾讯云开发者
