Genome-scale algorithmics (GSA)

MUMs

Maximal Unique Matches (MUMs) computed with a bidirectional BWT-index. This is an implementation of one of the results in our ESA 2013 paper, plugged into to Simon Gog's SDSL library. We conducted a small benchmark to show it is competive. Two versions of human chromosome 20  (2*60 MB) were used as input, and running time and peak space usage was compared againts vmatch and mummer. We used suffix array sampling frequency 256 in our implementation; the mechanism described in ESA paper to avoid suffix array samples completely was not implemented.

  time (s) space (MB)
ours 751 207
vmatch 437 938
mummer 97 930

 

25.09.2013 - 16:40 Veli Mäkinen
13.09.2013 - 10:46 Veli Mäkinen