如何用Python基础函数实现Smith-Waterman序列比对算法的初始部分

实现思路 #

• 输入校验：接收两个字符串类型的序列s、t，无需额外外部依赖，仅用Python基础语法实现
• 打分规则固定为需求指定标准：碱基匹配得+1，错配扣2分，插入/删除（InDel）扣1分，矩阵所有位置得分不得低于0
• 矩阵初始化：创建大小为(len(s)+1) * (len(t)+1)的二维列表，第0行、第0列所有元素默认初始化为0，符合算法初始条件
• 矩阵填充逻辑：
  • 外层循环遍历第一条序列的每个字符（对应矩阵行索引i从1到len(s)）
  • 内层循环遍历第二条序列的每个字符（对应矩阵列索引j从1到len(t)）
  • 分别计算三个方向的候选得分：
    • 匹配/错配得分：matrix[i-1][j-1] + 匹配分/错配分，对应两个序列当前位置碱基对齐的情况
    • 空位罚分（行方向）：matrix[i-1][j] - 1，对应第一条序列当前位置插入空位的情况
    • 空位罚分（列方向）：matrix[i][j-1] - 1，对应第二条序列当前位置插入空位的情况
  • 当前位置matrix[i][j]取三个候选得分和0的最大值，保证无负分

可运行代码 #

def build_sw_matrix(s: str, t: str) -> list[list[int]]:
    """
    构建Smith-Waterman算法的打分矩阵
    :param s: 第一条输入序列
    :param t: 第二条输入序列
    :return: 填充完成的打分矩阵
    """
    n = len(s)
    m = len(t)
    # 初始化(n+1)行(m+1)列的矩阵，所有元素初始为0
    matrix = [[0]*(m+1) for _ in range(n+1)]
    
    def get_base_score(a: str, b: str) -> int:
        """计算两个碱基的匹配/错配得分"""
        if a == b:
            return 1
        else:
            return -2
    
    # 遍历填充矩阵
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 对角线得分：匹配/错配
            match_score = matrix[i-1][j-1] + get_base_score(s[i-1], t[j-1])
            # 上方得分：s序列插入空位
            delete_score = matrix[i-1][j] - 1
            # 左方得分：t序列插入空位
            insert_score = matrix[i][j-1] - 1
            # 取最大值，最小为0
            matrix[i][j] = max(match_score, delete_score, insert_score, 0)
    
    return matrix

# 测试用例
if __name__ == "__main__":
    s = "ACGT"
    t = "ACGT"
    sw_matrix = build_sw_matrix(s, t)
    # 打印矩阵
    print("生成的Smith-Waterman打分矩阵：")
    for row in sw_matrix:
        print(row)

代码测试输出 #

测试序列为ACGT和ACGT时，输出结果如下：

生成的Smith-Waterman打分矩阵：
[0, 0, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 0, 2, 1, 0]
[0, 0, 1, 3, 2]
[0, 0, 0, 2, 4]

和算法规则预期结果完全一致。

内容的提问来源于stack exchange，提问作者user8769986