User Tools

Site Tools


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

blogtng/2010-05-14/marriage_matching_algorithm.txt · Last modified: 2016/05/24 12:46 by

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki