Árbol de sufijos generalizado

En informática , un árbol de sufijos generalizado es un árbol de sufijos para un conjunto de cadenas . Dado el conjunto de cadenas $D=S_{1},S_{2},\dots ,S_{d}$ de longitud total $n$ , es un árbol Patricia que contiene todos $n$ sufijos de las cadenas. Se utiliza principalmente en bioinformática . ^{[ 1 ]}

Funcionalidad

Se puede construir en $\Theta (n)$ tiempo y espacio, y se puede utilizar para encontrar todas las $z$ ocurrencias de una cadena $P$ de longitud $m$ en $O(m+z)$ tiempo, que es asintóticamente óptimo (suponiendo que el tamaño del alfabeto es constante ^{[ 2 ]}^{: 119} ).

Al construir dicho árbol, cada cadena debe rellenarse con un símbolo (o cadena) marcador único fuera del alfabeto para garantizar que ningún sufijo sea una subcadena de otro, asegurando así que cada sufijo esté representado por un nodo hoja único.

Entre los algoritmos para construir un GST se incluyen el algoritmo de Ukkonen (1995) y el algoritmo de McCreight (1976).

Ejemplo

En la figura superior se muestra un árbol de sufijos para las cadenas ABABy BABA. Estas cadenas se rellenan con las cadenas terminadoras únicas $0y $1. Los números en los nodos hoja corresponden al número de cadena y la posición inicial. Observe cómo un recorrido de izquierda a derecha de los nodos hoja se corresponde con el orden de los sufijos. Los terminadores pueden ser cadenas o símbolos únicos. $En este ejemplo, se omiten las aristas que parten de la raíz.

Alternativas

Una alternativa para construir un árbol de sufijos generalizado es concatenar las cadenas y construir un árbol de sufijos regular o una matriz de sufijos para la cadena resultante. Al evaluar los resultados de una búsqueda, las posiciones globales se asignan a documentos y las posiciones locales se representan mediante algún algoritmo o estructura de datos, como una búsqueda binaria en las posiciones inicial y final de los documentos.

Referencias

↑ Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Árboles de sufijos generalizados para datos de secuencias biológicas". Biotechnology Computing, Actas de la Vigésimo Séptima Conferencia Internacional de Hawái sobre . pp. 35– 44. doi : 10.1109/HICSS.1994.323593 .
↑ Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: Informática y biología computacional . EE. UU.: Cambridge University Press. ISBN 978-0-521-58519-4.

Enlaces externos

Contenido multimedia relacionado con el árbol de sufijos generalizado en Wikimedia Commons.
Implementación AC del árbol de sufijos generalizado para dos cadenas

[BRCR-1] Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Árboles de sufijos generalizados para datos de secuencias biológicas". Biotechnology Computing, Actas de la Vigésimo Séptima Conferencia Internacional de Hawái sobre . pp. 35– 44. doi : 10.1109/HICSS.1994.323593 .

[Gus97-2] Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: Informática y biología computacional . EE. UU.: Cambridge University Press. ISBN 978-0-521-58519-4.

[ 1 ]

[ 2 ]