title: Toward optimizing the cache performance of suffix trees for sequence analysis algorithms suffix tree cache performance optimization.
abstract: Efforts have been devoted to accelerating the construction of suffix trees. However, little attention has been given to post-construction operations on suffix trees. Therefore, we investigate the effects of improved spatial locality on certain post-construction operations on suffix trees. We used a maximal exact repeat finding algorithm, MERF, on which software REPuter is based, as an example, and conducted experiments on the 16 chromosomes of the yeast Saccharomyces cerevisiae. Two versions of suffix trees were customized for the algorithm and two variants of MERF were implemented accordingly. We showed that in all cases, the optimal cache-oblivious MERF is faster and displays consistently lower cache miss rates than their non-optimized counterparts.
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut, 06269 Storrs, CT, USA. chih.lee@uconn.edu
authors.forename: Chih
authors.initials: C
authors.lastname: Lee
authors.forename: Chun-Hsi
authors.initials: CH
authors.lastname: Huang
mesh_terms: D000465:Algorithms; D015825:Chromosomes, Fungal / Q000235:genetics; D019295:Computational Biology; D016681:Genome, Fungal; D012091:Repetitive Sequences, Nucleic Acid; D012441:Saccharomyces cerevisiae / Q000235:genetics; D017421:Sequence Analysis / Q000706:statistics & numerical data*; D012984:Software