python - 在 Python 中从带有一些皱纹的相似性矩阵中找到最佳的成对对齐集

Question

我试图从相似性矩阵中找到两个序列的最佳比对。较高的值表示更好的对齐方式。

import numpy as np
a = np.array([
[0,5,5,5,5,5,5,5],
[3,10,0,0,0,9,0,0],
[3,0,10,0,0,0,1,0],
[3,0,0,9,0,0,0,0],
[3,0,0,0,0,0,0,10],
])

每行/列必须与一列/行对齐，但第 0 行和第 0 列除外，它们可以用于 0 个或多个对齐。

也就是说，这些序列的最佳比对是：

(0,0)
(1,1)
(2,2)
(3,3)
(0,4)
(0,5)
(0,6)
(4,7)

(1,5)不是对齐对，因为(1,1)是更好的对齐方式，并且行和列> 0 只能参与一次对齐。

任何建议表示赞赏。

Answer 1

我正在稍微改变问题。现在每一列都必须正好对齐一行，并且每一行都必须正好对齐一列。为了使矩阵成正方形，我添加了与行/列 0 等效的行/列，以前可以参与多个对齐。对于方阵和每行/列仅参与一次对齐的要求，该问题可以被视为稳定婚姻问题的一个实例。