Differences

This shows you the differences between two versions of the page.

--- lecture_notes:04-22-2011 [2011/06/08 17:01]
eyliaw
+++ lecture_notes:04-22-2011 [2011/06/10 00:22]
eyliaw [Searching]
@@ Line 6: / Line 6: @@
 ===== Suffix array ======
-The suffix array is found by sorting the cyclic transformation lexicographically and taking their original indices.
+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:
+   X = GOOGOL$
+Cyclic transformation:
+GOOGOL$
+OOGOL$G
+OGOL$GO
+GOL$GOO
+OL$GOOG
+L$GOOGO
+$GOOGOL
+Sort:
+$GOOGOL
+GOL$GOO
+GOOGOL$
+L$GOOGO
+OGOL$GO
+OL$GOOG
+OOGOL$G
+   S(i) = [6,3,0,5,2,4,1]
+The Burrows Wheeler transform takes the last character of the sorted cyclic strings:
+   B(i) = LO$OOGG
+===== Searching =====
+We can use the FM-index to find the upper and lower bounds of a substring.
+C_X(a) is the number of characters lexicographically before a in X.
+   G 0
+   L 2
+   O 3
+O_X(a,i) is the number of occurrences of a in B_X[0,i].
+^ i ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^
+| 1 | L        | 0        | 1        | 0        |
+| 2 | LO       | 0        | 1        | 1        |
+| 3 | LO$      | 0        | 1        | 1        |
+| 4 | LO$O     | 0        | 1        | 2        |
+| 5 | LO$OO    | 0        | 1        | 3        |
+| 6 | LO$OOG   | 1        | 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.

Banana Slug Genomics

User Tools

Site Tools

Differences

Page Tools