我对Jon Limjap的采访事故感到好奇,并开始寻找有效的方法进行回文检测.我检查了回文高尔夫答案,在我看来答案中只有两个算法,反转字符串并检查尾部和头部.
def palindrome_short(s):
length = len(s)
for i in xrange(0,length/2):
if s[i] != s[(length-1)-i]: return False
return True
def palindrome_reverse(s):
return s == s[::-1]
我认为这些方法都不能用于检测巨大DNA序列中的确切回文.我环顾四周,没有找到任何关于这种超高效方式的免费文章.
一种好的方法可能是以分而治之的方式并行化第一个版本,为每个线程或处理器分配一对char数组1..n和length-1-n..length-1.
什么是更好的方式？
你知道任何？
只给一个回文,你必须在O(N)中做,是的.如上所述,通过拆分字符串可以提高多处理器的效率.
现在说你想做精确的DNA匹配.这些字符串长达数千个字符,并且它们非常重复.这为我们提供了优化的机会.
假设你将一个1000字符长的字符串分成5对100,100.代码如下所示:
isPal(w[0:100],w[-100:]) and isPail(w[101:200], w[-200:-100]) ...
等......第一次进行这些比赛时,你必须处理它们.但是,您可以将已完成的所有结果添加到哈希表的哈希表映射对中:
isPal = {("ATTAGC", "CGATTA"): True, ("ATTGCA", "CAGTAA"): False}
等......这会占用太多的记忆.对于100,100对,哈希映射将具有2*4 ^ 100个元素.假设你只存储两个32位的字符串哈希作为键,你将需要10 ^ 55兆字节,这是荒谬的.
也许如果你使用较小的字符串,问题可以解决.那么你将有一个巨大的散列图,但至少回文可以说10x10对需要O(1),因此检查1000字符串是否为回文将需要100次查找而不是500次比较.它仍然是O(N),但......
京公网安备 11010802040832号 | 京ICP备19059560号-6 