 |
The Laboratory Robotics Interest Group Home |
|
|
|
[web_discuss/_private/disc3_ahdr.htm]
Re: A CORRECTION for 384-well mathmatical puzzle.From: beckerds@sagian.com CommentsAs stated, the minimum number of digits needed is 4 times then number of digits of the barcode for the aliquots. To show the math, lets assume we are using the same length barcode for all aliquots ( n digits long ) -- which uses a 10 character alphabet ( 0-9 ). We can see that the total # of source barcodes is 10^n. If we make NO assumptions about the source barcodes (IE, the 384 well plate can be made of A,B,C,D (4 distinct 96 well aliquots) or B,B,D,D ( only 2 distinct aliquots ), we see the there will be (10^n)^4 different 384 well plates that can be made. This means that the barcode to uniquely identify the 384 well plate will need to have (base 10)log (10^n^4) = 4n digits. However, clearly, if we use that many digits, we might as well say that the 384 well barcode is just the concatination of the 4 96 well barcodes. (as originally proposed) However, your problem becomes more interesting (as you've noticed) when the source space is limited. For instance, what would have happened if we had assumed that order of 96 well plates on the 384 well plate is irrelevant, and furthermore, there are no repetitions. (e.g. the 384 well plate called A,A,C,C cannot be made) In this case, we are restricting the # of 384 well plates that can be created -- and therefore we expect that some compression algorithm exists. Using a similar argument to our last problem, we see, m = # of 384 well plates allowable = (10^4)(10^4 - 1)(10^4 - 2)(10^4 - 3) / 4! (base 10) log m = 4n - 1.38 = # of digits. So, what this is saying is that a perfect compression algorithm exists that produces a unique 384 well barcode of (4n - 1) digits. So, unfortunately, the only true solutions I can give people looking into this problem is "What assumptions can you make about the source plates?" Kevin Olsen's assumption, thatsources will all be within 9 of the next closest, we can then have great compression. However, without any assumptions, then there is unfortunately no unique mapping from source to destination barcode using less than 4n digits. (Postscript: This entire discussion assumed constant length 384 well barcodes. Not making that assumption, the line : (base 10) log m = 4n - 1.38 = # of digits. becomes a monstrosity lower bounded by (base 11 ) log m = 4n / 1.04 which for 6 digit source barcodes would be 23. If anyone is adventurous enough to try to find a best case solution to variable length destination barcodes, please send me the solution! =:> ) Doug Becker The views expressed don't reflect the views of the company, unless I'm right. [web_discuss/_private/disc3_aftr.htm] |
|
|
with questions or comments about this web site.