FU Logo
  • Startseite
  • Kontakt
  • Impressum
  • Home
  • Listenauswahl
  • Anleitungen

Re: [Seqan-dev] Suffix links

<-- thread -->
<-- date -->
  • From: John Reid <j.reid@mail.cryst.bbk.ac.uk>
  • To: SeqAn Development <seqan-dev@lists.fu-berlin.de>
  • Date: Wed, 05 Jun 2013 09:32:08 +0100
  • Reply-to: SeqAn Development <seqan-dev@lists.fu-berlin.de>
  • Subject: Re: [Seqan-dev] Suffix links

Hi David,

Thanks for the pointers. I'll have a look. I'll probably use some slow method of creating suffix links until I have checked if my model is good. If it is I'll have a look at how to get the links efficiently.

Cheers,
John.


On 05/06/13 09:02, Weese, David wrote:
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



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

<-- thread -->
<-- date -->
  • References:
    • Re: [Seqan-dev] Suffix links
      • From: "Weese, David" <weese@campus.fu-berlin.de>
  • seqan-dev - June 2013 - Archives indexes sorted by:
    [ thread ] [ subject ] [ author ] [ date ]
  • Complete archive of the seqan-dev mailing list
  • More info on this list...

Hilfe

  • FAQ
  • Dienstbeschreibung
  • ZEDAT Beratung
  • postmaster@lists.fu-berlin.de

Service-Navigation

  • Startseite
  • Listenauswahl

Einrichtung Mailingliste

  • ZEDAT-Portal
  • Mailinglisten Portal