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