原生 Python 中的 DNA 序列比对（无 biopython）

Question

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

这里是。我从 454 次新一代测序运行中收到了 100,000 条 DNA 序列（最多 20 亿条）。我想修剪四肢，以去除两端可能存在的引物，无论是正常序列还是有义序列。示例：

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

引物可以出现一次或多次（一个接一个）。正常意义总是在左边，反之意义总是在右边。因此，我的目标是找到引物，剪切序列，仅保留无引物的部分。为此，我想使用一种经典的对齐算法（即：Smith-Waterman），该算法已在本机 Python 中实现（即：不是通过 biopython）。我知道这可能需要相当长的时间（最多几个小时）。

注意：这不是直接的“单词”搜索，因为序列和引物中的 DNA 都可能因各种技术原因而“突变”。

你会用什么？

Answer 1

简单研究一下该算法，这并不是一件容易的事。这将需要一些非常认真的算法工作。尝试将您的期望从“几小时”调整为“几天或几周”。

实现此功能的程序员需要：

• 具备较高的一般 Python 编程能力
• 算法编程经验，并且对时间复杂度有很好的理解。
• 很好地理解 dict、set、deque 等 Python 数据结构及其复杂性特征。
• 熟悉单元测试。

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

Answer 2

这是一篇关于该主题的论文：

Rocke，《关于寻找小说空白》 DNA 序列中的基序，1998。

希望从该论文及其参考文献以及引用上述内容的其他论文中，您可以找到许多关于算法的想法。您不会找到 Python 代码，但您可能会找到可以在 Python 中实现的算法描述。

Answer 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/