找到与 python 局部对齐的所有可能路径

Question

我正在尝试用 Python 实现 Smith-Waterman 算法。我能够构建评分矩阵、检索单元格以开始对齐、实施以及包含我们可用于重建对齐的可能移动的矩阵。问题是实现动态部分以创建一个列表列表，其中包含所有可能的路径，这些路径将用于定义所有可能的局部对齐方式。

我会给你一张矩阵的小例子的屏幕截图，其中包含可能的运动，这里我们有只有一个运动的单元格，但它的实现允许我们包含所有三种可能的运动（U = up，D = diagonal，L = left )

您是否有任何建议或参考来了解如何实现启用算法动态部分的功能？

非常感谢您提供的任何帮助。

这是我实现的：

M=[["N","N","N"],
   ["N",'DU','DLU'],
   ["N",'DU','DL']]
#print(M[2][1]) #[2 row] [1] colum
start_point = (2,2)
pipaths = []
def prova(M,starter,lista):
    beginning = M[starter[0]][starter[1]]
    # print((starter[0],starter[1]))
    paths = lista
    for i in beginning:
        if len(i) == 1:
            if i == 'D':
                paths.append(i) 
                # print((starter[0]-1,starter[1]-1))
                prova(M,(starter[0]-1,starter[1]-1),paths)
            elif i == 'L':
                paths.append(i) 
                # print((starter[0],starter[1]-1))
                prova(M,(starter[0],starter[1]-1),paths)
            elif i == 'U': 
                paths.append(i)
                # print((starter[0]-1,starter[1]))
                prova(M,(starter[0]-1,starter[1]),paths)
            elif i == 'N':
                # print(paths)
                return paths
        else:
            for k in i:
                if k == 'D':
                    paths.append(k)
                    # print((starter[0]-1,starter[1]-1))
                    prova(M,(starter[0]-1,starter[1]-1),paths)
                elif k == 'L':
                    paths.append(k)
                    # print((starter[0],starter[1]-1))
                    prova(M,(starter[0],starter[1]-1),paths)
                elif i == 'U':
                    paths.append(i)
                    # print((starter[0]-1,starter[1]))
                    prova(M,(starter[0]-1,starter[1]),paths)
    return paths

all_path = []        
all_path.append(prova(M,start_point,pipaths))
print(all_path)

代码生成的输出：

[['D', 'D', 'U', 'L', 'D', 'U', 'D', 'U']]

我想要的输出：

[['D', 'D'], ['D', 'U'], ['L', 'D'], ['L', 'U', 'D'], ['L', 'U', 'U']]