Matt:LabNotes/2014-9-2

From ZhangLabWiki
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
  • 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