原生Python中的DNA序列比对（没有生物球）

Question

我有一个有趣的遗传学问题，我想用原生Python解决（除了标准库之外什么都没有）。这是为了使解决方案非常容易在任何计算机上使用，而不需要用户安装额外的模块。在

给你。我收到了来自454个新一代测序的100000个DNA序列（高达20亿个）。我想把两端的引物都去掉。示例：

seq001: ACTGACGGATAGCTGACCTGATGATGGGTTGACCAGTGATC
        --primer-1---                 --primer-2-

引物可以出现一次或多次（一次接一次）。正常的感觉总是在左边，相反的在右边。因此，我的目标是找到引物，切断序列，使之只剩下不含引物的部分。为此，我想使用一个在原生Python中实现的经典对齐算法（即：smithwaterman）（即：不是通过biopython实现的）。我知道这可能需要相当长的时间（最多几个小时）。在

注：这不是一个直接的“词”搜索，因为DNA，无论是序列还是引物，都可能因各种技术原因而“突变”。在

你会用什么？在

Answer 1

您可以很简单地使用regex来实现这一点？我不认为会那么复杂！事实上，我刚刚完成了一些代码，为这里的大学里的一个家伙做了一些与此类似的事情！在

如果不寻找引物的精确拷贝，由于突变，那么可以应用模糊匹配元素！我所做的版本只是在开始和结束处查找完全匹配的底漆，然后使用以下代码返回值减去这些底漆：

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中fuzzy regex的链接http://hackerboss.com/approximate-regex-matching-in-python/

Answer 2

下面是一篇关于这个主题的论文：

Rocke, On finding novel gapped motifs in DNA sequences, 1998。在

希望从那篇论文及其参考文献中，再加上引用上述内容的其他论文，你可以找到许多算法的想法。虽然找不到python代码，但是可以找到算法的描述，然后可以在python中实现这些算法。在

Answer 3

简单地研究一下这个算法，这不是一件容易的事。这需要一些非常严肃的算法工作。试着把你的期望从“小时”调整到“几天或几周”。在

实现这一点的程序员需要：

• 精通通用python编程
• 有算法编程经验，对时间复杂度有很好的理解。在
• 很好地理解python数据结构，如dict、set和deque，以及它们的复杂性特征。在
• 熟悉单元测试。在

那个程序员现在可能是也可能不是你。这听起来是个很棒的项目，祝你好运！在