This is an old revision of the document!
====== Burrows Wheeler Aligner ====== We discussed the [[bioinformatic_tools:bwa]]. It uses the Burrows Wheeler Transform to represent a prefix trie, allowing for short read alignment with mismatches and gaps. ===== The prefix trie ====== The prefix trie is a tree built from possible prefixes, starting at the end of a branch and going backwards to the root. Each node is the range in the suffix array where that prefix may be found. Each edge is a character in the prefix. A string can be found--allowing for mismatches and gaps--in the prefix tree by going up each branch and comparing characters to the prefix until the all characters have been matched or the mismatch limit is met. ===== Suffix array ====== The suffix array is found by appending an end character and sorting the cyclic transformation of the resulting string lexicographically and storing the original indices. Example: GOOGOL Append end character: GOOGOL$ Cyclic transformation: 1 GOOGOL$ 2 OOGOL$G 3 OGOL$GO 4 GOL$GOO 5 OL$GOOG 6 L$GOOGO 7 $GOOGOL Sort: 7 $GOOGOL 4 GOL$GOO 1 GOOGOL$ 6 L$GOOGO 3 OGOL$GO 5 OL$GOOG 2 OOGOL$G
