Finding the optimal set of pairwise alignments from a similarity matrix, with some wrinkles, in Python
Question: I am trying to find the best alignment of two sequences from a similarity
matrix. Higher values indicate better alignments.

    
    
    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],
    ])
    

Each row/column must be aligned to exactly one column/row, except for row 0
and column 0, which may be used in 0 or more alignments.

That is, the best alignment for these sequences is:

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

`(1,5)` is not an aligned pair, because `(1,1)` is a better alignment, and
rows and columns > 0 can only participate in one alignment.

Any suggestions are appreciated.


Answer: I am changing the problem slightly. Now each column must be aligned to exactly
one row, and each row must be aligned to exactly one column. To make the
matrix square, I am adding rows/columns that are equivalent to row/column 0,
which previously could participate in multiple alignments. With a square
matrix and a requirement that each row/column participate in only one
alignment, the problem can be treated as an instance of the stable marriage
problem.

