这些JavaScript DNA补充算法是否等效和最优？

可以通过反转该串然后用其补体替换每个碱基（A-> T，T-> A，C-> G，G-> C）来找到对典型DNA碱基串的补充。例如，CTTAACCAGCGGACACGGGCTTGGC的互补序列是GCCAAGCCCGTGTCCGCTGGTTAAG。这些JavaScript DNA补充算法是否等效和最优？

我写了几个算法来做到这一点在JavaScript中，我想知道它们是否是等价的，即例如等效的时间复杂性，但也等同于在浏览器中找到补充和更新HTML文档与输出。我想了解正则表达式以及javacript如何被解释，编译和执行。

首先，脚本使用此正则表达式验证输入字符串s：/[^CGAT]/。如果输入字符串除了C，G，A或T之外还有一个字符，脚本将停止并提醒用户原因。接下来，该脚本将生成与var reverseSeq=s.split('').reverse().join('')(which I found here)相反的字符串。

然后这些javascript中的任何一个将反转的字符串转换为原始的补码。

1）

var complementSeq=''; 
for (i in reverseSeq){complementSeq=complementSeq+COMPLEMENT_BASES[reverseSeq[i]]};

2.）

complementSeq=reverseSeq.replace(/(A)|(C)|(T)|(G)/g, function (match) {return COMPLEMENT_BASES[match]})

2）取决于该对象上：COMPLEMENT_BASES={'A':'T','T':'A','G':'C','C':'G'};。

这些方法是否具有相同的效率，并且基本上是等价的？有没有其他的方法可以提高效率？

来源

2015-10-25 jwco

最快的方式可能是直接替换所有的正则表达式的功能。直到所有的替换都完成后，引擎才会返回。一些引擎提供在线更换。不知道JS虽然。 – sln

那么你可能加速它简化正则表达式有点因为你真的不使用多个预定义

var COMPLEMENT_BASES = {'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}, 
    re = /[ATCG]/g; 

var complementSeq = reverseSeq.replace(re, function ($0) { 
    return COMPLEMENT_BASES[$0] 
});

你也可以减半+迭代次数需要捕捉组。尽管如此，这是一个线性速度提升。即

var COMPLEMENT_BASES = { 
    'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G', 
    'AA': 'TT', 'AT': 'TA', 'AC': 'TG', 'AG': 'TC', 
    'TA': 'AT', 'TT': 'AA', 'TC': 'AG', 'TG': 'AC', 
    'CA': 'GT', 'CT': 'GA', 'CC': 'GG', 'CG': 'GC', 
    'GA': 'CT', 'GT': 'CA', 'GC': 'CG', 'GG': 'CC' 
}; 

var re = /[ATCG]{1,2}/g;

如果你会产生一个巨大的这个数据量，考虑是否的字符串ATCGs真的是最好的选择这里。例如，以下是使用整数更好吗？

__|_dec_|_bin_ <-- XOR --> _bin_|_dec_|__ 
A | 0 | 00  (3) 11   11 | 3 | T 
T | 3 | 11   11   00 | 0 | A 
C | 1 | 01   11   10 | 2 | G 
G | 2 | 10   11   01 | 1 | C

如果您跟踪序列长度您现在可以在32位异或做这种转变，所以每个XOR改造16个碱基。内存开销也由4.

在JavaScript中减小时，XOR运算符是^，即(0^3) === 3，(1^3) === 2; // true

来源

2015-10-25 22:12:31

的你的算法的大O效率是相同的。所有这三种算法都是O（n）复杂度（其中n是输入的长度）。我个人无法想象它可能比这更好，所以最终归结为分析代码以查看哪个更快。然而，有些事情要考虑：

正则表达式具有较高的初始编译成本，因此，如果这将要叫了很多，你可能要编译正则表达式。
函数调用在这种情况下也可能很昂贵（他们必须建立堆栈等），所以您可能想要远离正则表达式替换，因为这一点。
对于纯代码易读性，第一种方法赢得国际海事组织（主观我明白）。

另一件要考虑的事情可能是一次跨越两个或三个字母。再次，这将不得不被分析，但你可以建立一个基于两个或三个字母和他们的补充一次查找表。对于这样的事情，如果字符串长度足够大，循环操作和字符串连接操作可能会是一个相当大的开销。

来源

2015-10-25 22:16:29 syazdani

我想，你应该使用已经存在的数组并在加入之前映射补数值。

替换和使用正则表达式的开销比你真正需要的更多。

function complement(a) { 
 
    return { A: 'T', T: 'A', G: 'C', C: 'G' }[a]; 
 
}  
 

 
var sequence = 'CTTAACCAGCGGACACGGGCTTGGC', 
 
    complementSeq = sequence.split('').reverse().map(complement).join(''); 
 
document.write(complementSeq);

来源

2015-10-26 08:41:59

这些JavaScript DNA补充算法是否等效和最优？

回答

相关问题