lecture_notes:04-22-2011
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
lecture_notes:04-22-2011 [2011/06/09 23:39] eyliaw [Searching] |
lecture_notes:04-22-2011 [2015/08/09 23:06] 212.129.31.47 ↷ Links adapted because of a move operation |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Burrows Wheeler Aligner ====== | ====== 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. | + | We discussed the [[archive: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 ====== | ||
| Line 36: | Line 36: | ||
| C_X(a) is the number of characters lexicographically before a in X. | C_X(a) is the number of characters lexicographically before a in X. | ||
| - | $ 0 | + | G 0 |
| - | G 1 | + | L 2 |
| - | L 3 | + | O 3 |
| - | O 4 | + | |
| O_X(a,i) is the number of occurrences of a in B_X[0,i]. | O_X(a,i) is the number of occurrences of a in B_X[0,i]. | ||
| - | ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^ | + | ^ i ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^ |
| - | | 1 L | 0 | 1 | 0 | | + | | 1 | L | 0 | 1 | 0 | |
| - | | 2 LO | 0 | 1 | 1 | | + | | 2 | LO | 0 | 1 | 1 | |
| - | | 3 LO$ | 0 | 1 | 1 | | + | | 3 | LO$ | 0 | 1 | 1 | |
| - | | 4 LO$O | 0 | 1 | 2 | | + | | 4 | LO$O | 0 | 1 | 2 | |
| - | | 5 LO$OO | 0 | 1 | 3 | | + | | 5 | LO$OO | 0 | 1 | 3 | |
| - | | 6 LO$OOG | 1 | 1 | 3 | | + | | 6 | LO$OOG | 1 | 1 | 3 | |
| - | | 7 LO$OOGG | 2 | 1 | 3 | | + | | 7 | LO$OOGG | 2 | 1 | 3 | |
| - | + | ||
| - | + | There are then two recursive formulas to find the start and end positions of a substring. | |
| + | End R_(aW) = C(a) + O(a,R_(W) - 1) + 1 or 1 if W is the empty string | ||
| + | Start R-(aW) = C(a) + O(a,R-(W)) or (n - 1) if W is the empty string | ||
| + | Where a is the first character and W is the word. | ||
lecture_notes/04-22-2011.txt · Last modified: 2015/08/09 23:06 by 212.129.31.47
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
