Banana Slug Genomics

Workaround for broken symlinks on head and children nodes

1. Check assemblies/Pog/map-colorspace-5/Makefile for the workaround
   1. explicitly assigns working directory rather than using cwd

1. Kevin has been working on H. Pylori, which is a much more challenging genome than Pog. MAy have developed some new methods for dealing with genome assembly
2. One trick is a method to estimate how frequently a contig appears in a genome.
   1. Look at reads/base. For long regions, reads/base is roughly constant.
   2. Expect to have more reads/base in repeat regions.
   3. This measure is more noisy with smaller regions
3. Estimated gap size is helpful for interpolating smaller contigs between other contigs.
   1. Short fragments can fit in regions with large estimated gap size.
4. Biological tricks:
   1. c→b→a→b'→d
   2. an inversion of b→a→b' turns the scaffold into c→b→a'→b'→d… Note that flipping b→a→b' reverses and complements the sequences, so that it becomes (b')→a'→b' or b→a'→b'.

Burrows-Wheeler Transform (BWT)

1. The algorithm behind bowtie, bwa, soap2 and possibly a few other mapping algorithms.
2. The strength of this is it allows you to map short reads to a large genome rapidly and without alot of memory.
3. Dependent on a reference genome.
4. Indexes the genome and produces a fairly compact genome.
5. The current implementations are all optimized for short reads.
6. The algorithm inherently gets worse as the reads get longer.
7. Longer reads will have to be broken into shorter pieces, indexed the reads separately and piece them back together.

What is the Burrows-Wheeler Transform and where did it come from?

1. Came from data compression.
2. Original idea was to make a string and take an invertible string.
3. The converted string would be much easier to compress than the original string.
4. Also used for bzip.
5. Example of how BWT works:
   1. Note must, have an end marker at the end of the string
   2. Take the initial string (GOOGOL$) and all rotations:
      1. GOOGOL$
      2. OOGOL$G
      3. OGOL$GO
      4. GOL$GOO
      5. OL$GOOG
      6. L$GOOGO
   3. Sort them Lexographically
      1. $GOOGOL
      2. GOL$GOO
      3. GOOGOL$
      4. L$GOOGO
      5. OGOL$GO
      6. OL$GOOG
      7. OOGOL$G
   4. The BWT is the last column Array B
      1. 1 $GOOGOL
      2. 2 GOL$GOO
      3. 3 GOOGOL$
      4. 4 L$GOOGO
      5. 5 OGOL$GO
      6. 6 OL$GOOG
      7. 7 OOGOL$G
   5. How do you invert this thing and get the original string back?
      1. You know the all the letters in your original string. You know how to sort them alphabetically.
         1. This gives you the first column
      2. You know the first and the last are paired together.
         1. Take all the pairs you get from putting the first and last column together and reproduce the 2nd column.
   6. What is this really representing?
      1. You can also keep track of the permutation you did when you did the sorting. The array which maps position in BWT to original sorted array is know as the S
         1. 0⇒6 $GOOGOL
         2. 1⇒3 GOL$GOO
         3. 2⇒0 GOOGOL$
         4. 3⇒5 L$GOOGO
         5. 4⇒2 OGOL$GO
         6. 5⇒4 OL$GOOG
         7. 6⇒1 OOGOL$G
      2. These numbers are also a method of keeping track of the transform
   7. Let's say you have a repeated subsequence
      1. Take “GO” for example.
      2. All the repeated subsequences are clumped together (0 & 3) GOOGOL
   8. There's another way of looking at this from a computer science perspective
      1. Trie
         1. The branching structure of the tree
         2. The branching is based on the alphabet. The branching factor is the number of letters in your alphabet.
         3. BWT is aka a Prefix Trie
         4. [Insert Diagram] See the BWA paper for the picture [Fast and Accurate Short read alignment with Burrows-Wheeler Transform, Heng Li and Richard Durbin, bioinformatics 2009]
      2. It turns out there is a nice simple correspondence between the trie and the array of numbers in the BWT.
      3. Let's say you want to find a subsequence [OG] in the Trie.
         1. Invert the string and trace the path back to the first character. Each possibility is a child of that node.
         2. The table representation can also find all string starting with [OG] (4,4)
         3. Each node in the tree corresponds to a range from the array of the BWT.
         4. [GO] has range (1,2)
      4. Trie is not stored, but enough data to recalculate the trie is stored.
6. Algorithm
   1. C is the number of letters in the first letter of the BWT matrix lexicographically before a. [G⇒1,L⇒3,O⇒4)
   2. O(a,i) = # occurrences of letter a within B[0..1]
   3. R_(aw) = C(a) + O(a,R_(w)-1)+1, where a is a prefix letter and w is a word. R_ is the lower bound
   4. R-(aw) = C(a) + O(a, r-(w), where a is a prefix letter and w is a word. R- is the upper bound
   5. Let's see if we can map “GO”
      1. R_(nil) = 0
      2. R-(nil) = 6
      3. R_(“O”) = c(O) + O(“O”, -1) +1 = 4
      4. R-(“O”) = c(O) + O(“O”) + 1 = 6
      5. R_(“GO”) =
7. Kevin recommends reading the paper. Fast and accurate short read alignment with Burrows-Wheeler transform.[1]

References