Generalisert suffiks tre - Generalized suffix tree

Suffiksetre for strengene ABAB og BABA . Suffiks-lenker ikke vist.

I informatikk er et generalisert suffiks tre et suffiks tre for et sett med strenger . Gitt settet med strengene av total lengde , er det et Patricia-tre som inneholder alle suffikser av strengene. Det brukes mest i bioinformatikk . ${\ displaystyle D = S_ {1}, S_ {2}, \ prikker, S_ {d}}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Funksjonalitet

Den kan bygges i tid og rom, og kan brukes til å finne alle forekomster av en streng med lengde i tid, noe som er asymptotisk optimal (forutsatt at alfabetets størrelse er konstant). ${\ displaystyle \ Theta (n)}$ ${\ displaystyle z}$ ${\ displaystyle P}$ ${\ displaystyle m}$ ${\ displaystyle O (m + z)}$

Når du konstruerer et slikt tre, bør hver streng polstres med et unikt markeringssymbol (eller streng) utenfor alfabetet for å sikre at ikke noe suffiks er et underlag for en annen, og garanterer at hvert suffiks representeres av en unik bladnode.

Algoritmer for å konstruere en GST inkluderer Ukkonens algoritme (1995) og McCreights algoritme (1976).

Eksempel

Et suffiksetre for strengene ABAB og BABA er vist i figuren ovenfor. De er polstret med de unike terminatorstrenger $0 og $1 . Tallene i bladnodene er strengnummer og startposisjon. Legg merke til hvordan en venstre til høyre gjennomgang av bladnodene tilsvarer den sorterte rekkefølgen på suffiksen. Terminatorene kan være strenger eller unike, enkle symboler. Kanter på $ fra roten er utelatt i dette eksemplet.

Alternativer

Et alternativ til å bygge et generalisert suffiks-tre er å sammenkoble strengene, og bygge et vanlig suffiks-tre eller suffiks-array for den resulterende strengen. Når treff blir evaluert etter et søk, blir globale posisjoner kartlagt i dokumenter og lokale posisjoner med en eller annen algoritme og / eller datastruktur, for eksempel et binært søk i start- / sluttposisjonene til dokumentene.

Referanser

^ Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Generaliserte suffikstrær for biologiske sekvensdata". Biotechnology Computing, Proceedings of the Twenty-Seventh Hawaii International Conference on . s. 35–44. doi : 10.1109 / HICSS.1994.323593 .
^ Gusfield, Dan (1999) [1997]. Algoritmer på strenger, trær og sekvenser: Datavitenskap og beregningsbiologi . USA: Cambridge University Press. ISBN 978-0-521-58519-4 .

Eksterne linker

Media relatert til generalisert suffiks-tre på Wikimedia Commons
AC-implementering av Generalized Suffix Tree for to strenger

[BRCR-1] Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Generaliserte suffikstrær for biologiske sekvensdata". Biotechnology Computing, Proceedings of the Twenty-Seventh Hawaii International Conference on . s. 35–44. doi : 10.1109 / HICSS.1994.323593 .

[Gus97-2] Gusfield, Dan (1999) [1997]. Algoritmer på strenger, trær og sekvenser: Datavitenskap og beregningsbiologi . USA: Cambridge University Press. ISBN 978-0-521-58519-4 .

Languages

In other projects