## Marriage Matching Algorithm

Consider that we have probe 1 and 2 labeling some molecule as dots, and for each cell we have several signals for each probe, cf. 3 dots for probe 1 and 2 dots for probe 2. The we have an assignment that we want to pair them each, leaving one probe 1 dot unpaired (cf. In my case I know that a probe 1 dot and a probe 2 dot are on a same chromosome.) What would be the algorithm?

In broader sense, this is a combinatorial optimization problem but I thought there could be simpler way of doing this.. then following is some possibilities.

One way is to construct a cost function, such as “sum of distace between paired”, calculate cost funciton for all possible combinations and choose the one with the lowest sum.

I found otherway of doing this, by so-called "stable marriage algorithm". In this case, same each number of boys and girls are matched.

In Javascript it should be as follows:

function make_matches(gb, bg){ var N = gb.length; var boy = [], girl = [], position = [], rank = []; var b, g, r, s, t; for (g = 1; g <= N; g++){ rank[g] = [N+1]; for (r = 1; r <= N; r++){ b = gb[g-1][r-1]; rank[g][b] = r; } boy[g] = 0; } for (b = 1; b <= N; b++){ girl[b] = [0]; for (r = 1; r <= N; r++){ girl[b][r] = bg[b-1][r-1]; } position[b] = 0; } for (b = 1; b <= N; b++){ s = b; while (s != 0){ g = girl[s][++position[s]]; if (rank[g][s] < rank[g][boy[g]]){ t = boy[g]; boy[g] = s; s = t; } } } return boy; }

Only the problem when applying this to a problem with non-equal number of boys and girls population. For this case, either modify the above algorithm, or prepare a dummy with very low ranking to satisfy the equal number of populaiton for using the algorithm as the above.

**more references**