Matt:LabNotes/2014-9-2
Jump to navigation
Jump to search
Decoding Barcode Algorithm Calculation[edit]
Design[edit]
- Based on Gunderson article in Genome Research (2004) "Decoding Randomly Ordered DNA Arrays"
- Use multiple stages (cycles) of 2 or 3 dyes
- Every barcode should have 2 blank stages for error correction
- Most common error is color -> blank or blank -> color (color1 -> color2 is very unlikely)
- Therefore if a common error occurs it will be easy to recognize and discard because will have greater than or fewer than 2 blank stages
- Last caveat: No barcode can have the same color for all cycles
Calculate Number of Unique Barcodes[edit]
- With 7 stages of 3 dyes with 2 blank stages
- First ignore the blank stages and only consider the 5 colored stages
- 3^5=243 is the number of permutations(combinations)
- Next consider all the possible positions where the pair of blanks could be
- This is the combination 7 choose 2 = 6+5+4+3+2+1 = 21
- ie. 1&2, 1&3, 1&4, ...,1&7, 2&3, 2&4, ..., 6&7
- This is the combination 7 choose 2 = 6+5+4+3+2+1 = 21
- Combining the 5 color stages with the 2 blank stages
- 3^5 x 21 = 5,103
- Finally we must remove any barcodes where every color stage is the same color (e.g. Red,0,Red,Red,Red,0,Red)
- For each of the 3 colors there are 21 of these barcodes (all the possible combinations of where the blank stages are)
- Therefore there are 3 x 21 = 63 barcodes with only one color
- Result: 3^5 x 21 - 3 x 21 = 5,040 Unique Barcodes