Relative FM-Indexes

Intuitively, if two strings S-1 and S-2 are sufficiently similar and we already have an FM-index for S-1 then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S-2. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.