我是Python新手,已经花了很多时间来解决这个问题,希望有人能帮助我。 我需要找出两个序列之间的重叠。重叠在第一个序列的左端和第二个序列的右端。 我希望函数找到重叠,并返回它。
我的顺序是:
s1 = "CGATTCCAGGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC"
s2 = "GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTCGTCCAGACCCCTAGC"
我的函数应该命名为
def getOverlap(left, right)
其中s1
是左序列,s2
是右序列。
结果应该是
‘GGCTCCCCACGGGGTACCCATAACTTGACAGTAGATCTC’
如有任何帮助,我们将不胜感激
请查看^{} 库,并更准确地查看^{} :
您可以使用^{} :
Knuth-Morris-Pratt算法是一个很好的方法,可以在另一个字符串中找到一个字符串(因为我看到了DNA,我猜你希望这个可以扩展到。。。十亿?)。
The link where I got the KMP python code(和一个内置的,由于运行时常量的存在,对于小问题来说更快)。
为了提高性能,可以使用前缀表和字符串的哈希窗口作为基4整数(在生物学中,我们称它们为k-mers或oligos)。;)
祝你好运!
编辑:还有一个很好的技巧,可以对包含第一个字符串中的每个前缀(n total)和第二个字符串中的每个前缀(n total)的列表进行排序。如果它们共享最大的公共子序列,则它们必须在排序列表中相邻,因此从排序列表中最接近的另一个字符串中查找元素,然后获取完全匹配的最长前缀。:)
相关问题 更多 >
编程相关推荐