1. 生物学

人类有23对染色体。每条染色体上都排布着由碱基对组成的基因序列，碱基对有四种，即腺嘌呤（A，adenine）、胞嘧啶（C，cytosine）、鸟嘌呤（G，guanine）和胸腺嘧啶（T，thymine）。染色体序列可能以ACTGATTACA开始，可能会很长。最短的序列有4700万碱基对，最长的有2亿4700万碱基对。当代DNA测序技术一次只能测定大约20～1000个碱基对。生物学家需要想办法把许多短小的序列片段拼接成完整的序列。拼接序列是一个很难的计算问题，也是一个NP问题，因为如果我们提前知道了要拼接的DNA序列的全貌，我们可以用相对较快的方式检查某种拼接方式是否与之匹配。由于找不到解决这个NP问题的有效算法，生物学家需要更多的序列才能绘制出基因组图谱。而且很可能绘制出的图谱上有更多的空白和错误。研发出剪接序列的最优算法将显著提升基因图谱的质量。

DNA序列能编码信使RNA（mRNA）的序列，后者负责蛋白质的表达，而蛋白质则在组成生物细胞的几乎所有功能中发挥着关键性作用。蛋白质执行何种功能通常依赖于特定的几何形状，而mRNA序列决定蛋白质如何折叠，从而具有这种形状。蛋白质折叠的计算过程仍然是生物学一大未解之谜，研究P/NP问题对理解蛋白质折叠有着重要的启发作用，进而帮助人类预防和抵抗疾病。

蛋白质折叠识别（protein threading）是一种根据mRNA序列来预测蛋白质折叠方式的统计学方法。即使是这种对于理解蛋白质折叠有很大局限性的方法，也需要解决困难的NP问题。