python - 原生 Python 中的 DNA 序列比对(无 biopython)

Question

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

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

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

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

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

你会用什么？

Answer 1

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

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

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

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