在原生Python中进行DNA序列比对（不使用biopython）
我有一个有趣的遗传学问题，想用纯Python来解决（不使用任何额外的库）。这样做是为了让解决方案在任何电脑上都能很容易使用，不需要用户安装额外的模块。
问题是这样的。我收到了成千上万条DNA序列（最多可以达到20亿条），这些序列来自一次454新一代测序。我想要修剪这些序列的两端，以去掉可能存在的引物，这些引物可能在序列的两端都有，包括正常序列和反向序列。举个例子：
seq001: ACTGACGGATAGCTGACCTGATGATGGGTTGACCAGTGATC
--primer-1--- --primer-2-
引物可能出现一次或多次（一个接一个）。正常序列总是在左边，反向序列在右边。因此，我的目标是找到这些引物，剪切序列，只保留没有引物的部分。为此，我想使用一个经典的比对算法（比如：Smith-Waterman），而且是用纯Python实现的（也就是说，不通过biopython）。我知道这可能需要相当长的时间（可能要几个小时）。
注意：这不是直接的“单词”搜索，因为DNA序列和引物可能因为各种技术原因而“变异”。
你会用什么方法呢？
3 个回答
你可以很简单地用正则表达式来做到这一点。我觉得这并不复杂！实际上，我刚刚为我们大学的一个同学写了一段代码，功能和这个差不多！
如果不需要完全匹配引物，因为可能会有突变，那么可以使用模糊匹配的方式！我写的版本很简单，就是在开始和结束的位置寻找完全匹配的引物，然后用以下代码返回去掉这些引物后的值：
pattern = "^" + start_primer + "([A-Z]+)" + end_primer + "$" # start primer and end primer are sequences you are looking to match
regex = re.match(pattern, sequence) # sequence is the DNA sequence you are analyzing
print regex.group(1) # prints the sequence between the start and end primers
这里有一个关于Python中模糊正则表达式的链接 http://hackerboss.com/approximate-regex-matching-in-python/
这里有一篇关于这个主题的论文：
Rocke, 关于在DNA序列中寻找新颖的间隙模式，1998年。
希望通过这篇论文及其参考文献，还有其他引用了这篇论文的文章，你能找到很多算法的想法。虽然你不会找到Python代码，但你可能会找到一些算法的描述，然后你可以用Python来实现这些算法。
简单了解一下这个算法，发现这可不是简单的事情。这需要非常严谨的算法工作。你可能需要把自己的预期从“几个小时”调整到“几天或几周”。
实现这个算法的程序员需要：
- 对Python编程有很高的能力
- 有算法编程的经验，并且对时间复杂度有很好的理解。
- 对Python的数据结构，比如字典（dict）、集合（set）和双端队列（deque），以及它们的复杂性特征有很好的理解。
- 熟悉单元测试（unittests）。
现在这个程序员可能是你，也可能不是。这个项目听起来很棒，祝你好运！