Re: [Seqan-dev] Suffix links

["Weese, David" <weese@campus.fu-berlin.de>]

Hi John,

we not yet have suffix links in our suffix trees. There are two papers proposing how to post-compute a suffix link table on top of an enhanced suffix array:

Abouelhoda, M., Kurtz, S., & Ohlebusch, E. (2004). Replacing suffix trees with enhanced suffix arrays. Journal of Discrete Algorithms, 2(1), 53–86.

or on any suffix tree/array:

Maaß, M. G. (2007). Computing suffix links for suffix trees and arrays. Information Processing Letters, 101(6), 250–254. doi:10.1016/j.ipl.2005.12.012

I haven't looked how they are implemented and which one is faster or more practical for large datasets. Maybe you can use the implementation and tell us about your experiences or we'll find a Bsc/MSc. student to try them out.

Cheers,

David

Am 31.05.2013 um 20:38 schrieb John Reid <j.reid@mail.cryst.bbk.ac.uk>:

Hi,

I had a little google for this but I didn't find the answer. I have an
algorithm which should run quickly on a suffix tree or array. However in
the algorithm I will need to move from a node for say the suffix GCCGAA
to the node for CCGAA. This is obviously expensive in a normal suffix
tree. However I think that some suffix tree construction algorithms
create suffix links (perhaps Ukkonen's algorithm) that do exactly this.
Does SeqAn contain such algorithms and how can I access the suffix links
after construction?

Thanks,
John.

_______________________________________________
seqan-dev mailing list
seqan-dev@lists.fu-berlin.de
https://lists.fu-berlin.de/listinfo/seqan-dev