User Tools

Site Tools



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

Link to this comparison view

Next revision
Previous revision
Last revision Both sides next revision
lecture_notes:06-01-2015 [2015/06/01 13:35]
charles created
lecture_notes:06-01-2015 [2015/06/01 16:09]
Line 1: Line 1:
 +===== Suffix Arrays =====
 +Example Suffix Array, A[ ], of "​$banana"​
 +===== Burrows Wheeler Transform =====
 +An example BWT of "​^BANANA|"​
 +===== FM Index =====
 +An FM-index is created by first taking the Burrows-Wheeler transform (BWT) of the input text. For example, the BWT of the string T = "​abracadabra"​ is "​ard$rcaaaabb",​ and here it is represented by the matrix M where each row is a rotation of the text that has been sorted. The transform corresponds to the last column labeled L.
 + C[c] is a table that, for each character c in the alphabet, contains the number of occurrences of lexically smaller characters in the text.
 +The function Occ(c, k) is the number of occurrences of character c in the prefix L[1..k]
 <​code>​ <​code>​
 Charles M. - BWT Notes Charles M. - BWT Notes
Line 85: Line 112:
 Additional resources and better examples can be found below: Additional resources and better examples can be found below:
-{{BWT and FM Index tutorial:http://​​~langmea/​resources/​bwt_fm.pdf}}+ 
 +[[http://​​~langmea/​resources/​bwt_fm.pdf|BWT and FM Index tutorial]] 
 +[[http://​​pubmed/​19451168|BWT paper]] 
lecture_notes/06-01-2015.txt · Last modified: 2015/06/01 16:15 by jaredc