This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
lecture_notes:04-22-2011 [2011/06/08 16:46] eyliaw [Burrows Wheeler Transform] |
lecture_notes:04-22-2011 [2011/06/08 17:01] eyliaw |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Burrows Wheeler Transform ====== | + | ====== Burrows Wheeler Aligner ====== |
- | The Burrows Wheeler Transform can be used to compress a suffix array, and is used in [[bioinformatic_tools:bwa]]. | + | 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 ====== | ||
- | 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 the | + | 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 ====== | ===== Suffix array ====== | ||
The suffix array is found by sorting the cyclic transformation lexicographically and taking their original indices. | The suffix array is found by sorting the cyclic transformation lexicographically and taking their original indices. | ||
- | Range in the suffix array can be found by the R_ and R- |