===== 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 [[http://en.wikipedia.org/wiki/Combinatorial_optimization|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 [[http://en.wikipedia.org/wiki/Stable_marriage_problem|"stable marriage algorithm"]]. In this case, same each number of boys and girls are matched. 

In Javascript it should be as follows:
<code>
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;
}

</code>

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**

http://www.dcs.gla.ac.uk/research/algorithms/stable/

http://www.scopus.com/results/citedbyresults.url?sort=plf-f&cite=2-s2.0-0036557486&src=s&imp=t&sid=VGefBNpN1mm6vQdl2aIysKs:30&sot=cite&sdt=a&sl=0&origin=inward&txGid=VGefBNpN1mm6vQdl2aIysKs:2

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-461T492-4&_user=656666&_coverDate=04/30/2002&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000035599&_version=1&_urlVersion=0&_userid=656666&md5=8a948aa89d2b2682f26124c71e0dca5c